Qualification Problem Set 4 January 1112, 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 ProblemsImageEnlargerUsed as: Division One  Level One:
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:
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 wordCountk 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 wordCountj 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 k1 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 k1 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. 
