344.md (10400B)
1 Source: https://codeforces.com/blog/entry/8860 2 3 #### [344A - Magnets](/contest/344/problem/A "Codeforces Round 200 (Div. 2)") 4 5 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. 6 7 Solution complexity: *O*(*n*). Problem author: [gen](/profile/gen "Candidate Master gen"). 8 9 **Bonus:** The problem was created a day before the contest and filled in the last part of a physically flavoured DivII complect. :] 10 11 #### [344B - Simple Molecules](/contest/344/problem/B "Codeforces Round 200 (Div. 2)") 12 13 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*. 14 15  16 17 Second solution. Bruteforce all *x* values. For a fixed *x* values of *y* and *z* are defined uniquely: *y* = *b* - *x*, *z* = *a* - *x*. 18 19 Solution complexity: *O*(1) / *O*(*n*). Problem authors: [gen](/profile/gen "Candidate Master gen"), [andreyv](/profile/andreyv "Expert andreyv"). 20 21 **Bonus:** Can you solve the problem for any vertex number *n*? When and how can such a graph be built? 22 23 #### [343A - Rational Resistance](/contest/343/problem/A "Codeforces Round 200 (Div. 1)") 24 25 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. 26 27 Solution complexity: . Problem authors: [gen](/profile/gen "Candidate Master gen"), [andreyv](/profile/andreyv "Expert andreyv"). 28 29 **Бонус:** 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](https://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree). 30 31 #### [343B - Alternating Current](/contest/343/problem/B "Codeforces Round 200 (Div. 1)") 32 33 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. 34 35 Solution complexity: *O*(*n*). Problem authors: [gen](/profile/gen "Candidate Master gen"), [andreyv](/profile/andreyv "Expert andreyv"). 36 37 **Bonus:** If you are interested by this problem, you can learn about the braid theory [http://en.wikipedia.org/wiki/Braid_theory](https://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. 38 39 #### [343C - Read Time](/contest/343/problem/C "Codeforces Round 200 (Div. 1)") 40 41 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: 42 43 1. go to the right  seconds, then  to the left and *h*[*i*] - *p*[0] again to the left; 44 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. 45 46 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. 47 48 Solution complexity: . Problem authors: [gen](/profile/gen "Candidate Master gen"), [gorbunov](/profile/gorbunov "Pupil gorbunov"). 49 50 **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](/profile/gorbunov "Pupil gorbunov") were listening this on a lecture, and created the given problem out of boredom ;] 51 52 #### [343D - Water Tree](/contest/343/problem/D "Codeforces Round 200 (Div. 1)") 53 54 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. 55 56 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: 57 58 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*. 59 2. Empty a vertex *v*. Color the vertex *v* in the segment tree. 60 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. 61 62 [Shtrix](/profile/Shtrix "Expert Shtrix") noted that essentially the same solution can be implemented with only a single set. 63 64 Solution complexity: . Problem author: [gen](/profile/gen "Candidate Master gen"). 65 66 **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. 67 68 #### [343E - Pumping Stations](/contest/343/problem/E "Codeforces Round 200 (Div. 1)") 69 70 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. 71 72 The problem can be solved with [Gomory-Hu](https://en.wikipedia.org/wiki/Gomory%E2%80%93Hu_tree) tree data structure. For a given weighted graph the tree has the following properties: 73 74 1. The vertex set of the tree and the graph is the same. 75 2. The maximum flow between vertices *u* and *v* in the tree is equal to the maximum flow in the graph. 76 77 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. 78 79 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. 80 81 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*2). 82 83 Solution complexity: *O*(*n*·*maxFlow*). Problem authors: [gen](/profile/gen "Candidate Master gen"), [Gerald](/profile/Gerald "Master Gerald"). 84 85 **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*2) times also passed. We hope that nobody is particularly saddened by this fact. (;