RCC 2014 Warmup Training Round / Mail.ru Group Blog

The next season of the largest Russian Olympiad for programmers, the Russian Code Cup, started on Saturday, April 19, 2014. Ahead of new interesting and non-trivial tasks, uncompromising struggle and great prizes.

The jury of the Russian Code Cup prepared one surprise for all participants: on April 17, each of them had the opportunity to evaluate their strength. At 19:30 Moscow time , a training round of the Olympiad took place at http://codeforces.ru with a fresh portion of tasks from the creators of RCC.

RCC 2014 Warmup is a test that made it possible to try your hand and understand what to prepare for in the rounds of the championship. And for “experienced” participants, he was an ideal opportunity to train and warm up before the first battles of RCC 2014.

Moreover, if the Russian Code Cup tasks for participants are offered only in Russian, then on the Warmup Round tasks were in both Russian and English, which significantly expanded the geography of the venue. A total of 3265 participants registered for the round.

The conditions of the tasks were very different: it was necessary to help with the selection of participants for the Russian Code Cup final of 2214, restore the test system data after the fall, hold a football tournament among the participants of the Russian Code Cup, help the cunning boy Gene get a T-shirt, solve the interesting task of the boy Misha during travel by boat after the final of the Russian Code Cup, organize the final of the Russian Code Cup 2214 in a large number of hotels and get a password to access tasks during their development (the latter did not succeed).

So, let's see how it was best to prepare for participation in the championship.

Problem 1. Selection

Analysis: First, it should be noted that if k is greater than or equal to n • m, then the answer is 0. We only need to dial n • m - k people. There are three ways to dial them:
• Take only rounds of the first type:
• Take a little rounds of the second type to a number divisible by n:
• Take only rounds of the second type: d (n • m - k).
Also in this problem it was possible to write an exhaustive solution - how many rounds of the first type we take, and how many rounds of the second.

Task 2. Failure

Parse:Let's start an array a with 105 elements, initially filled with -1, and in the cell with number k we will store the maximum number of the kth participant's package, which is now there. We will process the parcels sequentially. Let the parcel xk be processed. If a [k] <x - 1, then it is obvious that the answer is NO, otherwise we update the array - a [k] = max (a [k], x).

Problem 3. Football

Analysis: Imagine a tournament as a graph. From each vertex there are exactly k outgoing edges. Then all nk edges. The full graph has a maximum of edges, so if n <2k + 1, then the answer is -1. Otherwise, connect the i-th vertex with i + 1, ..., i + k, and loop if necessary.

Task 4. Tricky Gene

Analysis:Let's sort our friends in ascending order of required monitors. We will consider the dynamics on the masks - what is the minimum amount of money you need to pay in order to solve such and such problems, if we took the first i friends. Then the answer must be compared with the answer for the first i friends plus the number of monitors that the i-th friend requires. It is not difficult to notice that if you take friends in sequence, then you can recalculate the dynamics as a backpack. The running time of this algorithm is O (nlog (n) + n2m).

Problem 5. Square table

Analysis: Let's build an array of length n for any n such that the sum of squares of numbers on it is a square:
• If n = 1, then take [1].
• If n = 2, then we take [3, 4].
• If n is even, then we take .
• If n is odd, then take.
We are given 2 numbers n and m. Let an array a correspond to the number n, and b correspond to the number m.
Then we construct the final array c in the following way - cij = ai • bj.

Task: 6. Big problems of the organizers.

Analysis: There are two solutions to this problem.
The first one. Suspend for some vertex. Let us calculate for each 3 the most distant vertices in its subtree, as well as the depth for each vertex. We also calculate arrays for binary upsurge. For each vertex i and degree two 2j, we calculate the following arrays - p [i] [j], up [i] [j] and down [i] [j]. p [i] [j] is the ancestor of the vertex i at a distance of 2j. In up [i] [j], the longest path from i will be stored to the vertices that are in the subtree of the vertices that are on the path between i and p [i] [j]. down [i] [j] is different from up [i] [j], which stores the path from the vertex p [i] [j].
Now it’s up to small. We receive a uv request, we are looking for its smallest common ancestor - w. It remains to find the peak hu, which will be in the middle of this path. Trim the tree at this vertex, and calculate the longest distance from the vertex u in its tree and the longest distance from the vertex v in its tree. Presenting this on the tree, if we do not delete, then we can, using our pre-calculated arrays, accurately recalculate the value of the longest path.
The solution is O (nlog (n)).
The second one. In short. Find the diameter of this tree. We calculate the answer there on the prefix for each vertex. Then, when answering the request, we find when the path results in a diameter. On this segment we find the middle peak, and then respond to the request with a prefix or suffix.

Task: 7. Tricky password
Analysis: The key theoretical idea of ​​this problem is that the 2nd line coincides with 4, 3 with 5, etc. Therefore, we need to be able to change something only on the first three lines.
Now the matter remains the practical part. First of all, we will compress all the values ​​so that they do not exceed 105. We divide the array into segments of length LEN. On each segment, we will consider the following - for each value we will store how many times it was found on the cnt prefix, as well as the Fenwick tree, in which the number of numbers on this prefix that occur exactly k times will be stored in cell f [k]. It is easy to notice that the answer to queries on the second row is stored in the first array, and to get the answer for the third row, you need to calculate f [cnt [k] ... 105]. It is also clear how to recalculate this dynamics.
Total, we get time for a request for . If we take , the response time to the request will be .