Analysis of the tasks of the training warmup round of the Russian Code Cup 2015



    On Sunday, a training warmup round of the Russian Code Cup took place. The first place was taken by Mikhail “mmaxio” Mayorov from Perm. The second - Igor "kraskevich" Kraskevich from Moscow. Third - Valentine “ValenKof” Kofman from Moscow. Congratulations to the winners!

    Ahead are the 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 is on the site http://www.russiancodecup.ru/ before the third qualifying round begins.

    Russian Code Cup is an opportunity for Russian-speaking programmers from all over the world to test their strength and demonstrate mastery, solving original problems of varying complexity, as well as express themselves to the expert IT community. The Olympiad takes place in three stages: qualification rounds, qualifying rounds and finals - at each of which four to eight diverse tasks are offered to participants in the Olympiad. The tasks and the technical part of the competition are provided by Mail.Ru Group specialists and experts from ITMO University, co-organizer of the Russian Code Cup.

    And now we will deal with the solution to the problems of the warmup round.

    Problem A. Balloons

    Find the number of different numbers in the array. If it is greater than or equal to k , then we can type kdifferent colors in response. If it is less than k , then we take one ball of each color, and take the missing balls arbitrarily. 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. Duplicate the boxes: say, we have not one box with two payment methods, but two with different costs, of which you can buy only one. Sort by time events: cash receipts and boxes. Moreover, if the time at the nearest receipt and at the box are the same, we prefer receipt. For each money receipt event, we simply add the received amount to the current amount. For each box appearance event that we have not bought yet, we check to see if there is enough money, and if so, then we buy the box.

    Problem C. Solemn parade

    If k> n 2 or the number of primes up to 10 7 is less than k, then there is no solution, in other cases the solution exists.

    We take advantage of the fact that the number of divisors of the number n = p1 s1 × p2 s2 × ... × pk sk is (s 1 +1) × (s 2 +1) × ... × (s k +1) .

    We generate a matrix so that in each row and each column the sets of powers of primes are equal, that is, so that 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 for all rows and columns of the number.

    If k> n , then n 2 - (k - n) matrix fill cells as follows: i -th row of the matrix fill the i -th cyclically shifted first n primes, and the remaining k - n matrix cells fill the remaining k - n primes . Thus, in each row and each column there will be exactly n different primes, and the number of divisors for them will be the same.

    If k ≤ n , then in the a [i] [j] th cell of the matrix we put (i + j) mod k-e prime (when indexing from scratch). You can make sure that this 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 in which the sum of the weights of the minimum and maximum edges is maximum. First, note that the function \ emph {is it true that the answer to the problem ≥ x} is monotonic. So, you can run a binary search on it. How to check that the answer to the problem is ≥x ?

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

    After that we continue the algorithm - take the next non-negative edge with weight w 2 , add all edges with weights -w 2 .. -w 1 -1 and add the edge w 2 itself. If, when adding, the ends of the edges were in the same component, then the cycle is found, if not, it is not there yet. We continue to execute the algorithm for all non-negative edges.

    Problem E. Lottery

    First we solve the problem when all x i are different. Sort the queries in ascending order x i . At every moment of time, we want to know which elements of the array are already occupied by some number. Initially, not a single element of the array is busy.

    Let us now have an array, some elements are occupied in it. We want to process a request whose response is x i . Queries for all x j such that x j <x ialready processed. We calculate the number of unoccupied elements on the segment l i ..r i . Let it be cnt . Then we say that we will put some number in all these elements and multiply the answer by x icnt - (x i -1) cnt is the number of ordered sets of cnt numbers, at least one number in which is equal to x i . We cannot put a number greater than x i in these elements (the response to the request in this case will not be equal to x i ). Therefore, we have not lost any arrays.

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

    Complete solution: we will solve the problem in the same way as in the previous case. Now we can have x i the same. We solve the problem for queries for which the answer is x . We remove from consideration all segments that contain others. On the remaining we count the dynamics: dp [i] - the number of ways to arrange numbers on a prefix of length i so that the number x is at the end . Then we need to iterate over the last time the number x was encountered , let this be the position 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 a segment. That is, so that there is no such segment ( l, r ), with the answer x , that j <l ≤ r <i . If this is the case, 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, the right border of which is located at position i and its left the end is closest to position i . Such dynamics will work in total for O (nm) .

    Note that the value of kfor position i can change in comparison with position i-1 only if at position i-1 there was the end of some segment. If, at position i-1, there was no right grazitsa 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 neighboring right borders, as x cnt , where cnt is the number of places in which you can put something.

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

    Also popular now: