Match Editorial

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

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;
    }

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)

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;
    }

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]),

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.

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.

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.