Second online round and its analysis were prepared by rng_58, snuke, snarknews and Gassa.

In the second round of “Yandex.Algorithm”, 495 participants have made at least one attempt, 425 of them have solved at least one problem. There were 503 attempts for problem A with 73 successful, 11 attempts for problem B with 2 successful, 472 attempts for problem C with 76 successful, 846 attempts for problem D with 386 successful, 42 attempts for problem E with 16 successful and 624 attempts for problem F with 182 successful.

The results of internal testing made us hope that the number of participants who solve 5 problems will be higher than in the first round, and that the winner will solve all 6 problems. But it turned out too optimistic. By the middle of the round two leaders appeared: tourist and eatmore who submitted all the problems “blind”. There also was a whole group of pursuers each of which solved no more than two problems “blind”. The first one to solve 5 problems was cgy4ever from China who had problem C submitted “blind”. On the 75th minute three more participants solved 5 problems: maciej.klimek (maciejk) from Poland, Jedi_Knight (ivan.popelyshev) and burunduk3. On the 77th minute tourist submitted his 5th problem and took first place with 5 problems “blind”, and also eatmore; submits “blind” problem B which was not solved by anybody else by then. Still, tourist stays in the first place. One minute before the end of the contest natalia submits problem E which becomes 5th for her and with four problems “blind” out of 5 takes 3rd place.

After the system tests it turned out that only tourist stayed in the top-3 thanks to all 5 “blind” submissions accepted. However, he had already passed into the finals from the first round, so the 5th place became a way to the finals. For eatmore, problem E which he submitted next to last — failed; for natalia, problem F which she also submitted next to last — failed. On the other hand, the last submitted problems — B which was solved only by two people (other than eatmore it was s-quark from China) for eatmore and E, submitted at 1:39, for natalia — passed the system tests.

In the end vepifanov took 2nd place, yeputons took 3rd place. They both submitted only problem D “blind” on the 5th minute. All the following participants submitted all problems “open”. Jedi_Knight (ivan.popelyshev) took the 4th place, and peter50216 from Taiwan took the 5th place and also got to the finals.

Problem A (Degree Sequence)

First, if the sum of d_i is not 2(N - 1), it can't be a degree sequence of a tree, so output “None”. Otherwise, it's easy to prove that it can be a degree sequence of some tree.

Let c be the number of i such that d[i] ≥ 2. There are several cases:

