Qualifying round of the Russian Code Cup 2014: results and analysis of tasks

Last Sunday, the qualifying round of the Russian Code Cup 2014 took place. It was attended by 802 programmers, who showed the best results in four qualifications. At this stage, the participants had to solve six problems in 3 hours, which is one hour and one task more than in the qualifying rounds. And the tasks were significantly more complicated than the previous ones. During the competition of the 802-x only 444 participants were able to solve at least one problem. A total of 3271 solutions were sent, of which 1402 were correct.

Most solutions on GNU C ++ - 1516.
Java 7 solutions - 333.
Java solutions 8 - 106.

The first task A was solved by Gennady Korotkevich (tourist) in 2:52 minutes. Gennady also solved problems B, C, and D at 7:05, 24:29, and 13:05 minutes, respectively. Task E was first solved by Dmitry Egorov (Dmitry_Egorov) at 40:59 minute. Task F was one of the most difficult in the entire history of the Russian Code Cup - of all the participants, only three people solved it correctly, and the first task F was solved by the winner of the RCC 2013 Peter Mitrichev (Petr) for 2:25:46.
')
Pavel Kunyavsky (PavelKunyavskiy) was the first to handle all the tasks in 2 hours and 47 minutes. Only 6 tasks were solved by 3 people, 100 people solved 5 and more problems. The last in the cherished top 50 was Roman Bilyi (RomaWhite), who passed the fifth task 2 hours 30 minutes after the start.

For the will to win, we note Egor Kulikov (Egor), who entered the top 50, having passed one of the tasks on his 7th attempt. As well as Petr Mitrichev (Petr), who, not thinking up how to solve task C, refused to try to solve it, first solved the most difficult task F. And then, returning to task C, he passed it 4 minutes before the end and finally took 3 a place.

The territorial distribution of participants in this round was as follows:

Russia	515
Ukraine	112
Belarus	77
Kazakhstan	26
USA	17
Armenia	eight
Uzbekistan	eight
Switzerland	6
Germany	four
Latvia	four
Austria	2
Bulgaria	2
Great Britain	2
Georgia	2
Moldova	2
Poland	2
Republic of Singapore	2
Azerbaijan	one
Argentina	one
Ireland	one
Canada	one
Cyprus	one
Lithuania	one
The Republic of Korea	one
Slovakia	one
Turkey	one
Sweden	one
Japan	one

At the same time for the first time in the Russian Code Cup were participants who do not know the Russian language from Austria, Argentina and Japan! As one of them admitted, he translated the conditions of the tasks of the round through online translation services.

The fight in the qualifying round was tense. As a result, 50 strongest programmers reached the final. We will tell about them in detail later.

Task A. Analysis of tasks

Idea: Anna Malova
Realization: Andrey Komarov
Analysis: Andrey Komarov

In the task it is required to make a plan for the analysis of the tasks so that the total duration of the analysis is minimal. Tasks must understand in order from first to m th. The time to parse one task is t seconds. Replacing the jury member who is reviewing the task is c seconds. If the same jury member deals with several tasks in a row, then replacement is not required. About each member of the jury it is known which tasks he wants to disassemble, and which - no.

This problem is solved by a greedy algorithm. Choose a jury member who is able to solve the maximum number of tasks, starting with the first one. Let him know how to solve k problems. Then, choose one who knows how to solve the maximum number of tasks, starting with the kth . We will continue this way until all the tasks are resolved. Then the answer to the problem is m · t + q · c , where q is the number of substitutions made.

Why is this the best answer? Suppose that at some point a jury member was chosen who wants to analyze not the maximum number of tasks. Then, from the fact that it will be replaced by someone who knows how to disassemble more and give it more to disassemble, the answer can only improve.

This solution works for O (n · m).

You could also write a simple solution using dynamic programming. dp [ i ] [ j ] is equal to the minimum time that is spent if I have analyzed the tasks and the i- th has analyzed the j- th jury member. This array can be easily calculated as O (n ² m) .

Problem B. On a distant Amazon

Idea: Vitaly Aksenov
Implementation: Demid Kucherenko
Analysis: Demid Kucherenko

In this task, it is necessary to construct a directed graph consisting of n vertices, in which the following conditions are satisfied:

• there should be no cycles in the column;
• a maximum of one edge leads to each vertex;
• the graph must have exactly a vertices from which outgoing edges exist;
• the graph must have exactly b vertices into which incoming edges exist.

To begin with, let's look at cases when the answer is “IMPOSSIBLE”. These are cases when at least one of the following conditions is met:

