On Sunday, June 14, the qualifying round of RCC 2015 was held. 604 programmers who had qualified in the previous three rounds fought for the title of RCC 2015 finalist. At least one correct decision was sent by 324 participants. And now the heroes of the round! Peter Mitrichev took the first line of the tournament table, first solving problems B (Split into teams) and F (Stage lighting) for 20:32 and 1:31:41. Gennady Korotkevich comes second - he was the first in 2 minutes and 30 seconds to solve task A (playing with strings) and was the first to cope with task D (Cartesian trees) in 14:16. Makoto Soejima from Japan is the third, apparently before the decision, he translated the conditions of the tasks through an online translator. Mikhail Pyaderkin first solved Problem C (Map) in 51 minutes and 4 seconds. Egor Kulikov was the first to solve problem E (Alley) in 1 hour 5 minutes and 49 seconds. According to the results of the qualifying round, 50 participants reached the final. September 19 in the Final will be determined the strongest programmer of the year! All participants in the qualifying round will receive online certificates, and the 200 best ones will receive RCC 2015 T-shirts.

Task A. Playing with strings

Idea: Gregory Shovkoplyas
Realization: Gregory Shovkoplyas
Analysis: Gregory Shovkoplyas

The task is given a string with which you can do the following operations:

• remove three consecutive units;
• remove two consecutive zeros;
• replace the substring " 01 " with the substring " 10 ";
• replace the substring " 10 " with the substring " 01 ".

It is necessary to calculate how many ways there are to get a string of a certain length from a given one using these operations.
')
To begin with, we will look at the replacements operations and understand that this is nothing but a swap. Thus, we can get any from this string, which contains the same number of zeros and ones. Now, using these operations, we obtain from the source line, where all zeros are at the beginning, and ones at the end. From the resulting string, we can get a string of new length, without rearranging anything, since all ones and zeros are already grouped. A string of length k can be obtained from a string of length n by removing 3x ones and 2y zeros, where k = n - (3x + 2y) . The x and y values ​​can be iterated. And finally, for each obtained string of the required length, we need to take into account all permutations. They can be calculated, for example, as the number of combinations of the length of a line by the number of units in it. The answer will be equal to the sum of these combinations for all the lines of the desired length, which can be obtained from this one.

Problem B. Splitting into teams

Idea : Gregory Shovkoplyas
Implementation : Dmitry Filippov
Analysis : Dmitry Filippov

The problem is given a graph, on each edge of which numbers 0 or 1 are written, meaning that the ends of the edges are the same color or different, respectively. Also, some of the vertices of the graph are painted white or black. The question is, is it possible to somehow paint the remaining vertices in black and white so that the information written on the ribs is correct and the number of vertices in black and white is the same?

We partition our graph into connected components. Note that, knowing the color of one vertex in the component, we can restore the color of all the others. From this it follows that if at least one vertex is already colored in the component, the coloring of the entire component is unique (except for the case when some of the required conditions are violated in the resulting coloring, then the answer to the problem is “ NO ”). If no vertex is colored yet, there are two variants of coloring - you can paint any vertex of the component white, restore the colors of the other vertices, and after that, if they are inverted, we get the second coloring.

It is easy to see that we have reduced our original task to the backpack problem: we can take some white vertices from each component, and all we have to do is type n 2 (if n is odd, the answer to the problem is “ NO ”). And this can already be solved with the help of dynamic programming for O (n ² ) .

Task C. Map

Idea : George Korneev, Vitaly Aksyonov
Realization : Vitaly Aksyonov
Analysis : Vitaly Aksyonov

The problem is given a checkered convex polygon on the checkered plane. You need to fold it once along the vertical grid line so that the area occupied by the polygon after addition is minimal.

Consider first the simplest version of the problem. Given a rectangle, and you need to fold it, getting the minimum area. Obviously, it should be folded along the grid line closest to the middle (if there are two of them, then it can be folded on any). Consider the area function of the fold position. For a rectangle with corners ( x ₁ , y ₁ ) and ( x ₂ , y ₂ ), this function has the following form:

• on segments ( -∞; x ₁ ] and [ x ₂ ; + ∞ ) the function is equal to the area of ​​the rectangle;
• on the segment [ x ₁ ; (x ₁ + x ₂ ) / 2 ] the function decreases linearly with the coefficient y ₂ - y ₁ ;
• on the segment [ (x ₁ + x ₂ ) / 2; x ₂ ] the function increases linearly with the coefficient y ₂ - y ₁ .

Total: the function changes its state only at three points. Between two points in a row, the function is linear.

Note that, since our task is discrete, in the case when ( x ₁ + x ₂ ) is not divisible by two, it is better to beat the function into five sections between the points x ₁ , (x ₁ + x ₂ ) / 2⌋, (x ₁ + x ₂ ) / 2⌉ and x ₂ .

Let our polygon be given by n vertices. Then it is easy to see that a convex checkered polygon can be cut into at most n rectangles by horizontal lines. Then the function of the area depending on the place of addition will be the sum of the functions for the rectangles. Again, it is easy to make sure that if we take all the change points for each function and sort them, then the global function between two adjacent points will be linear. Then the answer is to take a minimum of the values ​​at these points.

To realize this, you need to take advantage of the idea of ​​events. Each event will correspond to the point of change of the function for some rectangle. Then, processing the events from left to right and recalculating the coefficient of a linear function, it is easy to calculate the function at the selected points.

Problem D. Cartesian trees