1. c = 0. In this case d = {1, 1}. Clearly, the answer is “Unique”.
2. c = 1. The tree must look like a star. The answer is “Unique” again.
3. c = 2. There are two vertices with degree  ≥ 2. Let us call them s and t. There must be an edge that connects s and t, and all other edges connect one of {s, t} and a leaf. Therefore, the answer is “Unique” again.
4. c = 3. There are three vertices with degree  ≥ 2. Let us call them s, t and u. Consider three pairs of vertices {s, t}, {t, u} and {u, s}. Exactly two of them must be connected by an edge (if all of them are connected by an edge, the edges form a cycle; if one or less are connected by an edge, we can't make the graph connected), so there are three ways to connect them. If the degrees of s, t, u are all the same, all of those three trees are isomorphic, so return “Unique”. Otherwise return “Multiple”.
5. c ≥ 4. If the degree sequence looks like {1, 1, 2, ..., 2}, the tree must be a chain, so return “Unique”. Otherwise we have at least one vertex with degree  ≥ 3. We can construct two non-isomorphic trees using this vertex: one possible way is to construct a chain with vertices with degree >= 2 and add leaves to it, the other is to construct three chains with one common vertex. In this case return “Multiple”.

Problem B (Frogs)

Let f(t) be the position of Frog k at time t. We are asked to compute minimal t such that t - f(t) ≥ d. Note that t - f(t) is a non-decreasing function because for any t, f(t + 1) - f(t) is 0 or 1. Since t - f(t) is monotonous, we can use binary search. The main part of the solution is computing f(t).

For simplicity let us assume that k = 2 (otherwise we can repeat a similar algorithm k - 1 times). Let us call n good if the sum of beauty between cell 1 and cell n is a multiple of m. It has period m(p - 1), i.e. n is good if and only if is good. For each n ≤ m(p - 1), precalculate whether n is good. It turns out that f(t) is (the number of good numbers between 1 and t), so we can calculate it quickly with precalculated table.

Problem C (Green Triangle)

We want to compute the sum of signed areas pqr of all clockwise triplets (p, q, r). If we fix points p and q, the signed area of pqr is a linear function of coordinates of r, so we just want to know the sum of x-coordinates (or y-coordinates) of all points in the halfplane.

Fix a point p. Sort other points by the angle from point p in clockwise order (let us call them p₀, ..., p_n - 2). Then we should use a two-pointer algorithm: we should keep two indices i and j. Here, j is the biggest index that satisfies the condition “three points p, p_i, p_j are clockwise in this order”. We increment i from 0 to n - 2 and change j properly. If we increment i, j never decreases, so the total number of changes of i and j is O(n). Overall the algorithm works in O(n^2 log n).

There are some problems with precision in this problem under the given limits on the coordinates: double precision is not enough in case of triangles with small area and large perimeter. This is especially troublesome for Java where there is no long double type and using BigInteger leads to Time Limit Exceeded.

One of the variants to cope with precision problems is to store the sum of areas of triangles with the same base both in double and in a 64-bit integer. In this case double will store the highest 52 bits of the result and 64-bit integer will store the lowest 64 bits.

Problem D (MathWorlds)

This is the easiest problem. You should check all operators, and count the number of operators that satisfy the equation “x [operator] y = z”. You should carefully consider the case when y = 0: for example, for y = 0 don't check the division operator at all. Solutions that transform division into multiplication don't work for test 0 0 1 which became a problem for a lot of participants.

Problem E (Small Cycltes)

The properties in the statement are equivalent to the following:

1. G has a spanning tree. Fix one spanning tree T, and let us call edges contained in T “tree edges”, and call other edges “non-tree edges”.
2. If e = {u, v} is a non-tree edge, the distance between u and v in T is exactly two.
3. For each non-tree edge e = {u, v}, color the path between u and v in T. No edge is colored more than once.

The original problem can be reduced to the following problem: You are given a tree, and some edges are already colored. In each operation, you must choose a path of length 2 and color it (you can't color an edge if the edge is already colored). How many operations can you perform?

This task can be solved greedily. See the tree as a rooted tree, and find the deepest uncolored edge e. If e is not adjacent to other uncolored edges, you can't color this edge, so ignore it. If e is adjacent to one of its sibling edges (let's call it e₂), you should color e and e₂ at the same time (otherwise you can't color both). If e is adjacent only to its parent edge, you should color e and its parent at the same time. After either e is colored or is ignored, find the deepest uncolored edge once again and repeat the process.

Problem F (Swap Balls)

If the answer of (p, q, r, s) is “Yes”, then the answer of (p + 2, q, r, s) is also “Yes”. This is because if you perform the same operation twice in a row, nothing changes. It is intuitive that if p is quite big, the answers to (p, q, r, s) and (p + 2, q, r, s) are the same. In fact we can prove that if p ≥ 48, this is true. With these observations, you can assume that p, q, and r are small, so we can use dynamic programming to solve the task (dp[p][q][r][s]: is it possible to change s to “RGB” using the operations p, q, r times respectively?).

Here is the formal proof. Construct a graph with 48 vertices. Each vertex corresponds to a tuple: (the parity of p, the parity of q, the parity of r, s). A sequence of operations corresponds to a path in this graph. If this path is very long, the path contains cycles. If the cycle contains p', q', and r' times of each operation, these numbers are even, and we can delete this cycle and prove that the answer of (p - p', q - q', r - r', s) is “Yes”. We can repeat this process until p, q and r satisfy  ≤ 48.

It turns out that 48 can be replaced with 3 (if you experiment using a computer).