Match Editorial

This set had the hardest hard problem, and only 12 competitors were able to solve both of them. Top among them was John Dethridge, scoring over 60 points more than second place mathijs. Luckily, the easy problem was straightforward, and almost everyone who submitted it got it correct.

The Problems

Value	250
Submission Rate	138 / 160 (86.25%)
Success Rate	123 / 138 (89.13%)
High Score	Ruberik for 248.21 points (1 mins 56 secs)
Average Score	204.27 (for 123 correct submissions)

Unlike last year's problem dealing with bitmaps, this one was relatively simple. Basically, you just need to make an array with factor times as many elements as the input, and then fill in the characters. If you notice that ret[i][j] == input[i/factor][j/factor], when using integer division, then the task of generating the output becomes particularly simple.

for (int i = 0; i < input.length*factor; i++)
    ret[i] = "";
    for (int j = 0; j < input[0].length(); j++){
        ret[i] += input[i/factor].charAt(j/factor);
    }
}

Value	1000
Submission Rate	51 / 160 (31.87%)
Success Rate	11 / 51 (21.57%)
High Score	John Dethridge for 741.01 points (14 mins 32 secs)
Average Score	511.02 (for 11 correct submissions)

This was probably the hardest problem of the qualification round. It requires the use of dynamic programming. The basic idea is that you want to figure out the optimal way to place the last wordCount-k words for all k. Once you know the optimal placement for all k > j+1, you can then calculate the optimal placement for j. Here is the basic algorithm in pseudocode:

    //Finds the optimal placement for the last wordCount-j words
    findOptimalPlacement(int j){
        if(cache contains j){
            return cache[j]
        }
        placement best = BAD_PLACEMENT;
        foreach (k > j+1 and k ≤ wordCount){
            //Within this loop, we will consider each 
            //placement starting with word j at the beginning 
            //of a line, by trying to put words j 
            //through k-1 on a single line, and then 
            //recursively calling findOptimalPlacement to get
            //the placement for the words starting at k.
            placement p = findOptimalPlacement(k)
            prepend a single line with words j through k-1 to p
            if(p is better than best){
                best = p
            }
        }
        cache[j] = best
        return best
    }