Match Editorial

Match summary

A healthy turnout of 1500 coders was faced with tough problemsets in both divisions. However, that was no obstacle for Petr to show impressive times on both medium and hard and to win Division 1 achieving the best-ever rating of 3799 (and with such high rating revealing a bug in the rating distribution application, as well :)).

In Division 1 coders were faced with a tricky easy which suggested a possibility of greedy approaches (many of which were incorrect), a somewhat involved geometrical medium and a not-so-straight-forward graph DP as a hard. The submissions of the medium and hard were scarcer than usual and only 11 coders submitted all 3 problems. However, only 8 of them survived the challenges and system tests with no losses. Another sixty-something had two problems standing in the end. The Top 3 was comprised solely of Russian coders: Petr won the match with two best times and a comfortable lead, andrewzta was the second thanks to two successful challenges which helped him score higher than Jedi_Knight, who was the third.

Division 2 coders found an Easy which required careful coding, a Medium which many of them found quite hard to figure out and a Hard which asked for some clever ideas. Noone managed to solve all three problems correctly. venkateshb seemed to win the match thanks to the best score on Hard, but his violation of the UCR took the victory away from his hands. bbi5291 was the author of the other 1000-pointer which survived the system tests, bringing him the victory, while Alex_KPR and ahmed_aly rounded out the Top 3 with quick submissions of the first two problems and the help of challenges.

The Problems

Value	250
Submission Rate	629 / 791 (79.52%)
Success Rate	569 / 629 (90.46%)
High Score	dinoj18 for 243.02 points (4 mins 50 secs)
Average Score	164.40 (for 569 correct submissions)

The problem was a simulation of a walk with some details not to be overlooked. The following code is self explanatory.

public int cellsVisited(String[] map, int heightDifference) {
    int X = 0, Y = 0, n = map.length, m = map[0].length(), ans = 0;
    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, -1, 0, 1};
    boolean[][] were = new boolean[50][50];
    for(int i = 0; i < n; i++) 
        for(int j = 0; j < m; j++) were[i][j] = false;
    boolean go = true;
    while(go == true) {
        ans++;
        were[X][Y] = true;
        go = false;
        for(int k = 0; k < 4; k++) {
            int nx = X + dx[k], ny = Y + dy[k];
            if(nx >= 0 && nx < n && ny >= 0 
                    && ny < m && were[nx][ny] == false) {
                int diff = map[nx].charAt(ny) - map[X].charAt(Y);
                if(diff < 0) diff = -diff;
                if(diff <= heightDifference) {
                    X = nx;
                    Y = ny;
                    go = true;
                    break;
                }
            }
        }
    }
    return ans;
}

Value	500
Submission Rate	233 / 791 (29.46%)
Success Rate	55 / 233 (23.61%)
High Score	Alex_KPR for 435.17 points (11 mins 18 secs)
Average Score	268.03 (for 55 correct submissions)

Value	250
Submission Rate	556 / 605 (91.90%)
Success Rate	411 / 556 (73.92%)
High Score	yuhch123 for 246.66 points (3 mins 18 secs)
Average Score	176.53 (for 411 correct submissions)

Counting the number of occurences of each letter in our original string we may reformulate the problem:

Given k natural numbers a₁, a₂, ..., a_k you can modify them by repeating the following procedure no more than n times: pick a number a_i > 0 and replace it by a_i - 1. Denote the resulting sequence of natural numbers (zeroes you throw out) b₁, b₂, ..., b_m. Find the minimal value of max b_i - min b_i you can obtain.

There are quite a few different approaches to this problem varying in "greediness" involved. Perhaps the simplest one is not greedy at all: just iterate through all possible values M = max b_i and m = min b_i and then iterate through all a_i's to see which ones have to be thrown out/reduced in order to make them fit in the interval [m, M]. For each such a_i one adds cost of its modification (which is a_i if a_i < m, a_i - M if a_i > M, and zero otherwise) and if the cumulative cost is less than or equal to n one checks if M - m is better than the current answer.

Consult yuhch123's code to see this approach in practice. You may also want to see kalinov's solution for a neat implementation of a somewhat different idea.

Value	1000
Submission Rate	29 / 791 (3.67%)
Success Rate	2 / 29 (6.90%)
High Score	bbi5291 for 538.73 points (32 mins 58 secs)
Average Score	369.36 (for 2 correct submissions)

The problem was quite easy if one noticed what should be done. The constraints were too high for a straight forward 'iterate over every m in the interval and compute the number of its cool divisors' approach since in the most naive form this would be O(b*a^1/2) which is circa 10,000,000,000. The last example suggested that one wouldn't get away with plain brute force. Some coders decided to try their luck anyway, exposing their solutions for easy challenges.

We solve using the usual gun - change the order of summation! Instead of summing over all m's in the interval we sum over all candidates to cool divisors k and count how many times a particular k is calculated in the sum d(a) + d(a + 1) + ... + d(a + b). But given k this is easy: it is equal to [(a + b)/k] - [(a - 1)/k] - ([(a + b)/kⁿ] - [(a - 1)/kⁿ]) for obvious reasons (here [x] is the integer part of x). If k is greater than a - 1 then in this way we count it as a divisor of itself once which requires some adjustments (the last if in the code) since cool divisors must be less than numbers themselves. With these observations the resulting code is really short:

