On Saturday, September 19, the final round of the RCC 2015 took place. The winner and owner of the main prize of 300,000 rubles was Peter Mitrichev, who had already won the RCC cup twice: in 2011 and 2013. The second place and the prize of 150,000 rubles was received by the winner of the last year’s RCC - Gennady Korotkevich. The third place, as last year, was taken by Egor Kulikov. His prize was 90,000 rubles. Also prizes of 30,000 rubles each were received by participants who took the 4th to the 10th places - Pavel Marin, Vladislav Epifanov, Sergey Kopeliovich, Yury Pisarchik, Konstantin Semenov, Mikhail Tikhomirov and Nikolai Kalinin.

Heroes of the round:
')

• The first in 6 minutes and 8 seconds to solve the problem A (Ribbon bending) Gennady Korotkevich (tourist), he was the first to do it in 45 minutes and 29 seconds to cope with the task D (Right garden).
• The finalist from Japan, Kawai Ryuta (anta), was the first to solve Problem B (Collect Coins) in 16 minutes and 20 seconds.
• Petr Mitrichev (Petr) was the first to solve Problem C (Topological sorting and children) - in 45 minutes and 29 seconds.
• Task F (Robot on the tree) could not solve any of the finalists.

As we said , this year the final was held in a format unique to the IT Championship: it was accompanied by a four-hour online show that was broadcast on our website. The event was broadcasted live by the popular Russian showman Anton Komolov (a graduate of the Moscow State Technical University named after Bauman) and the head of the Center for Olympiad Training of Programmers of the Saratov State University Mikhail Mirzayanov. Nikolai Nikiforov, Minister of Communications and Mass Communications of the Russian Federation, representatives of leading IT companies and key industry experts, became guests of the studio. Recorded broadcast can be viewed at https://it.mail.ru/rcc/ .

And now we proceed to the analysis of tasks.

Problem A. Ribbon bending

Idea: Vladimir Smykalov
Implementation: Dmitry Filippov
Analysis: Dmitry Filippov

In the task, a 1 × 2 ⁿ strip is given, which was first folded n in half exactly in half, and then turned back. Folding is possible in two ways: the left half to impose on the right or the right half to impose on the left. It is required to respond to requests: by the number of the fold, find out whether it is oriented up or down.

Let's learn how to respond to a request for O (log 2 ⁿ ), that is, for O ( n ). The total number of requests does not exceed 10 ⁵ , so this is quite enough. We will emulate the bending process for each request. Knowing the current length of the ribbon and the number of the fold, it is easy to understand in which half this number is located, and then, knowing which way the fold will be folded in half, you can find a new fold position in the shortened ribbon. To respond to a request at the same time as the position, we support which way the fold is now oriented. So, we get the solution in O ( qn ), where q is the total number of queries.

Problem B. Collecting coins

Idea: Vitaly Aksenov
Realization: Boris Minaev
Analysis: Boris Minaev

The task is given a tape, divided into cells, on which the player walks. Every second in each cell additionally appears a certain number of coins, fixed for each cell. The player for a second can go to the next cell or stay in the current one. Every time a player is in a certain cell, he collects all the coins that are in it. It is necessary to calculate the maximum number of coins a player can collect in t seconds.

Note that for each cell it is important to know only the last moment when the player was in it. Consider the player's path from the end. At each moment of time, the last moment of their visit is already known about some continuous segment of cells, but not for the remaining cells. Therefore, you can use the dynamic programming method, the state of which is the segment of visited cells and the current time. In addition, you must keep the current position of the player. Note that you can only store positions when a player is standing at one of the ends of a segment of visited cells. From each state there are no more than two transitions: the player can visit the cell to the left or to the right of those already visited. Thus, the running time of the algorithm is O ( n ² t ).

Problem C. Topological sorting and children

Idea: Artem Vasilyev
Realization: Vitaly Aksyonov
Analysis: Vitaly Aksyonov

The task is given a graph and its topological sorting, some elements of which have been erased. It is necessary to correctly restore it topological sorting.

We first consider the algorithm, and then prove its correctness. Vertices for which the order is given will be called marked, the rest unmarked. We know which numbers were not used in the topological sorting, we will put them one by one from large to smaller to correspond to the vertices. We have another unplotted number. First of all we will delete all already marked drains. Further, for each unlabelled drain, we find out the maximum value in the labeled vertex, which is reachable from the back edges. For each vertex, this number can be pre-calculated: we find some topological graph sorting and solve the dynamic programming problem. As the corresponding vertex of the un spaced number, we choose any drain that has the highest calculated number, and remove it from the graph.