Idea: Artem Vasilyev
Realization: Ilya Zban
Analysis: Ilya Zban

In the problem given n numbers y _i , it was necessary to calculate how many Cartesian trees can be built on the set ( i, y _i ). To begin with, we note that if all n numbers y i are equal to the same number, then the answer is C _n , n is the Catalan number. You can understand this, for example, on the basis of the recurrent formula: if k vertices are defined in the left subtree, then nk-1 vertices will be in the right subtree, that is, C _n = Σ _{k = 0} ⁿ C _k · C _nk-1 . Consider all occurrences of the maximum number in the array. Any vertex with such a priority can be either a root, or be a child of another vertex with the same priority. Let the occurrences of a maximum have indices a ₁ , a ₂ , ..., a _k . Then we have to build some Cartesian tree on the vertices a ₁ , a ₂ , ..., a _k , and hang some Cartesian trees built on the vertices (1, ..., a ₁ -1), (a ₁ +1, ..., a ₂ -1), ..., (a _k +1, ..., n) . Note that for neighboring a _i and a _{i + 1} in any Cartesian tree built only on maximal vertices, one of these vertices will be the ancestor of the other, therefore the subtree constructed on the vertices ( a _i +1, ..., a _{i + 1} -1 ), we can uniquely hang for one of these two vertices.

Thus, the number of ways to build a Cartesian tree on vertices from l to r is equal to cnt (l, r) = C _k · cnt (l, a ₁ -1) · ... · cnt (a _k +1, r) . The answer will be cnt (1, n) .

Task E. Alley

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

From a mathematical point of view, the problem contains segments of integer length. It is necessary to break some of them into smaller ones so that the length of the largest segment is as short as possible, and the number of partitions does not exceed the specified number. The task is somewhat complicated by the fact that the total length of all segments can reach 10 ⁹ , and the number of queries that need to be answered can reach 10 ⁶ .

Consider how many breaks need to be done so that the answer is no more than Ans . For each segment of length Len it is necessary to make (Len - 1) / Ans partitions (the result of division is rounded down). We construct the function of the number of necessary splits of the answer for each segment. Add these functions for all segments. In order to find the minimum value of Ans that can be achieved by making no more than K partitions, we use the binary search.

We will store the functions in a compressed form, namely, we will save the value of the function for Ans only if f (Ans) ≠ f (Ans-1) . It can be proved that for the length segment Len the O (sqrt (Len)) memory is required to save its function. Positions in which the value of the function changes can be determined in time proportional to their number. The maximum total number of change positions will be achieved on a test in which all segments have the same length. In the case of restrictions, which are given in the statement of the problem, their number cannot exceed 10 ⁶ · sqrt (10 ³ ) = 10 ^7.5 .

To combine several functions that are saved in a compressed format, you need to sort out all the moments of changing functions. To do this, we divide all positions in which the functions change into two classes. In the first class, we put all positions that are less than 10 ⁶ . They can be sorted by counting in time proportional to their number. The rest of the positions will be few, and for their sorting you can use the built-in functions of the language. To make sure that the number of positions that are more than 10 ⁶ is small, we will do the following. To ensure that a segment of maximum length does not exceed 10 ⁶ , it is sufficient to make no more than Len / 10 ⁶ partitions of segments. Since in the condition of the problem the total length of the segments does not exceed 10 ⁹ , the number of changes in the function whose positions exceed 10 ⁶ will be less than 1000.

Problem F. Stage Lighting

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

In this problem, an array of pairs (power, set of outputs) is given with a rather confusing condition, and for each left boundary in the array, we need to find a minimal right boundary so that there is a subset of pairs with the following conditions on this sub-array:

1. The amount of power must be at least Z.
2. The sets of outputs of the selected spotlights do not overlap in pairs.

A subarray with such properties will be called good. First, we solve the problem for one fixed left border. This problem can be solved with the help of dynamic binary _mask programming: dp _mask is the maximum cost of spotlights, for which the union of output sets is a subset of mask . The recalculation formula for adding one element (p, m) looks like this: dp ' _mask = max (dp _mask , dp _{mask - m} + p) , if m is a sub- mask of mask , and dp _mask - otherwise. Adding one element can be realized in O (2 ^k ) . When dp _{2 ^k - 1} becomes greater than or equal to Z , an answer must be given.

It is easy to prove that as the left boundary increases, the corresponding right boundary does not decrease. This allows you to use the technique of two pointers to find the answer. To implement the technique of two pointers, it is necessary to implement a data structure that supports the following operations:

1. Add item to end.
2. Remove item from start.
3. Answer the query: “Is the current set of spotlights good?”.

The solution to this problem uses the implementation of a queue on two stacks with ideas from the method of implementing a queue with a minimum. Similarly, the queue with a minimum, we will store in the stacks not just elements, but pairs (element; array dp _i , which contains values ​​of DP for elements from the current and below). Adding one element to such a stack can be done in O (2 ^k ) , deletion in O (1) . Finally, using this modification of the stack in the queue, you can respond to a type 3 request with O (2 ^k ) : the answer is positive if and only if max _{i = 0..2 ^k - 1} dp ¹ _i + dp ² _{2 ^k - 1 - i} ≥ Z , where dp ¹ , dp ² - arrays of values ​​of DP at the top of the first and second stack, respectively.

In conclusion, remembering that each element moves O (1) times to the results of a queue implemented on two stacks, we find that the solution works in O (n2 ^k ) time and uses O (n2 ^k ) memory.