Analysis of the tasks of the first qualifying round of the Russian Code Cup 2015

On Saturday, March 28, the first qualifying round of the Russian Code Cup 2015 was held. 3093 programmers solved problems within two hours, of which at least one correct solution was sent by 1012 participants. The right decision for all five problems was passed by two: Gennady Korotkevich and Peter Mitrichev. In total, participants sent for verification 4069 solutions, 2517 in C ++, 705 in Java, 425 in Python, 318 in C #. There are 1745 correct decisions, 1099 of which were sent to C ++, 339 to Java.

The first in a record 2 minutes and 2 seconds to solve the problem A (Magic Cards) winner of the RCC 2014 - Gennady Korotkevich (tourist). He was the first to solve problems B (Homework) for 6:50 and C (Congress of Young Amateurs) for 25:43. Problem D (Decryption) in 51 minutes and 42 seconds was decided by the winner of the RCC 2013 Petr Mitrichev (Petr). And the last task E (Entertaining cryptography) was solved by the participant from Japan (anta) in 1 hour 2 minutes and 52 seconds. The last successful attempt was made by Mikhail Tikhomirov 6 seconds before the end of the competition. The most simple task A, the most difficult task - E, task E passed only 13 people.

Following the results of the round, 202 participants were qualified, who will compete for the title of finalist in the qualifying round on June 14. Those who were not lucky on Saturday and who for one reason or another could not take part in the round, will be able to try their hand in the second qualifying round on April 25 at 12:00, and if necessary in the third - on May 31 at 13:00 . In the qualifying round, scheduled for 1:00 pm on June 14, 200 best participants from each qualifying round will be selected. In order to participate in the Russian Code Cup, you need to register on the site (registration will be open before the start of the third qualifying round).
')
For the participants of the championships and interested ones, our VKontakte group is available, where you can find information about creating artificial intelligence, web-design, sports programming, developing interfaces, marketing and creating IT projects. The materials of the group include the opinions of industry experts, useful literature, master classes, educational videos, the best thematic conferences, as well as all the most interesting events in the IT sphere. Subscribers of the group will be the first to know all the important news about the Mail.Ru Group competitions and other Russian and international IT championships.

And now we will analyze the tasks of the first qualifying round.

Task A. Magic Cards

Idea: Vitaly Aksyonov
Realization: Gregory Shovkoplyas
Analysis: Gregory Shovkoplyas

The task requires you to check whether Grisha wins the round in any case, regardless of the selected cards. Consider the case when Grisha will have l minimal cards chosen, while Dima has l max cards. Obviously, if in this case Grisha wins, then he wins in any other, since if you replace any card among the chosen ones with another one from the player’s set, then the amount of Dima will not increase, and Grisha will not decrease. Thus, to solve the problem, you just need to sort the Grisha cards in ascending order, and Dima in descending order. Then find the sum of the first l numbers in both sets and compare them. If the amount of Grisha is more, he will win any round, otherwise he will not.

Problem B. Homework

Idea: Vitaly Aksenov
Implementation: Dmitry Filippov
Analysis: Dmitry Filippov

The problem contains three numbers x, y, z, written in decimal number system. It is necessary to check whether x _k · y _k = z _k is true for an infinite number of k ( x _k denotes the value of the number x , if we assume that it is written in the k -thick notation). Suppose that there are infinitely many such k . Then the equality must be satisfied for arbitrarily large k . Take a number system in which the multiplication of the numbers x and y will not transfer in any place. If in any digit there is a number greater than or equal to 10, then the equality will not be fulfilled for the given k , as well as for all the number systems with a large base, since there will also be no transfer to them. This means that the equality is true for an infinite number of numbers k , at least when multiplying without a transfer, there should not be any digits with numbers greater than 9. If this is done, all that remains is to check that the resulting product coincides with the number z , and if so, the answer to the problem is “Infinity”, otherwise - “Finite”.

Task C. Congress of Young Amateurs

Idea: Vitaly Aksyonov
Realization: Vitaly Aksyonov
Analysis: Vitaly Aksyonov

