JOIN
 Match Editorial
SRM 308
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 Problems

MedianOfNumbers
Used as: Division Two - Level One:
 Value 250 Submission Rate 371 / 386 (96.11%) Success Rate 361 / 371 (97.30%) High Score vlad_D for 249.40 points (1 mins 24 secs) Average Score 227.92 (for 361 correct submissions)

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:
 Value 450 Submission Rate 336 / 386 (87.05%) Success Rate 324 / 336 (96.43%) High Score Dottik for 444.87 points (3 mins 3 secs) Average Score 337.47 (for 324 correct submissions)
Used as: Division One - Level One:
 Value 200 Submission Rate 312 / 319 (97.81%) Success Rate 311 / 312 (99.68%) High Score gevak for 199.24 points (1 mins 45 secs) Average Score 183.99 (for 311 correct submissions)

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:
 Value 1000 Submission Rate 109 / 386 (28.24%) Success Rate 10 / 109 (9.17%) High Score vlad_D for 580.00 points (29 mins 3 secs) Average Score 479.49 (for 10 correct submissions)

This problem is a combination of two well-known 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 i-th 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 non-divisible treasures correspondingly. If W1 is the weight of the non-divisible 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.

CornersGame
Used as: Division One - Level Two:
 Value 500 Submission Rate 154 / 319 (48.28%) Success Rate 143 / 154 (92.86%) High Score rem for 429.15 points (11 mins 57 secs) Average Score 258.63 (for 143 correct submissions)

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 Breadth-first search algorithm.

You can look Petr's solution as a refernce.

Wardrobe
Used as: Division One - Level Three:
 Value 1000 Submission Rate 59 / 319 (18.50%) Success Rate 1 / 59 (1.69%) High Score bmerry for 440.77 points (47 mins 16 secs) Average Score 440.77 (for 1 correct submission)

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:

• dp + dn != 3, since otherwise corresponding bolts and holes can be connected
• p1+n2 <= A[s + 1]
• p2+n1 <= A[s + 1]
• if dn == 0, p1+n2 == p2+n1
• if dn == 1, p1+n2 >= p2+n1
• if dn == 2, p1+n2 <= p2+n1

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:

• if dn == 0, DN = DP
• if dn == 1, DN = DP + (p1+n2) - (p2+n1)
• if dn == 2, DN = DP + (p2+n1) - (p1+n2)

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.

By Andrew_Lazarev
TopCoder Member