344A - Magnets

By the definition each block consists of a number of consequent and equally oriented dominoes. That means that in places where adjacent dominoes are not oriented equally, one block ends and another block starts. So, if there are x such places, the answer is equal to x + 1.

Solution complexity: O(n). Problem author: gen.

Bonus: The problem was created a day before the contest and filled in the last part of a physically flavoured DivII complect. :]

344B - Simple Molecules

First solution. First, the sum a + b + c should be even, since each bond adds 2 to the sum. Now let x, y, z be the number of bonds between 1st and 2nd, 2nd and 3rd, 3rd and 1st atoms, accordingly. So we have to solve the system x + z = a, y + x = b, z + y = c. Now observe that the solution to the system is the length of the tangents on the triangle with sides of length a, b, c to its inscribed circle, and are equal to , , . If the problem asked only the possibility of building such a molecule, we could just check if there exists (possibly degenerate) triangle with sides a, b, c.

Second solution. Bruteforce all x values. For a fixed x values of y and z are defined uniquely: y = b - x, z = a - x.

Solution complexity: O(1) / O(n). Problem authors: gen, andreyv.

Bonus: Can you solve the problem for any vertex number n? When and how can such a graph be built?

343A - Rational Resistance

If a fraction can be obtained with k resistors, then it is simple to calculate that we can obtain fractions and with k + 1 resistors. So adding one resistor means performing one operation backwards in Euclidean algorithm. That means that the answer is equal to the number of steps in standard Euclidean algorithm.

Solution complexity: . Problem authors: gen, andreyv.

Бонус: At first we thought about the major problem (any two elements can be joined), but had a moment of eureka and got that the given problem unexpectedly naturally can be reduced to GCD. By the way, the result tree — http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree.

343B - Alternating Current

Let us solve the following problem first: we are given a string of symbols A and B. If the i-th symbol is A, then at the i-th step the upper wire (see figure) is being put over the lower wire. If the i-th symbol is B, the lower wire is being put over the upper wire at i-th step. Observe that if some two symbols A and B are adjacent, we can untangle this place, throw the symbols out and obtain the string of length two symbols less. So the wires can be untangled iff the number of A's and B's in the string is the same. The given problem can be reduced to the described in a following fashion: in each odd position we change – to B and + to A. In each even position we change — to A and + to B. The reduction is correct, since on each even position the order of — and + are always swapped, and in each odd position their order is the same as in the beginning.

Solution complexity: O(n). Problem authors: gen, andreyv.

Bonus: If you are interested by this problem, you can learn about the braid theory http://en.wikipedia.org/wiki/Braid_theory :] Fun fact: a harder version of this problem was planned already for Round #142, but the error in solution idea was found, and the problem was left to lay for almost a year.

343C - Read Time

Let's search the answer t with the binary search. Fix some value of t. Look at the first head from the left h[i] that can read track p[0]. If p[0] > h[i], then h[i] goes to the right t seconds and reads all tracks on its way. Otherwise if p[0] ≤ h[i], then the head has two choices:

1. go to the right seconds, then to the left and h[i] - p[0] again to the left;
2. go to the left h[i] - p[0] seconds, then h[i] - p[0] to the right and t - 2·(h[i] - p[0]) again to the right.

Obviously, for h[i] it is more advantageous to visit the track positioned as much as possible to the right. So we choose by . Then we move the pointer onto the first unread track, and repeat the algorithm for h[i + 1], and so on with each head.

Solution complexity: . Problem authors: gen, gorbunov.

Bonus: The problem is completely real, if the disk has only a single head, if we know, what tracks should be read; then the optimal algorithm chooses between the two choices described above. I and gorbunov were listening this on a lecture, and created the given problem out of boredom ;]

343D - Water Tree

Let's learn how to color a whole subtree. For that enumerate all vertices in post-order DFS. Then each subtree covers a single continious vertex number segment. For each vertex we store the bounds of such segment for a subtree with a root in this vertex. Then to color a subtree means to color a segment in a segment tree.

Then create a segment tree that has a following property: if a vertex v was emptied, and is still empty, then this vertex is colored in the segment tree. In the beginning "empty" all the vertices. That is, color all the vertices in the segment tree. With this tree we can efficiently process the queries:

1. Fill a vertex v. Clean the interval for the subtree of v. If before that some vertex of a subtree was empty, color the parent of v.

2. Empty a vertex v. Color the vertex v in the segment tree.

3. Reply whether a vertex v is filled. If in the segment tree at least one vertex is colored, then there is such a descendant of v that is empty now, so the vertex v is not filled.

Shtrix noted that essentially the same solution can be implemented with only a single set.

Solution complexity: . Problem author: gen.

Bonus: Some participants could see the similarities with a problem Ball Machine from BOI 2013, but the solutions to the both problems are quite different.

343E - Pumping Stations

In this problem we are asked to find such graph vertex permutation that maximizes the sum of the maximum flows sent between each two consequtive vertices in the permutation.

The problem can be solved with Gomory-Hu tree data structure. For a given weighted graph the tree has the following properties:

1. The vertex set of the tree and the graph is the same.
2. The maximum flow between vertices u and v in the tree is equal to the maximum flow in the graph.

Surprisingly, such a tree exists for any weighted graph, and can be built in O(n·maxFlow). It appears that the answer to the problem is equal to the sum of the edge weights in this tree.

We prove this statement by induction on the number of the tree vertices. Pick the edge (u, v) with the smallest weight in the tree. Consider that in an optimal permutation more than one path between two adjacent verteces in the permutation passes through this edge. Erase all these paths, then each of the u and v subtrees holds a set of disjoint remaining paths from the permutation. For each set, join all the paths in one chain, obtaining two chains. These chains we join by a path s that goes trough the edge (u, v). Thus we have built a permutation that is not worse than the considered one. For a path s the edge (u, v) is the smallest, so the flow along this path is equal to the weight of this edge. It follows from the induction that in subtrees u and v the answer is equal to the sum of edges. By adding the weight of edge (u, v), we get the desired result.

From the last paragraph it is clear how to build such a permutation: take the smallest edge, obtain two chains from the vertex subtrees recursively, and add them together to form a one chain. Since there are not many vertices, we can do this part in O(n²).

Solution complexity: O(n·maxFlow). Problem authors: gen, Gerald.

Bonus: Shortly before the contest we decided to make the constraints more loyal, so some solution that find Gomory-Hu tree by finding flow O(n²) times also passed. We hope that nobody is particularly saddened by this fact. (;