331.md (4987B)
1 Source: https://codeforces.com/blog/entry/8397 2 3 Hello! 4 5 ABBYY Cup 3.0 is finished! Many thanks to everyone: participants, people who created and prepared problems and etc! The post about ABBYY Open Day will be later but now let's consider finals' solutions: 6 7 #### Problem A 8 9 Claim: If the walk starts from tree *i* and ends at tree *j*, then we need to cut down all trees before *i*, all trees after *j* and all trees with negative esthetic appeal between *i* and *j*. In order to solve subproblem A1 we could use the claim for each pair of trees with equal aesthetic appeal and choose the maximum; the constraints allowed to do this either at *O*(*n*2) or *O*(*n*3). In order to solve subproblem A2 we could use the following claim: whichever is the number of trees with equal esthetic appeal, we are always better off if we consider only a pair of the leftmost and rightmost of such trees. Then the number of the pairs of trees considered is reduced from *O*(*n*2) to *O*(*n*). Then we may proceed with either taking partial sums or calculating a sum on the interval. 10 11 #### Problem B 12 13 In order to solve subproblem B1 we may emulate the behavior of Beavershave as it is described in the problem. In order to solve subproblem B2 it is sufficient to store a raised unity-flag for each terminal beaver, where terminal beaver is such beaver *i* who does not have a beaver *i* + 1 on his right (that is, if we make a query which includes beavers *i* and *i* + 1, then we would have to run Beavershave one more time). If we swap beavers *i* and *j*, then we have four possible positions at which the status of the flag may change: *i* - 1, *i*, *j* - 1, *j*. A response to a query is then the number of the terminal beavers in the interval which is a classical problem. 14 15 #### Problem C 16 17 In order to solve subproblem C1 we could either calculate dynamics or subtract the largest number using greedy algorithm. It is easy to prove that it is always better to subtract the largest number. In subproblem C2 it is sufficient to calculate dynamics for the first million, divide (in head) the number into two groups of digits — low orders and high orders — and make not one subtraction, but a series of subtractions in order to instantly minimize low orders. In order to solve subproblem C3 it is necessary to store in dynamics parameters not the number itself, but only the number of digits. 18 19 #### Problem D 20 21 Obviously, the Beaveractor moving along the arrows will either get out or go round a cycle. If the latter is the case, we need to find the length of the cycle *l*, and then we need to find the remainder of dividing the time by the length of the cycle. Thus, we have solved this case. In order to solve subproblem D1 it is sufficient to emulate the behavior of the Beaveractor saving at each step the time of the visit of the current point (this way we will know the length of the cycle the moment we come to the point in the cycle from which we started). In order to solve subproblems D2 and D3 we need to construct a graph of Beaveractor's movements and then process each of the multiple tests. In D2 we may construct the graph in a straightforward way and find an answer to each test by going through the graph. In D3 we are supposed to use logarithmic data structures. The idea of the solution is, thus, clear. The problem is interesting from the technical point of view. 22 23 #### Problem E 24 25 In order to solve subproblem E1 we may use the following claim: If the edge *x* → *y* has marks *x* and *y* in succession, then such edge may generate the path of interest. Call such edge "initiating". It is easy to understand that the path in both directions is constructed unambiguously from the initiating edge. Now, it is sufficient to consider only initiating edges. Indeed, consider required path in a graph. It has *p* nodes and *p* - 1 edges. By pigeonhole principle at least one edge has two or more marks. Let some edge *x* → *y* have marks *a* *b*, (*a*, *b*) ≠ (*x*, *y*). Then cut this path in two by the edge *x* → *y* and note that one of the two subpaths has more marks than it has edges. Proceeding in a similar fashion we may come to the conclusion that there is at least one edge *x* → *y* with marks *x* and *y*. If there are no initiating edges, then the path of interest does not exist. The path which is generated by the initiating edge is the shortest valid path for a given initiating edge. We may add to this path incoming and outgoing tails in such a way that the path becomes longer. The tails should not contain initiating edges, because initiating edges generate their own paths. Any valid path is a path consisting of three parts (incoming tail, path of the initiating edge, outgoing tail) which are connected by edges without marks. In order to solve subproblem E2 we may count all tails and paths generated by initiating edges beforehand and then count the number of paths with a fixed length by dynamics.