This task is a dynamic programming task. Let's calculate the following array: d [how many places are from the beginning of seating] [how many of them are philosophers] [number of philosopher-mathematician couples sitting together] [types of people in the last two processed places] - the number of ways to settle mathematicians and philosophers, relying only on their types and conditions of the problem. This array is recalculated sequentially when a new place is added. That is, we add a new person, sort out how many philosophers are sitting before him, sort out his type, check that the conditions about the environment and the type of place are fulfilled (for this we keep the types of people in the two previous places), perhaps we have a couple philosopher -mathematics, sitting on the adjacent places.

So far we have not used that people from different countries. Note that if we fixed the assignment of types, we only need to know for counting by country that people from more than one country sit in the positions of the philosopher and mathematician. It should also be noted that the number of assignments of countries depends only on the number of such pairs in the assignment of types. It is easy to get an array c through array d , which returns the number of corresponding type assignments by the number of pairs.

Let p _{n, k} be the number of permutations of n elements such that there are no fixed points among the first k positions. Then it is easy to make sure that the answer will be equal to n ! Σ _i = 1 ⁿ p _{n, i} · c _i . It remains to calculate p . We use the idea to calculate permutations without fixed points, for example, described on wikipedia , and we get the recurrent expression p _{n, k} = (n-1) p _{n-1, k-1} + (k-1) p _{n-2, k- 2} , and p _{n, 0} = n ! and p _{n, 1} = n! - (n - 1) ! ..

Problem D. Decoding

Idea: Dmitry Fillipov
Realization: Nikolay Vedernikov
Analysis: Nikolay Vedernikov

To begin, learn how to solve a problem without modifications. To do this, we use the idea of ​​dynamic programming. The number of ways to get the prefix of length i will be stored in dp [i] . Then let's look at the next initial digit x , if the encrypted digit matches the string from the position i + 1 , then increase the value of dp [i + len (x) ] by dp [i] , where len (x) is the length of the encrypted digit x .

Now we will solve the problem with the changes. Note that, given the restrictions on the coefficients of the trinomial, one digit can turn into a number consisting of no more than three digits. Then, to solve this problem, we use the segment tree. At the vertex, which is responsible for the interval from l to r , we will store 9 values ​​of the number of ways to get the substring c l + 0 ... 2 positions to r - 0 ... 2 positions. How to build such a tree?

• If the segment from l to r is small, then we calculate the values ​​using dynamic programming.
• If the segment is large, then we divide it into two and calculate the corresponding values ​​for them recursively. Now it remains to learn how to count the value in a node, if we know the values ​​in children. First, when the right and left subsegments are in contact, this value on their union is equal to the product of the values ​​on them. If there is a distance between them (that is, a value without one or two characters to the left is taken from the right sub-section, and a value from one or two characters to the right is taken from the left sub-section), then the answer will be equal to the number of ways to get one number between them multiplied by the value right sub-cut and the value on the left-hand cut.

The answer on the whole segment will be in the root of the segment tree. Thus, when we modify one digit, we update the value in the list, and then update the value, going up. Since the depth of the segment tree is O (log ( n )), where n is the length of the string, the total running time is O ( m log ( n )), where m is the total number of queries.

Problem E. Entertaining cryptography

Idea: Vitaly Aksyonov
Realization: Ilya Zban
Analysis: Ilya Zban

In the task you need to count the number of lines that have this hash. The naive solution uses the idea of ​​dynamic programming dp _{i, j} - the number of lines of length i that have hash j . Transitions can be done in Σ , and the solution is obtained in n · m · Σ . This solution can be accelerated to m ² · log n , if we use the binary ascents technique: dp _{i, j} is the number of lines of length 2 ⁱ that have hash j . dp _{i, j} = Σ (x = 0..m-1) dp _{i-1, x · p} ^2i-1 _{% m} · dp _{i-1, jx} . Using the values ​​of this dynamics, we can look at the expansion of n in powers of two, and get an answer to the problem. The last acceleration is that in the transition formula of the previous dynamics one can see nothing more than the product of two polynomials. If we use the fast Fourier transform for this, we obtain the asymptotics of m · log m · log n . This will be the complete solution.