405A - Gravity Flip

Observe that in the final configuration the heights of the columns are in non-decreasing order. Also, the number of columns of each height remains the same. This means that the answer to the problem is the sorted sequence of the given column heights.

Solution complexity: O(n), since we can sort by counting.

405B - Domino Effect

If the first pushed domino from the left was pushed to the left at position l, all dominoes at prefix [1;l] fall down, otherwise let l be 0. Similarly, if the first pushed domino from the right was pushed to the right at position r, all dominoes at suffix [r;n] also fall down, otherwise let r be n + 1. Now, in the segment (l;r) there will remain vertical dominoes and blocks of dominoes supported by the equal forces from both sides.

When does a domino at position p in segment (l, r) remains standing vertically? One way is that it is not pushed by any other domino. This could be easily checked by looking at the pushed dominoes closest to p (from both sides). It is pushed by dominoes, only if the closest from the left was pushed to the right, and the closest from the right was pushed to the left. Suppose these dominoes are at positions x and y, x < p < y. Then, the only way that the domino is still standing is if it is positioned at the center of the block [x;y], which could be checked by .

Solution complexity: O(n) / O(n²), depends on implementation.

406A - Unusual Product

Written as a formula, the problem asks to find the value of

Suppose that i ≠ j. Then the sum contains summands A_ijA_ji and A_jiA_ij. Since the sum is taken modulo 2, these summands together give 0 to the sum. It follows that the expression is always equal to the sum of the diagonal bits:

Now, each query of type 1 and 2 flips the value of exactly one bit on the diagonal. Thus we can calculate the unusual product of the original matrix, and flip its value after each query of type 1 and 2.

Solution complexity: O(n + q), if we don't take the reading of the input into account... :)

406B - Toy Sum

Let's define the symmetric number of k to be s + 1 - k. Since in this case s is an even number, k ≠ s - k.

Note that (k - 1) + (s + 1 - k) = s, i.e., the sum of a number and its symmetric is always s. Let's process the given members x of X. There can be two cases:

1. If the symmetric of x does not belong to X, we add it to Y. Both give equal values to the respective sums: x - 1 = s - (s + 1 - x).
2. The symmetric of x belongs to X. Then we pick any y that neither y and symmetric of y belong to X, and add them to Y. Both pairs give equal values to the respective sums, namely s.

How to prove that in the second step we can always find such y? Let the number of symmetric pairs that were processed in the step 1 be a, then there remain other pairs. Among them, for pairs both members belong to X, and for other pairs none of the members belong to X. To be able to pick the same number of pairs for Y, as there are in X, we should have

which is equivalent to , as given in the statement.

Solution complexity: O(s) / O(n).

406C - Graph Cutting

It can be proved that only graphs with an odd number of edges cannot be partitioned into path of length 2. We will construct a recursive function that solves the problem and also serves as a proof for this statement.

The function partition(v) will operate on non-blocked edges. It will partition the component of vertex v connected by the non-blocked edges into paths of length 2. If this component has an odd number of edges, the function will partition all the edges of the component, except one edge (u, v); the function then will return vertex u, expecting that the parent function call will assign it to some path.

The function works as follows: find all vertices that are adjacent to v by the non-blocked edges, call this set adjacent. Then block all the edges from this set vertices to v. For each u in adjacent, call partition(u). Suppose partition(u) returned a vertex w. That means we can pair it into the path (v, u, w). Otherwise, if partition(u) does not return anything, we add u to unpaired, since the edge (v, u) is not yet in any path. We can pair any two vertices of this set u, w into a single path (u, v, w). We pair as much of them as possible in any order. If from this set a single vertex, u, is left unpaired, the function will return u. Otherwise the function will not return anything.

The function could be implemented as a single DFS:

