Match Editorial

Match summary

Division 1 was presented with slightly unusual problem set, with technical 250, tricky 500 and relatively easy 1000 problems. After challenge phase, Petr was taking lead with impressively quick submissions on all problems and +175 points on challenge. But system tests have find flaw in his medium, which allowed Eryx to win his 10th SRM and became target again. He was third after 75 minutes of match, but intensive challenge phase (7 successful and 6 unsuccessful challenges, +200) gave him top position. Second was Egor, and inazz took third place. This SRM is also remarkable because of a new record – after it there are 12 active targets in TC rating, more than ever.

Division 2 problem set was uniformly harder than usual. Only 49 coders correctly solved 500, and only 3 solved 1000 problem. Newcomers araste and mhwu solved all problems and took first and second places. pszemsza_ took third with relatively quick submissions on first two problems. 1000 problem was also solved by newcomer YaoJinyu, but with incorrect 250 and 500 problems it brought him only fifth place.

The Problems

Value	250
Submission Rate	431 / 537 (80.26%)
Success Rate	267 / 431 (61.95%)
High Score	itsmemyself for 249.19 points (1 mins 37 secs)
Average Score	161.88 (for 267 correct submissions)

Because of small constraints, the problem was pretty straightforward. To solve it you should process all contiguous subsequences of length K and more, calculate their average values and lengths and select the best one, as pointed out in the statement. The only thing we need to care about is precision. We can use epsilon, when comparing floating-point numbers, or even calculate average values as common fractions to avoid floating-point arithmetic at all. The following code demonstrates such approach.

public int[] findMaxAverage(int[] a, int K){
    int bestp = -1, bestq = 1;
    int ret[] = new int[2];
    int acc[] = new int[a.length+1];
    for(int i = 0; i < a.length; ++i)
        acc[i+1] = acc[i] + a[i];
    for(int i = 0; i < a.length; ++i){
        for(int j = i; j < a.length; ++j){
            if(j - i + 1 < K) continue;
            if(bestq * (acc[j+1] - acc[i]) > bestp*(j-i+1)){
                bestp = acc[j+1] - acc[i];
                bestq = j-i+1;
                ret[0] = i;
                ret[1] = j;
            }
            else if(bestq * (acc[j+1] - acc[i]) == bestp*(j-i+1)){
                if(j-i > ret[1]-ret[0]){
                    ret[0] = i;
                    ret[1] = j;
                }
            }
        }
    }
    return ret;
}

Value	500
Submission Rate	86 / 537 (16.01%)
Success Rate	49 / 86 (56.98%)
High Score	araste for 374.44 points (17 mins 44 secs)
Average Score	250.14 (for 49 correct submissions)

Value	250
Submission Rate	358 / 438 (81.74%)
Success Rate	258 / 358 (72.07%)
High Score	Triple_M for 234.37 points (7 mins 26 secs)
Average Score	161.07 (for 258 correct submissions)

First, we can notice, that distance in K-rider moves between two cells can be easily expressed in terms of knight (1-rider) moves: distance(K, from, to) = ceil(distance(1, from, to)/K). This leads to the following solution: first, calculate distance in knight moves between every pair of cells; second, search over all possible "collection points", calculate total time for each of them and select the optimal point to collect all riders. We can implement BFS, Floyd-Warshall or even flood-fill for the first part of solution, due to small constraints. You can see some clear solutions demonstrating different approaches here and here.

Value	1000
Submission Rate	15 / 537 (2.79%)
Success Rate	3 / 15 (20.00%)
High Score	mhwu for 573.25 points (29 mins 38 secs)
Average Score	562.83 (for 3 correct submissions)

This problem is the easy version of Division 1 Hard, so it also can be solved in optimal O(K²) way. Here we describe non-optimal, but possible O(K³) solution, which will pass because of small constraints. Let's denote S1 and S2 sets of numbers containing only good digits and satisfying first or second conditions, correspondingly. By inclusion-exclusion principle, the answer is |S1|+|S2|-|S1 ∩ S2|. We find out these values, using the following DP: calculate N(k,i,j) -the amount of k-digit numbers composed only from good digits, with sum of digits equal to i, and difference between digits in odd and even positions equal to j. Thus, we can find |S1| (and |S2|) as sum[N(K,i,j1)*N(K,i,j2) over all i,j1,j2], and |S1 ∩ S2| as sum[N(K,i,j)*N(K,i,-j) over all i,j]. It seems that nobody from Division 2 have correctly implemented this approach during the competition.

Value	500
Submission Rate	270 / 438 (61.64%)
Success Rate	65 / 270 (24.07%)
High Score	Eryx for 471.31 points (7 mins 5 secs)
Average Score	301.70 (for 65 correct submissions)

First thing we can notice is small number of points and integer values of angles. So we can try all possible rotation angles (no more than 360), and solve corresponding subproblem for each. Imagine that rotation is fixed. Some point will overlap other points after rotation. Imagine graph, whose vertices are points on original circle, and arcs goes from first point to second one if and only if the first point overlaps the second after rotation. Our task is to color two different subsets of vertices in red and blue in such way that each blue vertex will have outgoing edge to some red point, each red vertex will have incoming edge from some blue point, and the total size of subsets is maximized. This task seems to be hard in general case, but it's easy to notice that in our problem graph will contain only non-intersecting chains and/or cycles. So, the answer is sum of 2*floor(V(C)/2), where V(C) is the number of vertices in connected component C of corresponding (here undirected) graph, over all connected components. There are different ways to calculate this, see Eryx solution for an example of fastimplementation.

Value	1000
Submission Rate	44 / 438 (10.05%)
Success Rate	32 / 44 (72.73%)
High Score	Egor for 837.58 points (13 mins 2 secs)
Average Score	590.41 (for 32 correct submissions)

As it was mentioned in CharmingTicketsEasy analysis, our task can be solved by finding |S1| and |S1 ∩ S2|. First of all, we can find |S1| by the following standard DP: calculate numbers N(k,i) - amount of k-digit numbers composed only from good digits, with sum of digits equal to i. Then |S1| can be found as sum[N(K,i)*N(K,i) over all i]. Denote this function from K as Lucky(K), it will come into play further.

Let's find |S1 ∩ S2|. Write out necessary and sufficient condition on digits for number from S1 ∩ S2:

x[1] + x[2] + ... + x[k] - x[k+1] - x[k+2] - ... - x[2*k] = 0  (1)
x[1] - x[2] + ... - x[k] + x[k+1] - x[k+2] + ... - x[2*k] = 0  (2)
x[i] is good digit for all i

x[1] + x[3] + ... + x[k-1] - x[k+2] - ... - x[2*k]   = 0  (1*)
x[2] + x[4] + ... + x[k]   - x[k+1] - ... - x[2*k-1] = 0  (2*)
x[i] is good digit for all i

First equation will have 2*ceil(K/2) variables, second – 2*floor(K/2) variables, and each variable is present in only one equation. Solutions of (1*) and (2*) are independent. Thus the number of solutions of this system equals to (number of solutions of (1*))*(number of solutions of (2*)). It's easy to see, that both equations are like the first condition from the statement, so it will be Lucky(ceil(K/2))*Lucky(floor(K/2)). The final answer will be 2*Lucky(K) – Lucky(ceil(K/2))*Lucky(floor(K/2)) (of course, all calculations are made modulo 999983). See Petr's solution demonstrating this approach.