The number count is performed in O ( V + E ). Each iteration needs to be performed as quickly as possible, so at each vertex we store the number of outgoing edges leaving it. When we remove a drain, all the vertices from which there is an edge in it decrease the outgoing degree, and if this degree becomes zero, we place this vertex in the set by the calculated value. Thereby, all drains are stored in our set, and in order to select the one we need, we only need to take the latest vertex from the set. Each vertex is put into a set and pulled out exactly once. Total running time of the algorithm: O ( V · log ( V ) + E ).

Now we prove the correctness of our algorithm. Note that it is enough for us to prove the correctness of the first step of the algorithm, then we use the method of mathematical induction. Consider the correctly filled topological sorting p , having previously thrown out all the marked drains. Next, we consider the sink s , which we have chosen by our algorithm for the maximum number, and the drain to which it corresponds in the topological sort p . If we reduce all the numbers in the permutation large p (s) by one, and select the maximum number for the selected sink s , the permutation will remain correct. The operation occurred correctly: we retained the topological sorting property for unlabeled vertices, and for marked vertices, the topological sorting value did not change, because by the property of selecting the vertex sp (s) is greater than the topological sorting value of any labeled vertex.

Problem D. Proper garden

Idea: Artem Vasilyev
Realization: Artem Vasilyev
Analysis: Artem Vasilyev

In this problem, a set of points on the plane is given and the concept of a good set of points is introduced. A good set of points is such a set of points that any non-degenerate rectangle with sides parallel to the axes of coordinates and with opposite corners at given points contains at least one other point from this set inside or on the border. It is required to check whether a given set of points has such a property.

To begin with, we prove an equivalent property: a set of points is good if and only if for each corner of such a rectangle there exists a point on the side adjacent to this angle. Obviously, if this property is satisfied, then the property described in the statement of the problem is also satisfied. However, the corollary in the opposite direction is also true: consider an arbitrary rectangle with corners at points A and B. By assumption, inside or on the border of this rectangle there is another point from the set, let's call it C. If this point already lies on the side adjacent to A , then our statement is true. Otherwise, consider a rectangle built on points A and C. Its area is strictly smaller than the area of ​​the original rectangle, and there are a finite number of points in the set, then someday we will choose a point lying on the side adjacent to A.

The formulated property helps to reach the solution: for a point ( x _i , y _i ) we denote for left _i such a maximal x <x _i , that in a given set there exists a point ( x, y _i ). In the case when this value is not defined, we consider it equal to minus infinity. Similarly, we introduce the values right _i , down _i and up _i . Consider the region ( left _i , right _i ) × ( down _i , up _i ). If in this area there is another point from the given set, then you can find two points for which the constructed rectangle violates the property. It is worth noting that not every point from this area is suitable. For example, the closest one in the Euclidean or Manhattan distance is always suitable as a second point. When there is only a point ( x _i , y _i ) in this area, all the rectangles contain another point on the side adjacent to it. Thus, the solution was reduced to checking n rectangles for the presence of more than one point inside.

This check can be implemented using any data structure that allows counting the number of points in a rectangle on a plane: a two-dimensional segment tree (online solution) or an offline solution with a scanning line and a one-dimensional segment tree. Such a solution can be implemented in O ( n log ( n )).

Problem E. Interfluve

Idea: Vitaly Aksyonov
Realization: Ilya Zban
Analysis: Ilya Zban

In the problem, n disjoint monotone broken lines and a convex polygon are given. You need to find out what minimum number of times you need to attach a polygon so that each polyline has at least one common point with one of the attached polygons (on the border or inside the polygon).

Note that since the polygon is convex and the broken lines are monotone and do not intersect, the following fact is true: if the polygon intersects the broken lines i, k, then for any j that i ≤ j ≤ k , this polygon will intersect the j -th broken line. Using this fact, we will solve the problem eagerly: find the maximum i ₁ , such that there exists a polygon intersecting all broken lines from 1st to i ₁ , add it to the answer, and continue: we find the maximum i ₂ such that there exists a polygon covering the broken lines with i ₁ + 1 st through i ₂ , and so on. The number of polygons that had to be used will be the answer.

Let's learn to find i _{k + 1} for broken i _k . This is the maximum index such that there exists a polygon covering the i _k + 1-st and i _{k + 1} -nd polyline. We first solve a simpler problem: there is a point A and a segment BC, we need to check whether there exists a polygon containing both a given point and some points of the segment inside itself. To do this, we construct the Minkowski sum of this polygon and its own, inverted with respect to (0, 0) (that is, with coordinates of all points of opposite signs). This is some kind of new polygon, let's call it P, with O ( n ) vertices containing inside the point (0, 0). Shift it so that the point (0, 0) goes to point A, and check that segment BC intersects with a shifted polygon P - it is easy to verify that this is a necessary and sufficient condition.

