Tuesday, January 24, 2006 Match summary
Each of the problems presented to the competitors have at least two fundamentally different solutions and this may explain the high success rate even for the harder problems. The Division 1 winner is rem with the highest score for the hard problem. bmerry, wleite and andrewzta placed second to forth correspondingly. marek.cygan who was the first coder to submit a correct solution for the 1000th problem took fifth place.
The ProblemsBasketsWithApplesUsed as: Division Two  Level One:
The solution for this problem is straightforward. Obviously the discarded baskets should have smaller number of apples then the remaining. So we just need to sort the baskets and choose the best answer for all possible numbers of discarded baskets. Here is the sample solution: public int removeExcess(int[] apples) { Arrays.sort(apples); int ans = 0; for(int i=0; i<apples.length; i++) { ans = Math.max(ans, (apples.length  i) * apples[i]); } return ans; }SentenceSplitting Used as: Division Two  Level Two: Used as: Division One  Level One:
The easiest way to solve the problem is to try all possible values of the text width and choose the smallest value which satisfies the problem statement. For a given width of the text we can greedy add words to the current line, unless their total length exceeds the width. After that we put the line break and go to the next line. If the total number of lines will not exceed K + 1, the width considered satisfying the problem statement. The sample solution goes further: public int split(String sentence, int K) { String[] words = sentence.split(" "); for(int ln = 1; ln <= sentence.length(); ln++) { if (can(words, K, ln)) return ln; } return 1; } private boolean can(String[] words, int k, int ln) { int l = 1; for (String s : words) { if (l + 1 + s.length() > ln) { k; if (k < 0) return false; l = s.length(); if (l > ln) return false; } else { l += 1 + s.length(); } } return true; } A lot of coders used more complex dynamic programming algorithms, calculating for example the answer for all possible substrings and all allowable numbers of lines. OperationsArrangementUsed as: Division Two  Level Three:
If given sequences contains zero digit, all operators in the result string will be '*',
because the value of the expression will be minimal possible  zero
and '*' comes before '+' lexicographically. public String arrange(String sequence) { String ret = sequence.charAt(0)+""; if (sequence.indexOf("0")!=1) { for (int i = 1; i < sequence.length(); i++) ret += "*" + sequence.charAt(i); return ret; } int acc = sequence.charAt(0)'0'; for (int i = 1; i < sequence.length(); i++) { char c = sequence.charAt(i); if (acc*(c'0') > acc+(c'0')) { ret += "+"+c; acc = c'0'; } else { ret += "*"+c; acc *= c'0'; } } return ret; } Dynamic programming solution was also possible for this problem. RobotTestingUsed as: Division One  Level Two:
Let's put one robot to each cell, resulting N*N robots on the grid. We will calculate the number of commands all robots will do in total before stop. Obviously the answer will be equal to the calculated number of commands divided by the number of robots N*N. Each robot will do no more then 50000 moves, so we can calculate the number of "live" robots for each move by simulating the process. All "live" robots on each move will form a rectangle, which can be defined by coordinates of two opposite vertices. The total number of commands is equal to the sum of counts of "live" robots during all steps of simulation. Here is the sample C++ solution by BenjaminHummel: double estimateCommands(int N, string program) { long long sum = 0; int xmin = 0, xmax = 0, ymin = 0, ymax = 0; int x = 0, y = 0; int ps = program.size (); for (int i = 0; i < 50000; ++i) { xmin <?= x; xmax >?= x; ymin <?= y; ymax >?= y; int dx = xmax  xmin; int dy = ymax  ymin; if (dx >= N  dy >= N) break; sum += (N  dx) * (N  dy); switch (program[i % ps]) { case 'U': ++y; break; case 'D': y; break; case 'L': x; break; case 'R': ++x; break; } } return (double)sum / (N*N); }Distincter Used as: Division One  Level Three:
We will solve the problem using the dynamic programming. First step is to sort the numbers in ascending order. After sorting we can assume that performing operations will not change the order of the numbers. Let's define A(i, j, k) as a number of operations required to make k distinct numbers using first i elements so that ith element is not greater then j. To calculate A(i, j, k) we should choose best from two choices:
So the final formula is: A(i, j, k) = min(A(i, j1, k), A(i1, j1, k1) + abs(sequence[i]  j))
As a sample solution you can take the fastest coded solution by rem. 
