JOIN
 Match Editorials
TCHS SRM 5
Wednesday, July 5, 2006

Match summary

This match continued the streak of Burunduks. With the best overall score and with 3 successful submissions, Burunduk3 took first place, Burunduk2 took second place, despite losing his 250 and getting no challenges he lost by less than 50 points. Impressive! Rounding out 3rd place was Weiqi.

# The Problems

TVSize
Used as: Level One:
 Value 250 Submission Rate 73 / 80 (91.25%) Success Rate 22 / 73 (30.14%) High Score sharpobject for 246.41 points (3 mins 26 secs) Average Score 203.43 (for 22 correct submissions)

This problem appeared to be really tricky for most of the coders. The main source of the troubles was the classical floating point imprecision (misof's article on this topic is going to become a classic among TopCoder members).

The simplest way of solving this problem is to directly follow the instructions

``` double h = sqrt(sqr((double)diagonal) / (sqr(((double)width) / height) + 1));
double w = sqrt(sqr((double)diagonal) / (sqr(((double)height) / width) + 1));
vector ans(2);
ans[0] = h;
ans[1] = w;
return ans;
```
and round both h and w down to the nearest integer. Unfortunately for lots of our coders, this approach is wrong. Even a small imprecision can be fatal for your solution - value of h equal, for example, to 2.99999 instead of 3 will be rounded down to 2 and cause your solution to fail.

Fortunately, this problem can be solved without using any floating point numbers at all. The problem asks us to find the biggest integer number h such that

``` h <= (diagonal * height / hypoth), where hypoth = sqrt(height2 + width2).
```
Squaring this formula we can get the following one:
``` h * h <= (diagonal * height)2 / (height2 + width2),
```
or, in other words,
``` (height2 + width2) * h * h <= (diagonal * height)2,
```
Having this formula, we can easily find h (don't forget to use long variables to avoid integer overflow):
``` for (long i = 0; ; i++)
if ((height * height + width * width) * i * i > (diagonal * height * diagonal * height)
return i - 1;
```

SuperSort
Used as: Level Two:
 Value 500 Submission Rate 58 / 80 (72.50%) Success Rate 40 / 58 (68.97%) High Score Weiqi for 484.66 points (5 mins 5 secs) Average Score 385.99 (for 40 correct submissions)

This problem was fairly simple. Given a string of words, spaces and punctuation, sort the words while preserving the spaces and punctuation. In pseudocode, all one needs to do is locate each word, extract it and replace it with a place holder. Store each word in a container and sort it; both C++ and Java provide mechanisms for sorting so you shouldn't have to write your own sort algorithm. With this sorted list of words, iterate across the original string (with the place holders) and build a new string. If the current position of the original string has a place holder add the next sorted word, otherwise, add the current character to the return string. My solution is show below.

```public String wordSort(String sentence)
{
int           characterIndex = 0;
int           wordIndex      = 0;
List  words          = new ArrayList ();
String        parsedSentence = "";
String        returnCode     = "";
String        word           = "";

for (characterIndex = 0; characterIndex < sentence.length();
characterIndex++)
{
if ((sentence.charAt(characterIndex) >= 'a' &&
sentence.charAt(characterIndex) <= 'z') ||
(sentence.charAt(characterIndex) >= 'A' &&
sentence.charAt(characterIndex) <= 'Z'))
{
if (word.length() <= 0)
{
parsedSentence += 'P';
}
word += sentence.charAt(characterIndex);
}
else
{
if (word.length() > 0)
{
word = "";
}
parsedSentence += sentence.charAt(characterIndex);
}
}

if (word.length() > 0)
{
word = "";
}

Collections.sort(words);

for (characterIndex = 0; characterIndex < parsedSentence.length();
characterIndex++)
{
if (parsedSentence.charAt(characterIndex) == 'P')
{
returnCode += words.get(wordIndex++);
}
else
{
returnCode += parsedSentence.charAt(characterIndex);
}
}

return returnCode;
}
```

Used as: Level Three:
 Value 1000 Submission Rate 25 / 80 (31.25%) Success Rate 8 / 25 (32.00%) High Score Burunduk2 for 883.10 points (10 mins 37 secs) Average Score 582.13 (for 8 correct submissions)

The problem asked for the fewest keystrokes required to navigate from the starting position in the given source to the ending position. This is a classical example of a Breadth First Search (BFS). I solved this problem using a 50 by 50 array of int with each position holding the minimal keystrokes possible to get to that point. As a detail of implementation, we can make all strings of the text to be of the same length. This makes coding and checking for boundaries a bit easier. To start the BFS, we need to initialize our time array. We set the time for the starting position to 0 (because we can get it in 0 steps) and all other positions to an impossibly high value like 1000000. Also, we add the starting position to a queue. The program continues working until the queue is empty trying each of the possible 10 moves at the current position, adding new positions when performing the move causes the table to be updated with a new minimum. Finally, one returns the entry in the table indexed by the ending position. Java implementation follows:

```    Queue q;
int N;
int[][] memo;
// If time t is the best time for position
// (n1, n2) - add position (n1, n2) to the queue
void add(int n1, int n2, int t) {
if (n1 < 0 || n2 < 0 || n1 >= N || n2 >= 51 || memo[n1][n2] <= t)
return; // position is out of the text or time t isn't the best time.
memo[n1][n2] = t;
q.offer(n1);
q.offer(n2);
}
public int keystrokes(String[] source, int[] start, int[] finish) {
N = source.length;
// element (i, j) stores the best time we
// need to get to position (i, j) from the start
memo = new int[N][51];
for (int i = 0; i < N; i++)
while (source[i].length() < 51)
source[i] += " "; // make all strings of the same length
for (int i = 0; i < N; i++)
Arrays.fill(memo[i], 10000000);
while (q.size() > 0) {
int r = q.poll();
int c = q.poll();
int t = memo[r][c] + 1;
add(r - 1, c, t); // up
add(r + 1, c, t); // down
add(r, c - 1, t); // left
add(r, c + 1, t); // right
add(r, source[r].length() - 1, t); // end
add(N - 1, c, t); // bottom
for (int i = c; i < 50; i++)
if (!Character.isLetter(source[r].charAt(i)) &&
Character.isLetter(source[r].charAt(i + 1))) {
add(r, i + 1, t); // word right
break;
}
for (int i = c - 2; i >= 0; i--)
if (!Character.isLetter(source[r].charAt(i)) &&
Character.isLetter(source[r].charAt(i + 1))) {
add(r, i + 1, t); // word left
break;
}
}
return memo[finish[0]][finish[1]];
}
```
Despite the efforts of the problem statement, it wasn't clear to some people that one could view the columns as expanding from 0 (the leftmost column) to infinity (the rightmost column); although 50 columns was all you needed. Also, some people had a difficult time interpreting word left and word right.

By Uranium-235
TopCoder Member