Match Editorials

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

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;

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).

 h * h <= (diagonal * height)2 / (height2 + width2),

 (height2 + width2) * h * h <= (diagonal * height)2,

 for (long i = 0; ; i++) 
         if ((height * height + width * width) * i * i > (diagonal * height * diagonal * height) 
         return i - 1;

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)
            {
                words.add(word);
                word = "";
            }
            parsedSentence += sentence.charAt(characterIndex);
        }
    }

    if (word.length() > 0)
    {
        words.add(word);
        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;
}

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) {
        q = new LinkedList();
        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); 
        add(start[0], start[1], 0);
        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, 0, t); // home
            add(r, source[r].length() - 1, t); // end
            add(0, c, t); // top
            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]];
    }