JOIN
 Match Editorial
2005 TopCoder Collegiate Challenge
Qualification Problem Set 4

January 11-12, 2005

Summary

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

ImageEnlarger
Used as: Division One - Level One:
 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);
}
}
```

Justify
Used as: Division One - Level Three:
 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
}
```
This method will calculate the optimal placement for every j by first trying to place some words, starting at j, on a single line, and then placing the rest of the words on subsequent lines. The reason this words is because there is an optimal subproblem that you can solve. That is, once the first N words have been placed, the best way to place the remaining words is always the same, regardless of how you placed the first N words. The key to making the solution run within the 8 second time limit is to use memoization (the red code) so that you only compute the solution to the subproblem once for each N. If you were to omit the red code, you're solution would still return the correct answer, but the resulting runtime would not pass the constraints from the round 3 hard problem, as it would take over 1000 years for some inputs.

By lbackstrom
TopCoder Member