Analysis of the tasks of the fourth qualifying round of the Russian Code Cup 2014

On Sunday, June 1, the fourth, final, qualifying round of the Russian Code Cup 2014 was held.

5428 people registered for the round. At least one solution was sent by 730 participants. In total for the round 4793 decisions were sent, from them correct - 1531.
')
Most solutions on GNU C ++ - 1786.
Decisions on Python - 307, from them correct 86.
There are 93 PHP solutions, 15 of which are correct.
Perl solutions - 6, of which 2 are correct.

The first task was solved by Dmitry Filippov (DimaPhil) in 2:42 minutes, and he was the first to solve task B in 12:09. Problems C and D were first solved by Alexander Obednikov (AOb) at 12:25 and 37:44 minutes, respectively. The first task E was solved by Fefer Ivan (Fefer.Ivan) at 45:22 minute. Ivan was also the first to cope with all the tasks in 1 hour and 8 minutes. Only 5 problems solved 12 people. 10 participants were disqualified by the judges.

In just 4 qualifying rounds, 802 participants passed to the qualifying round, who will compete with each other in the final on June 8.

Task A Opinion poll
Idea: Andrei Stankevich
Realization: Nikolay Vedernikov
Analysis: Nikolay Vedernikov

The task is to find the minimum and maximum possible number of participants who will solve the problem. If the total number of participants is n , one of them knows how to solve problem a , and b to participants the task is opposite.

Since, according to the condition of the problem, it will be solved only by those to whom it is not disgusting and able to solve, the number of those who try to solve the problem will be equal to or less than n - b . That is, if among all those who try to solve the problem, there are those who can do it, then this will be the maximum among those who decide. This is min ( a , n - b ).

The minimum is reached if everyone who is against the problem will be able to solve the problem, then the answer is max (0, a - b ).

Task B. Hundred
Idea: Vitaly Aksyonov
Realization: Pavel Krotkov
Analysis: Pavel Krotkov

The solution of the problem is a program that carefully examines several simple cases. The simplest case is the situation when the number of digits in the number x is equal to k +1. In this case, you must output −1 if the number does not contain a single zero, and zero - if at least one zero is present in the number.

If the number of numbers in the number x exceeds k by at least three, this situation should be handled more carefully. We find among the second zero from the end. Make sure that there is no more than k +1 digit behind it. We delete from the number all nonzero digits behind the second zero from the end, and also delete the necessary number of digits immediately before the second zero from the end. Note that the first digit is never deleted, which means that there will not be leading zeros in the final number.

It was important not to forget that the operation of deleting numbers should not be performed beyond the length of the number - solutions with such an error received exceeding the time limit on the third test.

Task C. Hike on a visit
Idea: George Korneev
Realization: Boris Minaev
Analysis: Boris Minaev

To solve the problem, you must carefully simulate the process that is described in the condition. When implementing it is convenient to use built-in tools for maintaining the queue. In the queues themselves, you can store, for example, the number of the person who bought the corresponding gift. Then the next visit is as follows. Take the item from the queue, which corresponds to the person going to visit. If his turn is empty, then we will assume that an item was taken from the queue that corresponds to this person. After that, add this item to the queue, which corresponds to the person to whom they came to visit. If the value of the added item is equal to the queue number to which it was added, then YES must be output, otherwise NO.

Task D. SNM
Idea: Artem Vasilyev
Realization: Artem Vasilyev
Analysis: Artem Vasilyev

In the problem, the implementation of a system of non-intersecting sets with rank heuristics was described, but without a compression path heuristics. We will solve the problem for each root tree independently; we should also consider the case of the presence of cycles.

Although the rank array was not specified in the input data, it is easy to understand that without compressing the paths, rank _i is the height of the subtree with vertex i at the root. Also note that the algorithm is designed so that rank _i each time increases by no more than one, and after the vertex is suspended from another, its parent and rank do not change, so you can build from leaves to root.

Consider a subtree with root at u . If rank _u = r , then children with rank 0, 1, ..., r -1 must exist at the vertex u . It is easy to show that this condition is sufficient: if the union operations are performed in order of increasing the son’s rank, all operations will be completed correctly.

Hence the solution for a single tree:

1. Recursively build a solution for all children of the root of the tree.
2. We verify that for all h from 0 to rank _root - 1 there is a son with rank h .
3. We perform union operations ( root , child _i ) in order of increasing the rank of child _i .

It is also possible to implement SNM and directly perform all operations, checking that the resulting parent array coincided with the desired one.

Solution time is O ( n log ( n )).

Task E. Nanobots
Idea: Vitaly Aksyonov
Realization: Andrey Komarov
Analysis: Andrey Komarov

In the task, it is required to transfer all nanorobots from the upper left to the lower right for the minimum number of actions of moving or splitting into two parts.

We will solve this problem using dynamic programming. Denote by dp [ w ] [ x ] [ y ] the minimum number of steps for which you can bring a robot with a mass w from a cell ( x , y ) to the final cell ( n , m ). The initial values dp [ w ] [ n ] [ m ] = 0 indicate that there is no need to go from the target cell. After dp is calculated, the answer will be contained in the dp [ w ] [1] [1] cell.

Learn to count dp . To calculate dp [ w ] [ i ] [ j ], let's do one of two things:

• We will reach the finish without breaking the robot apart. To do this, using a detour to the depth, we find the shortest path to the finish line on the supporting cells.
• Or we will reach some cell, we will break into two parts and we will reach them from there.

So that there are no problems with understanding the order in which the values ​​of the dynamics should be considered, it can be considered lazy. The final complexity of the algorithm: O ( w ² n ² m ² ).