• there are more mothers than daughters;
• mothers are greater than n -1 (all cannot be mothers);
• daughters are greater than n -1.

If such a graph can be constructed, then first we construct a chain of a edges. So we will have a +1 woman involved, and there will be a mothers and a daughters. After that, we supplement the daughters of any mothers so that the daughters become exactly b . It may happen that some women are neither mothers nor daughters, but this does not contradict the condition of the problem.

Problem C. Laboratory in Physics

Idea: Vitalik Aksenov
Realization: Artem Vasilyev
Analysis: Artem Vasilyev

In this task, it is required to determine what water temperature can be obtained by mixing water from two vessels with cold and hot water. It was necessary to respond to several such requests at a given temperature.

We write the water temperature formula if we mix cold water from a vessel with volume c _i and hot water from a vessel with volume h _j : T = p / q = (C · c _i + H · h _j ) / (c _i + h _j ) this formula, we get that (H · q - p) / (p - C · q) = c _i / h _j Thus, we reduced the problem to the following: an irreducible fraction and a set of numerators and denominators are given, is it possible to choose the numerator and denominator to get a given fraction?

We introduce the notation A _x - the set of all c _i / x, where c _i is divisible by x . Similarly, B _y is the set of all h _i / y, where h _i is divisible by y . Then the irreducible fraction p / q can be represented if and only if A _p and B _q intersect. It should be noted that the total size of all sets A _x and B _y is O ( M log M ), where M is the limit on the volume of vessels (in this problem, M is 10 ⁵ ).

When A _x and B _{y are} represented as sorted lists, one query can be executed for O (M / max (x, y)) . If we represent A _x and B _y as bit sets, then we get a solution in O ( M / 64) per request.

The quickest solution is obtained, except for the answers for the same fraction several times. In this case, it is possible to prove a more accurate estimate for the time the solution works. Let us prove the estimate O ((M + k) sqrt (M)) , where k is the number of queries. If the maximum of p and q is greater than sqrt (M) , then the query can be executed in O (sqrt (M)) by looking at all the elements of the smaller one from the sets. We estimate the sum of the execution times of all other queries. Requests running in O (M / x) are no more than 2 x . Summing over all x, and taking into account that x is not greater than sqrt (M) , we get the estimate O ((M + k) sqrt (M)) The total running time of the solution: O ((M + k) sqrt (M)) .

Task D. Designing saws

Idea: Nikolay Vedernikov
Realization: Nikolay Vedernikov
Analysis: Nikolay Vedernikov

The task requires counting the number of permutations, such that:

• a _{2 · i -1} ≤ a _{2 · i}
• a _{2 · i} ≥ a _{2 · i + 1}

For all i from 1 to n ⁄ 2. We call such a permutation an increasing sawtooth .

Note that the number of such permutations is equal to the number of permutations that have numbers in odd positions that are larger than their neighbors. Bijective correspondence: b _i = n - a _i . We call such a permutation a decreasing sawtooth. This is useful to us further to solve the problem.

Obviously, if the length of the permutation is 0 or 1, then the answer is 1.

Suppose we know the answer for all lengths from 0 to n , find the answer for n +1. We will consider the total number of sawtooth sequences. In order to get the number of increasing, you need to divide the total number of sequences by 2, since the number of increasing is equal to the number of decreasing.

Let n +1 be put on the position 2 · k , then first we have an increasing saw-tooth with a length of 2 · k −1, and then an increasing length with a length of n −2 · k +1. For the first 2 · k −1 positions, we can choose any of the n numbers. Total, we find that the number of permutations of length n +1, for which the number n +1 is at the position 2 · k : ans _{2 · k −1} · ans _{n −2 · k +1} · Binom ( n , 2 · k −1) .

Let n +1 be put on the position 2 · k +1, then first we have a decreasing sawtooth with a length of 2 · k , and then an increasing length of n −2 · k . For the first 2 · k positions, we can choose any of the n numbers. In total, we find that the number of permutations of length n +1, for which the number n +1 in the position 2 · k +1 is: ans _{2 · k} · ans _{n −2 · k} · Binom ( n , 2 · k ).

Total, the total number of sawtooth sequences of length n +1: ans _{n +1} = ∑ ⁿ _{k = 0} ans _k · ans _{n − k} · Binom (n, k) .

Task E. Salary

Idea: Anna Malova
Realization: Pavel Krotkov
Analysis: Pavel Krotkov

In this problem, a directed graph is given. All edges could be classified into three parts:

