We analyze the tasks of the second qualifying round of the Russian Code Cup 2014

On Sunday, May 18, the second qualifying round of the RCC 2014 was held. 5451 people registered for participation in the round, more than 1500 people took part, 886 of them sent at least one decision. A total of 4890 decisions were sent during the round.

Gennady Korotkevich (tourist), one of the winners of the RCC 2013, confidently took the first line in the participants' table of the 2nd qualifying round , solving all 5 problems with the smallest penalty time. Also, Gennady was the first of all participants in the round to solve problems A, B, C, and E at 4:22, 9:40, 16:25, and 50:29 minutes, respectively. The first at 30:17 minute problem D was solved by Dmitry Sutygin (morojenoe). According to the results of the 2nd qualification round, 200 of the best sports programmers moved to the qualifying round, and 11 people were disqualified by the judges for cheating.
')
Participants who did not qualify in the first two rounds can take part in the 3rd and 4th qualification rounds, which will be held on May 24 at 19:00 and on June 1 at 13:00 Moscow time.

We remind you that in order to take part in the Russian Code Cup, you need to register on the site (registration will be open before the start of the last qualifying round).

Task A. Team Olympiad .
Idea: Vitaly Aksenov.
Realization: Andrei Komarov.
Analysis: Vitaly Aksenov.
The most logical in this task is to immediately sort out the number of tasks of the first type that Vasya decided. Let him solve vn problems of the first type, then it is obvious that the maximum number of problems of the second type vm that Vasya could solve for the Olympiad is (n-vn • p) / q. So, we have n - vn tasks of the first type and m - vm of the second. It is necessary not to forget to compare these quantities with zero.
Let us calculate what the maximum number of tasks of the first and second types can be solved for the Olympiad. The first type is maxn = t / p, and the second is maxm = t / q. Thanks to the calculated values, it is easy to calculate the answer: 1 + (n - vn + maxn - 1) / maxn + (m - vm + maxm - 1) / maxm.

Task B. Three rooks .
Idea: George Korneev.
Realization: Demid Kucherenko.
Analysis: Vitaly Aksenov.
Note that rooks can be set up only in a 3 by 3 square. Any other arrangement reduces to this transfer of rooks. There are two solutions. The first one just goes through all possible arrangements of three rooks in a 3 by 3 square.
The second one considers all the different variants of mutual arrangements of 3 rooks:
* (1, 1), (2, 2), (3, 3). Beat 3 • n + 3 • m - 12 cells.
* (1, 1), (1, 2), (2, 3). Beat 2 • m + 3 • n - 9 cells.
* (1, 1), (2, 1), (3, 2). Beat 3 • m + 2 • n - 9 cells.
* (1, 1), (1, 2), (2, 1). Beat 2 • n + 2 • m - 7 cells.
* (1, 1), (1, 2), (1, 3). Beat m + 3 • n - 6 cells.
* (1, 1), (2, 1), (3, 1). Beat n + 3 • m - 6 cells.
In all other cases, you must output "IMPOSSIBLE".

Task C. The king and queen .
Idea: Vitaly Demyanyuk.
Realization: Pavel Krotkov.
Parsing: Pavel Krotkov.
Note that the maximum number of regions on the board is eight. We will learn how to find the size of one of them, and find the sizes of all the others by reflecting and turning the board several times.
Let the queen be in a cell with coordinates (x, y), rows and columns are numbered from scratch, and we want to learn how to find the size of the region located to the left of the vertical on which the queen is standing, and above the diagonal ray released to the left upwards from the cell in which worth the queen. Note that if this beam rests against the top edge of the board (x ≥ y), the answer will be the sum of all numbers from 1 to x - 1. Otherwise, the number of cells that would be the queen bits should be subtracted from this value , if not for the edge of the board. The number of such cells is equal to the sum of all numbers from 1 to x - y -1.

Task D. Tree
Idea: Anna Malova.
Realization: Artem Vasiliev.
Analysis: Vitaly Aksyonov.
Given a tree that needs to be obtained from one vertex by two operations: cut an edge and add 2 vertices to the sheet. To solve this problem, we first check whether there is a vertex of degree at least 4. If it exists, then a tree cannot be obtained.

In any other case, you can build a tree. To do this, we calculate the number of vertices v 2 of degree 2 and v3 of degree 3. If there is a vertex of degree 2, then when choosing its initial, we construct a tree for (v 2 - 1) · 2 + (v 3 + 1), otherwise the number of actions is equal to ( v 2 + 1) · 2 + v 3. This is true because to obtain an internal vertex of degree 3, you need to apply one operation of the second type, and to get an internal vertex of degree 2 you need to apply 2 operations.

Task E. Tax on travel .
Idea: Boris Minaev.
Realization: Boris Minayev.
Analysis: Boris Minayev.
Note that the income received from taxes is always even, since for any pair of cities there are two residents who are going to travel along the path that connects them.
Calculate for each road the number of paths that pass through it. To do this, it is necessary to multiply the number of vertices in the two components, into which the tree is divided when the edge is removed. To calculate the total income, it is necessary to sum up on all roads the product of the fare on this road by the amount that we have just calculated.

We calculate the income that the president will receive if on all roads the prices for travel will be the lowest possible. Subtract this amount from the required. If we get a negative number, then there is not a single satisfying set of taxes. Note that if we get a non-negative number, then the total number of roads does not exceed 600.

Now we need to solve some modification of the backpack problem. It is solved by dynamic programming. We will consider all the roads in turn. We will also support the number of ways to collect a certain amount of money using only a certain prefix of roads. Consider in more detail how to handle the next road. Let the increase in the tax on travel on this road adds c monetary units to the total profit, and the price for traveling on the road may be in the range from 0 to max. How to find out how many ways there are to get total income m? In fact, this number coincides with the number of ways to get the total profit m - c with the exception of two terms. These terms correspond to the fact that we can assign a fare equal to 0, but we can not max + 1. That is, each value of dynamic programming can be calculated using the three already calculated values. Thus, the next road can be processed for O (MAX), where MAX is the profit that the president wants to receive.