Saturday, June 24, 2006 Match summary In both divisions, the first two problems were rather easy and standard, but the third caused some troubles. In Division 1 there was only one successful submission for the third problem done by bmerry who took the first place. Second and third went to warmingup and andrewzta. In division 2 there were a lot of submissions for the hard problem, but only ten of them were successful. The Division 2 winner is vlad_D, Piotrus and kupicekic are second and third. The ProblemsMedianOfNumbersUsed as: Division Two  Level One:
Clearly, the answer is 1 only if the number of elements in the array is even. Otherwise you just need to sort an array and return the middle element. Alternatively you could iterate through elements of the array and check for the median, using the definition of the median from the problem statement. Here is the sample solution: public int findMedian(int[] numbers) { Arrays.sort(numbers); return numbers.length % 2 != 0 ? numbers[numbers.length / 2] : 1; }HuffmanDecoding Used as: Division Two  Level Two: Used as: Division One  Level One:
The solution of the problem is pretty straightforward. You just need to iterate through the dictionary and find the prefix that the current string representing the archive starts with. After that cut the prefix and repeat the described operation until archive is empty. Here is the sample solution: public String decode(String archive, String[] dictionary) { String ans = ""; while (!archive.equals("")) { for (int i = 0; i < dictionary.length; i++) { if (archive.startsWith(dictionary[i])) { ans += (char) ('A' + i); archive = archive.substring(dictionary[i].length()); break; } } } return ans; }TreasuresPacking Used as: Division Two  Level Three:
This problem is a combination of two wellknown versions of the knapsack problem: discrete and continuous (fractional). The continuous problem on its own can be solved using greedy approach. You just need to sort all items by the ratio of the value and weight and get the most "precious" items with total weight not exceeding the limit. The discrete problem in case of integer weights can be solved using dynamic programming with time complexity O(maximal weight * number of items). Let A[i, w] be the maximal cost which is possible to get using first i items with total weight w. A[i, w] can be calculated using the following recurrence formula: A[i, w] = max(A[i  1, w], A[i  1, w  weight[i]] + cost[i]),i.e. we either do not use the ith item or use it, whatever leads to the greatest answer for the current weight. Now get back to the original problem. Let's find the solutions of continuous and discrete problems separately for each weight using only divisible and nondivisible treasures correspondingly. If W1 is the weight of the nondivisible treasures in the solution, W  W1 is the weight to be filled with divisible items. To find the solution for the problem you just need to iterate through the all possible values of W1 and choose the one leading to the best result. CornersGameUsed as: Division One  Level Two:
Let's build a graph, where vertex is the position of four draughts on the board. Two vertices are connected with an edge if there is an arbitrary move which translate state corresponding to the one vertex to the state corresponding to the other. This graph will have at most 58905 vertices (the number of ways to place draughts on the border) and 471240 edges (each vertex has at most 16 adjacent edges). The minimal number of moves necessary to reach the goal is equal to the length of the shortest path from the initial position to the target. This length can be easily found using the Breadthfirst search algorithm. You can look Petr's solution as a refernce. WardrobeUsed as: Division One  Level Three:
First, for each size let's calculate the number of bolts of this size A. We will process the bolts in the ascending order of their sizes. Let D[s, flag, p1, p2] be the maximum number of unused bolts and holes, if p1 bolts of the size s are connected with holes of the size s + 1, p2 holes of the size s are connected with the bolts of the size s + 1, bolts of size less than s are already balanced and flag is equal to 0, 1, or 2. flag is equal to 0 if there is no unused (in the terms of the problem) holes and bolts of the size s. flag is equal to 1 if there are some unused bolts of the size s and flag is equal to 2 if there are some unused holes of the size s. Clearly, state with both unused bolts and holes is forbidden, because we can connect them. Two states DP = D(s, dp, p1, p2) and DN = D(s + 1, dn, n1, n2) are called balanced if following rules are obeyed:
If two states DP and DN are balanced, and we already know the value of DP, the value of DN can be calculated using one of the following formulas:
Using the given formulas it is possible to calculate the answer with the help of dynamic programming. You can look at bmerry's solution which used similar (but not the same) ideas. 