Having learned to check whether there exists a polygon intersecting a point and a segment, it’s quite easy to check the same for two polygonal lines: we iterate over a segment on one polyline, build its Minkowski sum with polygon P and check if the new convex polygon intersects with any segment of the second polyline .

Let k be the total number of vertices on all broken lines. Let us find the asymptotics of the operations we use - O ( n ) to construct the polygon P, O ( n ) to construct the Minkowski sum of P and the line segment and O (log n ) to check the intersection of the convex polygon and the segment. Since polygons need to build a maximum of k , and in the worst case, you need to cross each polygon with each segment, the final asymptotic behavior of work is O ( nk + k ² log n ).

Problem F. Robot on the tree

Idea: Boris Minaev
Realization: Boris Minaev
Analysis: Boris Minaev

The problem is a non-oriented tree with n ≤ 10 vertices. Each edge is known for its strength wi , which does not exceed 15. A robot moves in a tree, which initially is located at a random vertex. Each time the robot equiprobably selects the edge from which it can pass, and moves along it. Each time a robot passes along an edge, its strength decreases by one. If the strength becomes zero, then the edge is removed. If the robot does not have any ribs that it can follow, it stops. It is necessary to calculate the expectation of the length of the path of the robot.

To begin with we will solve more simple task. Suppose that it is necessary to calculate not the expectation of the path length, but the number of different paths that the robot could go through. Imagine that we recorded vertices in which the robot began and ended its path, as well as the number of times that the robot went along each edge. Consider the limitations on these quantities. First, the edges along which the robot has passed a positive number of times must form a coherent subgraph of the source tree. Second, consider a certain vertex and the number of times that the robot went through all the edges that are adjacent to this vertex. If this vertex is the end of the path, then each adjacent edge must be used exactly wi times. A maximum of two edges adjacent to the vertex must be used an odd number of times. Moreover, if this vertex lies on the path from the starting to the final, then exactly two edges must be used an odd number of times. For the starting and ending vertices (if they do not coincide) there must be exactly one edge, which is used an odd number of times, or zero if the vertices coincide. For all other vertices, all adjacent edges must be used an even number of times.

If all these conditions are met, we will learn to count the number of paths that satisfy the condition of the problem and use edges a fixed number of times. For each vertex, we consider all the edges adjacent to it. We know the number of times that the robot went through each of them. We can easily calculate how many times the robot went along the edge in the direction from the given vertex. In what order could a robot pass along these ribs? First, the edge that lies on the way to the top, in which the robot finished the journey, the robot must pass last. On all other edges he can go in any order. Counting the number of such methods is a standard task. To calculate the total number of paths that a robot can go through, it is necessary to multiply the calculated values ​​for each vertex.

Note that to calculate the total number of paths, you can use the dynamic programming method. Let us calculate the number of paths that pass along a certain edge a given number of times and in some way pass along a subtree that is bounded by this edge. In this case, it is believed that every time the path goes up the edge, it immediately returns back along it. To calculate the value of dynamic programming, you need to fix the number of times that the robot went through each of the edges that go into the subtrees, multiply by the already calculated values ​​for the subtrees, as well as the number of ways to arrange the transitions into the subtrees. We will consider the subtrees of the vertex in turn and record the number of times the robot will go to all the considered subtrees. Considering the next subtree, let's look at the number of times the robot goes to this subtree. Multiply the response to the value of dynamic programming from the subtree, as well as the number of ways to arrange transitions to the subtree among other transitions.

Let's return to the initial task. Now, instead of the number of ways we will store the probability to choose such a path, as well as the expectation of its length. Counting probability differs from counting the number of ways only in that each time you go over an edge, you must divide the value by the number of edges that are incident to a given vertex. The only problem that arises with this is that the degree of the vertex is not constant, since the edges are removed during the travel of the robot. To calculate the dynamic programming values ​​for the edge, we use the following idea. We fix all subtrees, the edges to which will be deleted, as well as the total number of times that the robot will go from the top along some edge. We will restore the path from the end. There are two possible options that need to be distinguished. Either the robot goes along the edge, which will not be deleted, then you need to reduce the number of edges, which still need to go to the robot and go to a smaller task. Either the robot goes along the edge, which will be deleted, then to the total number of edges that the robot needs to go through, you need to add the number of times it passes along this edge, and also increase the number of existing incident edges by one.

In total, there are O (2 ^children ∑ wi ) states in dynamic programming for a given edge, and the transition between them is done in O (1). Since it is necessary to calculate the value of dynamic programming for each number of times in which the edge was used, the total running time of the algorithm is equal to O (2 ⁿ (∑ wi ) ² ).