Match Editorial

Match summary

Coders from Russia dominated this round, occupying the top 3 spots in the final table. Rating favorite Petr easily won this round, followed by TCO07 finalists darnley and Vitaliy.

The Problems

Value	250
Submission Rate	465 / 510 (91.18%)
Success Rate	420 / 465 (90.32%)
High Score	misof for 248.57 points (2 mins 9 secs)
Average Score	196.33 (for 420 correct submissions)

In this problem we need to sort an array of Strings. To do that, we must

• compute the popularity of each of the names
• sort the array to arrange the popularities in non-increasing order
• make sure that our sorting method is stable (that it preserves the order of the names of the same popularity)

    public String[] sort(String[] data) {
        for (int i = 0; i < data.length; i++)
            for (int j = 0; j < data.length - 1; j++) {
                int a1 = 0;
                for (int k = 0; k < data.length; k++)
                    if (data[k].split(" ")[0].equals(data[j].split(" ")[0]))
                        a1++;
                for (int k = 0; k < data.length; k++)
                    if (data[k].split(" ")[0].equals(data[j + 1].split(" ")[0]))
                        a1--;
                if (a1 < 0) {
                    String v = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = v;
                }
            }
        return data;
    }

Value	500
Submission Rate	266 / 510 (52.16%)
Success Rate	176 / 266 (66.17%)
High Score	Soultaker for 424.32 points (12 mins 27 secs)
Average Score	277.53 (for 176 correct submissions)

This problem can be solved in a number of ways. For example, you can transform the input into a tree structure (storing a father and a couple of children for each of the nodes), swap the subtrees and return a String representation of the resulting tree. Since all these algorithms are classical, we'll explain another approach.

In fact, to return the representation of the tree after the swap we don't need to construct the tree itself. We will find two substrings of the input, which completely describe the subtrees rooted with root1 and root2 respectively. Then we'll check whether the substrings intersect (checking for an overlap), swap them in the string and return the result.

If the input string represents a valid tree, then for each index K you can find another index L such that the substring between indices L and K will represent a subtree rooted at the vertex at position K. We'll create an array (first in the code below) and the i-th element of this array will represent the first character of the subtree rooted at vertex number i. This value can be easily found in the following way:

• If the i-th character of the input is an uppercase letter, then first[i] = i.
• Otherwise, the (i-1)-th character represents the right child of the i-th vertex, string between first[i - 1]-th and (i-1)-th characters represents the string rooted at the (i-1)-th vertex, and string between first[first[i - 1] - 1]-th and (first[i - 1] - 1)-th characters represent the subtree rooted at the left child of the i-th vertex. Therefore, first[i] = first[first[i - 1] - 1].

    public String newTree(String tree, int r1, int r2) {
        if (r1 > r2) {
            int tmp = r1;
            r1 = r2;
            r2 = tmp;
        }
        int n = tree.length();
        int[] first = new int[n];
        for (int i = 0; i < n; i++) {
            if (tree.charAt(i) >= 'A' && tree.charAt(i) <= 'Z') {
                first[i] = i;
                continue;
            }
            if (i - 1 < 0) return "BADTREE";
            int j = first[i - 1] - 1;  //j is last in i's lc
            if (j < 0) return "BADTREE";
            first[i] = first[j];
        }
        if (first[n - 1] != 0) return "BADTREE";  //(fix)
        int f1 = first[r1], f2 = first[r2];
        if (f2 <= r1) return "OVERLAP";
        return tree.substring(0, f1) + tree.substring(f2, r2 + 1) +
                tree.substring(r1 + 1, f2) + tree.substring(f1, r1 + 1) + tree.substring(r2 + 1);
    }

Value	1000
Submission Rate	102 / 510 (20.00%)
Success Rate	21 / 102 (20.59%)
High Score	Petr for 864.90 points (11 mins 36 secs)
Average Score	644.16 (for 21 correct submissions)

The first thing to observe in this problem is that the orders of length k are special ones - first, we can get plenty of them as a side effect of others orders, and, second, we can cut at least one marble of length k out of any stock marble of length > k. Therefore it might be a good idea to fill other orders first.

Obviously, if we can use several marbles from the stock to get a marble of some length m, the best way is to use the shortest available marble. This gives us a very simple algorithm to check the availability for all orders (except for those of length k) - sort all stock marbles, iterate through all orders. For each order[i], find the shortest stock marble of size (order[i] + i * k) and remove this marble from the stock. Of course, if there is no such marble for at least one order, the method should return -1. Also, count how many marbles of length k you cut during the process.

Now we need to fulfill the orders for the marbles of length k. First, compute the number of marbles of length k you already have (those you had in stock plus those you might have gotten some while fulfilling other orders). If you already have enough marbles, the process is over. Otherwise, you need to cut more marbles of length k from longer ones. The last trick to note is that cutting marbles of length divisible by k is better than others, so you should cut marbles of lengths i * k first. The implementation of this algorithm should be pretty easy; see Petr's solution as an example.