• in any arrangement of salaries and bonuses at the vertices of this edge, the condition of leadership will be fulfilled;
• to fulfill the conditions of the leadership, it is necessary either to change the salary with a bonus in both tops of this edge, or not to change on one;
• to fulfill the conditions of the leadership, it is necessary to change the salary with a bonus at exactly one of the vertices of this edge.

Let us forget about all the edges of the first type and about the orientation of the edges of the second and third types. After this, we merge the vertices reachable from each other along edges of the second type. After this, the task of checking whether the requirement of the manual can be fulfilled reduces to checking whether the resulting graph can be colored in two colors, which can be solved by a detour in depth.

To obtain the minimum number of vertices in which you need to swap salary with a bonus, modify this depth-first search. After traversing and coloring in two colors of the next connected component, we calculate the number of vertices (of the original graph, before combining by edges of the second type) painted in the same color, and, if necessary, invert the coloring.

Problem F. Robot

Idea: Boris Minaev
Realization: Boris Minayev, Artem Vasiliev
Analysis: Boris Minayev, Artem Vasilyev

The task is to calculate the number of different paths from one cell of the field to another in a certain number of steps. At the same time, a robot that performs actions cannot visit the final cell earlier than the last turn. Also, the robot can only walk one quarter of an infinite plane.

First, let's find the number of ways to get from one cell to another without the condition that you cannot visit the final cell before the last turn. Such a task can be solved independently according to the coordinates, and then go through how many moves were performed on one coordinate, and how many on the other. How to solve a problem in a one-dimensional case? Let the robot initially have a coordinate x ₁ , and at the end should have a coordinate x ₂ . Let a = | x ₂ - x ₁ |, and in total t moves were made. Then the number of different methods will be equal to the number of combinations of t for ( t - a ) / 2 (in this case, t - a must be non-negative and even). However, it should be noted that the robot can only have a positive coordinate in the process of traveling. To do this, simply subtract from the result the number of ways to get out of the cell - x ₁ to x ₂ . This is true, since between the paths from x ₁ , which violate the requirement of the positivity of the coordinate, as well as all the paths from - x _1, one-to-one correspondence can be shown. The paths corresponding to each other will have mirror first parts (until the entrance to cell 0) and common second parts.

Let us return to the consideration of the two-dimensional problem. Suppose we have already counted the number of ways to get to each coordinate from one cell to another (for each fixed length of the journey). To calculate similar values ​​for a two-dimensional task, you need to sort out the amount of time spent on each coordinate, and then multiply the corresponding values ​​in the already calculated arrays, and also multiply by the number of different ways to choose which moves will correspond to which coordinates. To calculate these values ​​quickly, you can use the Fourier transform. To reduce the problem to the multiplication of polynomials, it is necessary to get rid of the presence in the formula of the number of combinations. To do this, write it through factorials. By grouping the terms, we get that we can divide the i- th elements of the original arrays by i !, Multiply the resulting polynomials, and then multiply the value in the i- th digit by i ! In the task, the module on which it is necessary to perform all operations was chosen in such a way that it can be used to perform a fast Fourier transform.

Now consider how to take into account the fact that the robot can not enter the final cell until the last turn. We will consider the answer using dynamic programming. Let the number of ways to reach the cell in less than t moves be counted. To calculate this value for t moves, consider the total number of ways to do it in t moves and subtract from it all the methods that go into the final cell before turn t . To do this, let's go through the number of the first move, in which the robot visits the final cell and multiply the corresponding number of ways by the number of ways to get out of the cell ( x ₂ , y ₂ ) and return to it in the remaining time. At the same time, the robot can visit the final cell as many times as necessary (in the second part).

Note that the solution described above works for t ² . For a faster solution, you should reason in terms of generating functions. Denote f (x) = f ₀ x ⁰ + f ₁ x ¹ +… + f _t x ^t + ... , where f _i is not the answer. Similarly, we define count (x) - the generating function for the number of paths, without taking into account the condition of the first entry into the final cell on the last turn, cycle (x) - generating function for the number of paths from the final cell to itself. From the recurrence relations for f _i , we can derive the relation to the generating functions: f (x) = count (x) - f (x) cycle (x) , whence f (x) = count (x) / (cycle (x) + 1) = count (x) (cycle (x) + 1) ^-1 . To calculate f, it is necessary to calculate the first t + 1 terms of the fraction on the right-hand side. This can be done by calculating the inverse of cycle (x) + 1 polynomial modulo x ^{t + 1} , and multiplying count (x) with the result. Taking the inverse polynomial modulo x ^{t + 1} can be performed in O ( t log t ) time using the fast Fourier transform. Total running time: O ( t log t ).