public int P(int k, int n) {
    if(n == 1) return k;
    return k * P(k, n - 1);
}
    
public int analyzeInterval(int a, int b, int n) {
    int sum = 0;
    if(a == 1) {
        a++;
        b--;
    }
    for(int k = 2; k <= (a + b)/2; k++) sum += ((a + b)/k - (a - 1)/k);
    for(int k = 2; P(k, n) <= a + b; k++) sum -= ((a + b)/P(k, n) - (a - 1)/P(k, n));
    if(a <= (a + b)/2) sum -= ((a + b)/2 - a + 1);
    return sum;
}

Value	600
Submission Rate	77 / 605 (12.73%)
Success Rate	48 / 77 (62.34%)
High Score	Petr for 512.96 points (12 mins 8 secs)
Average Score	304.47 (for 48 correct submissions)

Geometry problems are certainly one of the most 'beloved' among contestants. CenetrsOfSymmetry was no exception: a fair amount of coders that openned it soon gained some confidence and decided to check out the Hard straight away. No, but seriously, the problem was not that hard, especially if one has some pre-written libraries for handling the most common geometrical operations. And if not, well, this was a chance to create some.

Note that if we have some intersection point of two given lines then after a symmetry with respect to some point it goes to an intersection point of two given lines (maybe to itself). Thus if there are intersection points then the only candidates to centers of symmetry that we are looking for are midpoints between pairs of (not necessarily distinct) intersection points of given lines. Moreover, since any intersection point behaves this way when treated with symmetry, while iterating through pairs of intersection points and checking their midpoints we may fix one of the points to optimize a bit. Calculating intersection points of pairs lines is a standard operation and checking if the symmetry of the given line is again a given line is easy: just check if the images under symmetry of the two given points on the line are collinear with some two points defining another (or possibly the same) line. Constraints were low enough so there was no need to worry about precise calculations of the coordinates of points and choosing any decent precision should have been enough.

Another case is when there are no intersection points, i.e., all the given lines are parallel. Now the answer is 0 or -1. It is not hard to see that the answer is -1 in this case if and only if the lines are "symmetrically spaced", i.e., the sequence d₁, d₂, ..., d_k of distances between adjacent lines possesses the property d_i = d_{k - i + 1}. This may seem exotic to check but it is not really hard. One may calculate the intersection coordinates of the given lines with one of the coordinate axes and, after ordering the obtained numbers, check if the sequence of differences between adjacent numbers possesses the aforementioned property (Thales' theorem suggests us that this is equivalent, though it is trivial anyway). Another way to do it is to convert all the lines into "normal form" (i.e., find the defining linear polynomials P_i(x, y) = a_i * x + b_i * y + c_i of the lines) and check if the "shiftings" (i.e., P_i(0, 0) = c_i) are "symmetrically spaced".

By the way, it is not hard to prove (exercise!) that the answer is always -1, 0 or 1, i.e., if there are at least two centers of symmetry then there are infinitely many of them. The idea of the proof is to show that if A and B are two distinct centers of symmetry then the image of A under symmetry centered at B is once again a center of symmetry. An interested reader is invited to work out the details.

Though it is difficult to read codes for geometry problems one may wish to look at the submissions of ACRush here or Burunduk1 here.

Value	900
Submission Rate	37 / 605 (6.12%)
Success Rate	27 / 37 (72.97%)
High Score	Petr for 846.64 points (7 mins 13 secs)
Average Score	497.35 (for 27 correct submissions)

First of all, it is not hard to see that the map of the roads of the kingdom is a tree. It is also quite evident that the problem begs for a DP solution. Let's find one!

Let's consider our original tree as a rooted tree with root 0. For each node x we wish to find an array dp[x][] such that the subtree rooted at x has probability dp[x][c] of having the most costly path from x to one of its leafs to have cost c, while not violating an assumption that the cost of any path in this subtree does not exceed savings. Indeed, this is what we want: if we know dp[0][] then the answer we must return is dp[0][0] + dp[0][1] + ... + dp[0][savings]. So how do we find such dp[x][]? Well, we iterate through all children y of x and compute dp[y][] first and then update the current version of dp[x][] which is initialised as {1, 0, ..., 0}. How does the updating work? Well, we know dp[x][] when we analyzed the first k children of x (initially k = 0) and we want to update to new_dp[x][] (latter we will assign dp[x][] := new_dp[x][]), where we also analyzed (k + 1)'st child y. How do we do that? Well, that's easy - just iterate through all costs b of an edge connecting x to y, and all costs a of the most costly path from y to one of its leaves, and all costs d of the cost of the most costly path connecting x to one of its leaves (where we analyzed only first k children) and add new_dp[x][max(d, b + a)] += p * dp[y][a] * dp[x][d] (new_dp[x][] is initialized as {0, 0, ..., 0}), where p = 1/(cost + 1) is the probability of an edge having cost b. Surely, this must work - we do not do anything fancy, plainly consider all possibilities of costs. But there are also some restrictions not to be overlooked. Namely, while iterating we skip those triples of (b, a, d) for which b + a + d > savings because we can not have paths of cost greater than savings in our subgraph rooted at x.

A real-quick implementation of this solution is Petr's code.