117.md (5139B)
1 Source: https://codeforces.com/blog/entry/2752 2 3 **[Problem A.](//codeforces.com/contest/117/problem/A)** 4 5 Consider three cases. 6 7 * *s* = *f*, *ans* = *t*. 8 * *s* < *f*, we must find the smallest non-negative *k* such, that *t* ≤ (*s* - 1) + 2(*m* - 1)*k*. *ans* = *s* - 1 + 2(*m* - 1)*k* + (*f* - *s*). 9 * *s* > *f*, similarly, we must find the smallest non-negative *k* such, that *t* ≤ 2(*m* - 1) - (*s* - 1) + 2(*m* - 1)*k*. *ans* = 2(*m* - 1) - (*s* - 1) + 2(*m* - 1)*k* + (*s* - *f*). 10 11 We can find *k* in any reasonable manner, for example, by using formulas of integer division. 12 13 **[Problem B.](//codeforces.com/contest/117/problem/B)** 14 15 Suppose, that the first player made a move *x* ≤ *a*, then consider the remainder *rem* = *x*· 109%*mod*. Obviously, if (*mod* - *rem*)%*mod* ≤ *b*, then the second player can win. Thus, we must iterate through all relevant values of *x* (we don't need iterate through more than *mod* values) and check whether the second player to win. If there exist a losing move for second player, then won the first, else second. Since we iterate through all relevant moves of the first player, then we can easily determine his winning move (if such move exist). 16 17 **[Problem С.](//codeforces.com/contest/117/problem/C)** 18 19 Approval. If the tournament has at least one cycle, then there exist a cycle of length three. 20 21 A constructive proof. Find any cycle in the tournament by using any standard algorithm, such as depth-first search. If there is no cycle, then output -1, else choose any three consecutive vertices of the cycle *v*1 *v*2 *v*3 (*A**v*1, *v*2 = *A**v*2, *v*3 = 1). Since given graph is a tournament, then there is an edge (*v*3, *v*1), or there is an edge (*v*1, *v*3). The first of these two cases, we find immediately the cycle of length three of the vertices *v*1 *v*2 *v*3, the second, we can reduce the length of the loop (erase vertex *v*2). 22 23 We can reduce the length of the cycle until we find a cycle of length three. 24 25 **[Problem D.](//codeforces.com/contest/117/problem/D)** 26 27 Imagine a recursion tree our transformation *F*. This tree is binary. We write on the edges leading into the left subtree, zero, and on the edges, leading to the right, one. Now consider the path of some number *a* (hereafter, we assume that we substracted one from all numbers in the array over which we make the conversion). This path start in the root of the tree and end in some leaf, and numbers written on the edges of the path is exactly bit representation of *a* in order from least significant bit to the most significant bit. 28 29 Construct the recursive function which solve our problem, similar to how we carry out a query to the segment tree. Here is the prototype of this function. 30 31 *solve*(*idx*, *tl*, *tr*, *l*, *r*, *u*, *v*) 32 33 This function returns the answer to the query (*l*, *r*, *u*, *v*), if we consider only subtree with positions [*tl*, *tr*], while on the path from the root to the subtree is written bit representation of *idx*. If *l* ≤ *tl* ≤ *tr* ≤ *r*, then we calculate answer by formulae, else we divide our segment of positions and return sum of answers from left and right part. 34 35 As described above, the answer to the whole subtree is a formula. Here you need to use the fact that all the numbers in the subtree have the form *k*· 2*depth* + *idx*, where *depth* - depth of subtree. We must find *k* such, that *u* ≤ *k*· 2*depth* + *idx* ≤ *v* and then calculate the sum of appropriate numbers. 36 37 Asymptotics of this solution *O*(*m*· *log*(*n*)· (*formulae* - *for* - *whole* - *subtree*)). We can calculate formulae for whole subtree in *O*(*logn*). 38 39 **[Problem E.](//codeforces.com/contest/117/problem/E)** 40 41 In this problem, suggested a solution using heavy light decomposition. Graph, given in problem statement, is a cycle, on which are suspended trees. For each tree construct the data structure (heavy light + segment tree), which can perform *change* on the path from some vertex to any parent, and to maintain the amount of ones. The same structure we use for the cycle. 42 43 Suppose, that we have no cycle, i.e. there is just a bunch of trees (forest). Then the amount of switched-on edges uniquely determines the number of connected components (each switched-on edge decrease the amount of components by one). 44 45 Suppose, that we have only the cycle. Then, similarly, the amount of switched-on edges uniquely determines the number of connected components. 46 47 We will maintain the amount of switched-on edges in the cycle and in the all trees. So, the answer to the problem *Comps**cicle* + *Comps**trees* - *Cnt**Cicle*, where *Comps**cicle* - the amount of connected components in cycle, *Comps**trees* - the amount of connected components in all trees, *Cnt**Cicle* - the amount of vertexes in cycle. 48 49 ([Google](https://www.google.com/search?aq=0&oq=Heavy+light+decom&gcx=w&sourceid=chrome&ie=UTF-8&q=heavy+light+decomposition)).