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

On Saturday, May 24, the third qualifying round of the RCC 2014 took place. 5483 people registered for the round, more than 1500 took part, 893 of them sent at least one decision.

Prishchenko Bogdan (LeBron), student of the Lviv National University. Ivan Franko, the first at 2:25 minute solved the problem A (Triangles). Problem C (Origami) at 4:44 minutes was first solved by Yuldashev Marat (snowbear), task C (Mitya and Count) was first at 10:34 minutes solved by Ahmedov Maxim (Zlobober), the correct solution to problem D (Prizes) at 26:45 minute sent Kopeliovich Sergey (Burunduk1), and the last task E (Crypto-resistant keys) was solved most quickly by Ponomarev Pavel (pperm) at 54:38 minute.
')
According to the results of the 3rd qualification round, there was not a single disqualification for cheating, and the 200 best sports programmers went into the qualifying round.

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

We remind you that in order to take part in the Russian Code Cup, you need to register on the site (registration will be open before the start of the last qualifying round).

Back in the run-up to the third round, we updated the compiler versions of almost all the programming languages ​​used in the RCC. Added the ability to send solutions to C ++ 11 under GNU C ++ (Visual C ++ 2013 and so supports C ++ 11) and added Java 8 (Java 7 still remains). You can see the current versions of compilers and compilation lines on the championship rules page < www.russiancodecup.ru/rules >.

Problem A. Triangles .
Idea: Andrei Stankevich.
Realization: Anna Malova.
Analysis: Anna Malova.

The task is to determine the number of triangles of each type, which can be made up of four segments.

Let's look through all possible triples of segments. Of the three segments, you can make a triangle 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 right-angled, if c2 <a2 + b2 is acute-angled, and if c2> a2 + b2 is obtuse

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

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

To do this, we iterate over all x-divisors of 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.

Runtime per 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 a rib cactus. If it did not turn out to be such, then there will necessarily be an even cycle. Since this is a cactus, then the number of cycles is m - (n - 1). And since each cycle contains at least 3 vertices, then 3 · (m - (n - 1)) ≤ m. From this we obtain 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 at 1 vertex, and for odd n, almost the same, but another pendant vertex is connected by an edge with any other.

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

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

In the first group, children get n candies, in the second - n-1 candies, ..., in the last group - 1 candy. Then we can add one sweet 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 chose the initial distribution, we can immediately subtract n · a1 + ... + 1 · an 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 task about a backpack.

O (nd) operation time.

Problem E. Crypto-resistant keys .
Idea: Vitaly Demyanyuk.
Realization: Vitaly Demyanyuk.
Analysis: Vitaly Demyanyuk.

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

We represent v in the form p1q1p2q2 ... pkqk, qi> 0, where p1, p2, ..., pk are prime numbers. For v to belong to S, for each i, 1 ≤ i ≤ k, there must be 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 LCM (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) ). Let ci be equal to the greatest common divisor of the 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 GCD and LCM operations).

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