Analysis of the tasks of the third qualification round of the Russian Code Cup 2014

The third qualifying round of RCC 2014 took place on Saturday, May 24th. 5483 people registered to participate in the round, more than 1500 took part, of which at least one decision was sent by 893 participants.

Prishchenko Bogdan (LeBron), student of Lviv National University. Ivan Franko, the first at 2:25 minutes to solve the problem A (Triangles). Problem B (Origami) at 4:44 minutes was first solved by Yuldashev Marat (snowbear), task C (Mitya and Count) was first solved at 10:34 minutes by Maxim Ahmedov (Zlobober), the correct solution to problem D (Prizes) at 26:45 minutes sent by Sergey Kopeliovich (Burunduk1), and the last task E (Cryptographic keys) was solved most quickly by Pavel Ponomarev (pperm) at 54:38 minutes.

According to the results of the 3rd qualification round, there were no disqualifications for cheating, and the 200 best sports programmers went into the qualifying round.

Participants who have not qualified during the last three qualifying rounds still have the opportunity to qualify for the round by taking part in the fourth qualifying round, which will be held June 1 at 13:00 Moscow time.

We remind you that 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 last qualification round).

Already on the eve of the third round, we updated the compiler versions of almost all the programming languages ​​used in RCC. We added the ability to send solutions to C ++ 11 under GNU C ++ (Visual C ++ 2013 already supports C ++ 11) and added Java 8 (Java 7 also remains for now). You can look at actual versions of compilers and compilation lines on the championship rules page < www.russiancodecup.ru/rules >.

Problem A. Triangles .
Idea: Andrey Stankevich.
Implementation: Anna Malova.
Analysis: Anna Malova.

In the problem, it is required to determine the number of triangles of each type, which can be composed of four segments.

We go over all the possible triples of segments. A triangle can be made up of three segments if the triangle inequality holds, that is, the sum of any two sides is greater than the length of the third side.

Consider the segments a, b, c in increasing order of length. If the equality c2 = a2 + b2 holds, then the triangle is rectangular, if c2 <a2 + b2 is acute-angled, and if c2> a2 + b2 is obtuse,

Problem B. Origami .
Idea: George Korneev.
Implementation: Nikolay Vedernikov.
Analysis: Nikolay Vedernikov.

In the problem, it is required to check whether in the rectangle a on b there exists a sub rectangle of area S whose sides are parallel to the original.

To do this, iterate over all x-divisors of the number S and check whether x ≤ a and S ⁄ x ≤ b. If there exists at least one such pair x and S ⁄ x satisfying the constraints, then a solution exists.

Operating time for one test case O (sqrt (S)).

Problem C. Mitya and Count .
Idea: Jury.
Implementation: Vitalik Aksyonov.
Analysis: Vitalik Aksyonov.

The first observation is as follows: the graph must be an edge cactus. If it did not work out like that, then there is sure to be an even cycle. Since this is a cactus, the number of cycles is m - (n - 1). And since each cycle contains at least 3 vertices, then 3 · (m - (n - 1)) ≤ m. It follows that the maximum number of edges is 3 · (n - 1) / 2.

For odd n, this is a mill, that is, a set of cycles of length 3 intersecting along 1 vertex, and for odd n it is almost the same, but another hanging vertex is connected by an edge to any other.

Task D. Prizes .
Idea: Vitalik Aksyonov.
Implementation: Vitalik Aksyonov.
Analysis: Vitalik Aksyonov.

We know that the number of candies given to participants should decrease depending on the group number. It is easy to make sure that any satisfying partition of sweets can be represented in the following way:

In the first group, children receive n sweets, in the second - n-1 sweets, ..., in the last - 1 sweets. Then we can add one candy to all the children on the group prefix. This means that we can choose the number p and increase ai by one for any i ≤ p.

Since we selected the initial distribution, n · a1 + ... + 1 · an can be immediately subtracted from the total number of candies. It is easy to see that the distribution operation subtracts bp = a1 + ... + ap. That is, we need to check whether we can represent d in the form of some sum b1, ..., bn, and this is a standard backpack problem.

Runtime O (nd).

Problem E. Cryptographic keys .
Idea: Vitaliy Demyaniuk.
Implementation: Vitaliy Demyaniuk.
Analysis: Vitaliy Demyanjuk.

Given the set of numbers a1, a2, ..., an. He was closed in relation to the operations of NCD and NOC. It is required to find out whether a given number v belongs to a closed set S.

We represent v in the form p1q1p2q2 ... pkqk, qi> 0, where p1, p2, ..., pk are primes. For v to belong to S, it is necessary that for every i, 1 ≤ i ≤ k, there exist j, 1 ≤ j ≤ n, such that piqi ∣aj and piqi + 1 ∤aj. This fact follows from the fact that we can represent any number in the form of NOCs (GCD (...), GCD (...), ..., GCD (...)), since min (a, max ( b, c)) = max (min (a, b), min (a, c)) and max (a, min (b, c)) = min (max (a, b), max (a, c) ) We set ci equal to the greatest common divisor of numbers aj such that piqi ∣aj. If all ci divide v, then v belongs to S. It can be obtained as the least common multiple of all ci. Otherwise, v does not belong to S (this follows from the properties of the operations of GCD and LCL).

Operating time O (nk + sqrt (v)), where k is the number of prime divisors of v.