Analysis of the tasks of the warm-up training round of the Russian Code Cup 2015

On Sunday, I passed the warm-up training round of the Russian Code Cup. The first place was taken by Mikhail “mmaxio” Majorov from Perm. The second is Igor “kraskevich” Kraskiewicz from Moscow. Third - Valentine "ValenKof" Kofman from Moscow. Congratulations to the winners!

Ahead of qualifying rounds of the championship. We remind you that the first qualifying round will be held on March 28 at 18:00 Moscow time, and registration for the championship takes place on the website http://www.russiancodecup.ru/ before the start of the third qualifying round.
')
Russian Code Cup is an opportunity for Russian-speaking programmers from around the world to test their strength and demonstrate their skills, solving original problems of varying complexity, as well as express themselves to the expert IT community. The Olympiad is held in three stages: qualifying rounds, the qualifying round and the final - each of which offers participants from four to eight diverse tasks. Tasks and technical part of the competition are provided by Mail.Ru Group experts and experts from ITMO University, co-organizer of the Russian Code Cup.

And now let's deal with the problem of the warmup-round.

Task A. Balloons

Find the number of different numbers in the array. If it is greater than or equal to k , then we can type k different colors in the answer. If it is less than k , then we take one ball of each color, and take the missing balls in an arbitrary way. You can find all the different numbers in the array by sorting.

Task B. Test purchase

In the task it was necessary to simulate the process described in the condition. We duplicate the boxes: let's say we have not one box with two payment methods, but two with different values, from which you can buy only one. Sort by event time: cash receipts and boxes. Moreover, if the time of the nearest receipt and the box are the same, we give preference to receipt. For each event of receipt of money, we simply add the amount received to the current amount. For each event of the appearance of the box, which we have not bought yet, we check whether there is enough money, and if so, then we buy the box.

Problem C. Solemn Parade

If k> n ₂ or the number of simple ones up to 10 ^{7 is} less than k , then there is no solution, in other cases there is a solution.

Let us take advantage of the fact that the number of divisors of a number n = p1 _s1 × p2 _s2 ×… × pk _sk is equal to (s ₁ +1) × (s ₂ +1) ×… × (s _k +1) .

We generate such a matrix so that in each row and each column the sets of powers of primes are equal, that is, the numbers in them have the form p1 _s1 × p2 _s2 × ... × pk _sk where p _i are some prime numbers, possibly different for each row and column, and s _i - fixed numbers for all rows and columns.

If k> n , then fill the n ₂ - (k - n) cells of the matrix as follows: fill the i -th row of the matrix with the i -th cyclic shift of the first n primes, and fill the remaining k - n cells of the matrix with the remaining k - n primes . Thus, in each row and each column there will be exactly n different prime numbers, and the number of dividers for them will be the same.

If k ≤ n , then in a [i] [j] -th cell of the matrix we put (i + j) mod k -th prime number (when indexing from zero). You can make sure that such a filling gives the desired result.

Problem D. The minions are having fun.

We reformulate the condition as follows: in an undirected graph, we need to find a cycle whose sum of weights of the minimum and maximum edges is maximal. First, we note that the function \ emph {is it true that the answer to the problem ≥ x} is monotone. So, you can run a binary search on it. How to check that the answer to the problem ≥x ?

Subtract x / 2 from all edges. Now we need to check the existence of a cycle whose sum of the minimum and maximum edges is greater than 0. Take the minimum edge with a non-negative weight, let its weight be w ₁ . Add to the data structure \ emph {a system of disjoint sets} all edges whose weight does not exceed -w ₁ . After that add an edge w ₁ . If, while adding, the ends of the edge lay in one component of the connectivity, then we have found the required cycle, if not - it has not yet.

After that, we continue the algorithm - take the next nonnegative edge with weight w ₂ by weight, add all edges with weights -w _{2 ..} -w ₁ -1 and add edge itself w ₂ . If, while adding, the ends of the edge lay in one component, then the cycle is found, if not - it is not there yet. Continue to execute the algorithm for all non-negative edges.

Problem E. Lottery

We first solve the problem when all x _{i are} different. Sort queries in ascending order x _i . At each moment in time, we want to know which elements of the array are already occupied by some number. Initially, no array element is occupied.

Let us now have an array, in it some elements are occupied. We want to process a request whose answer is x _i . Requests for all x _j such that x _j <x _i have already been processed. Calculate the number of unoccupied elements on the segment l _i ..r _i . Let it be cnt . Then we say that in all these elements we put some number and multiply the answer to x _icnt - (x _i -1) _cnt - the number of ordered sets of cnt numbers, at least one number in which is equal to x _i . A number greater than x _i , in these elements, we can not deliver (the answer to the request in this case will not be equal to x _i ). Therefore, we have not lost any arrays.

After we process all requests, we can put any numbers in the empty elements of the array. Therefore, we multiply the answer by k _cnt .

Complete solution: we will solve the problem as in the previous case. Now we have x _i can be the same. We solve the problem for queries, the answer to which is equal to x . Remove from consideration all the segments that contain others. For the remaining ones, we calculate the dynamics: dp [i] is the number of ways to arrange the numbers on the prefix of length i so that the number x is at the end. Then we have to go through, when the last time met the number x , let it be the position of j (in the remaining cells between j and i, the numbers are strictly less than x ), but this must be done so that we do not miss the segment. That is, so that there is no such segment ( l, r ), with the answer x , that j <l ≤ r <i . If it is, then there will be no x on it .

Therefore, dp [i] = sum (j = k..i-1: dp [j] (x-1) _{i - j - 1} , where k is the left border of the segment, whose right border is up to position i and its left the end is closest to this position i . Such dynamics will work in total for O (nm) .

Note that the value of k for position i can change compared to position i-1 only if there was an end of some segment in position i-1 . If, on the i-1 position, there was no right grancia of the segment, then dp [i] = dp [i-1] × (x-1) + dp [i-1] = dp [i-1] × x . Therefore, we can get rid of the multiplier n in the asymptotics, considering the value of the dynamics between two adjacent right boundaries, as x _cnt , where cnt is the number of places where you can put something.

The resulting solution will work for O (m log n + n) .