partition(v) :
    adjacent = { u | not blocked[(u,v)] }
    for(u : adjacent)
        blocked[(u,v)] = true

    unpaired = {}
    for(u : adjacent)
        int w = partition(u)
        if(w = 0)
            add(unpaired, u)
        else
            print(v,u,w)

    while(size(unpaired) >= 2)
        int u = pop(unpaired)
        int w = pop(unpaired)
        print(u,v,w)

    if(not empty(unpaired))
        return pop(unpaired)
    else
        return 0

Solution complexity: O(n + m).

406D - Hill Climbing

Note that the path of each hill climber is strictly convex in any case. Let's draw the paths from all hills to the rightmost hill. Then these paths form a tree with the "root" at the top of the rightmost hill. We can apply the Graham scan from the right to the left to find the edges of this tree. Each pop and insert in the stack corresponds to a single edge in the tree.

Now it is easy to see that for each team of climbers, we should calculate the number of the lowest common ancestor for the corresponding two vertices in the tree. The size if the tree is n, so each query works in .

Solution complexity: .

406E - Hamming Triples

Let's look at the Hamming graph of all possible distinct 2n strings, where each two strings are connected by an edge with length equal to the Hamming distance between these strings. We can observe that this graph has a nice property: if we arrange the vertices cyclically as a regular 2n-gon with a side length of 1, then the Hamming distance between two strings is the length of the shortest route between these vertices on the perimeter of the polygon.

For example, the figure shows the graph for n = 3. The gray edges have length 1, the orange edges have length 2 and the blue edges have length 3. That is the corresponding Hamming distance.

Now, we can convert each string coded by a pair (s, f) to an integer (f + 1)·n - s. The new numbers will be 0, 1, ..., 2n - 1 and correspond to the same cyclical order on the perimeter of the polygon. The given strings are mapped to some subset of the vertices. Now we have to find the number of triangles (possibly degenerate) with maximal perimeter in this subgraph. It will be useful to keep the new converted numbers sorted.

First, we can figure out what this perimeter could be. If there exists a diameter in the full graph, so that all of the points are on one side of the diameter, the perimeter is 2d, where d is the length of the longest edge:

Then any triangle with two vertices at the longest edge points and the third one being any point has the maximal perimeter. Since the numbers are sorted, the longest edge in this case will be produced by two cyclically adjacent elements, which is not hard to find.

If for any diameter this does not hold, then the maximal perimeter is 2n. This can be proved by taking two different points a, b and drawing two diameters with them as endpoints; since it is not the previous case, there shoud be a third point c in area where the perimeter of triangle a, b, c is 2n.

The tricky part is to count the triples in this case. We do this by working with the diameter (0, n). There can be several cases:

1. A maximum triangle has vertices 0 and n. This a simple case: with any other vertex as the third the triangle has perimeter 2n.
2. A maximum triangle has vertex 0, but not n. Then the second vertex should be in interval [0, n), and the third in interval (n + 1, 2n - 1], and the clockwise distance between the second and the third should not exceed n (since then the perimeter of the triangle would be less than 2n). We count the number of such triples iterating two pointers (one in each of these intervals). For each pointer in the first interval, all points from n + 1 till the second pointer will make a maximal perimeter triangle. We similarly solve the case where the maximal triangle has vertex n, but not 0.
3. The maximal triangle does not have 0 or n as its vertices. Then one vertex of the triangle should be on one side of diameter (0, n), and two should be on the opposite side. To count them, we iterate a vertex pointer on the first side, say, (0, n); let the diametrally opposite vertex on the opposite side be x. Then the second vertex can be any in [n + 1, s], and the third can be any of the [s, 2n - 1]. It is easy to calculate these numbers using partial sums on the circle. Note that s can be both the second and the third vertex (since strings can repeat). So we iterate this pointer over all one side vertices and update the answer. Similarly we solve the case where a single vertex is on the other side, and two on this side.

One only needs to be careful with the formulas in each case.

Solution complexity: , because of the sorting.

Post Scriptum

What were your solutions? Feel free to share any solutions or thoughts! For example, was there a solution to DivI E simpler than in this tutorial?