534A - Exam

Is easy to see that k = n with n ≥ 4. There are many algorithms that can be used to build a correct sequence of length n with n ≥ 4. For example, students can be seated from left to right with the first to seat students with odd numbers in decreasing order starting with largest odd number. Then similary to seat students with even numbers. In this sequence the absolute difference between two adjacent odd (or even) numbers equal to 2. And the difference between odd and even numbers greater or equal 3 (because n ≥ 4).

Cases n = 1, n = 2, n = 3 are considered separately. Solution complexity — O(n).

Jury's solution: 10691992

534B - Covered Path

It can be easily proved that every second i (0 ≤ i ≤ t - 1) the maximum possible speed is . You can iterate through i from 0 to t - 1 and the values of v_i.

Solution complexity — O(t).

Also you can use next fact. If current speed equal to u and left t seconds then there is a way to get v₂ speed at the end only if |u - v₂| ≤ t·d. Consider this criteria, one can simply try to change speed to maximum possible (from u + d down to u - d), choosing first giving a way to reach the end of the path.

Jury's solutions: 10692136 и 10692160

534C - Polycarpus' Dice

Solution uses next fact. With k dice d₁, d₂, ..., d_k you can dial any sum from k to . This is easily explained by the fact that if there is a way to get the amount of s > k, then there is a way to dial the sum equal s - 1, which is obtained by decreasing the value of one die by one.

Let's denote sum of all n dice as . Fix the dice d_i (value on it denote as x (1 ≤ x ≤ d_i). Using the other dice we can select s (n - 1 ≤ s ≤ S - d_i). We know that average value s + x = A, and n - 1 ≤ A - x ≤ S - d_i, giving A - (n - 1) ≥ x ≥ A - (S - d_i).

Using facts described above, for every dice one can calculate a possible values segment, giving the answer for the count of impossible values of that dice. Solution asymptotic — O(n).

Jury's solution: 10692192

534D - Handshakes

From here we will not consider resulting permutation but correct handshakes sequence (rearranged given sequence). Formally, the sequence of handshakes count a_i is correct if and only if a_i + 1 ≤ a_i + 1 and a_i + 1 ≡ a_i + 1 ± od{m} and a₁ = 0. To form correct sequence, we can use following greedy algorithm.

First, place 0 as the first number. Next, for every following number a_i + 1 we will select maximum possible number from numbers left, matching above constraints (in simple case it will be a_i + 1, otherwise we will check if a_i - 2 left, e.t.c).

The solution may divide given sequence into three parts (depending on modulo by 30), and using, for example, data structure ''set'', quickly find the next number to place into resulting sequence. Such solution will work in . There is also possible to get O(n) asymptotics using path compression technique.

Jury's solution: 10692252

534E - Berland Local Positioning System

Suppose that the bus started his way from the stop with number 1 and modulate its way during m stops. For every stop we will calculate how many times this stop was visited by the bus at that way. Check if that counts match counts in the input and update the answer if needed. Then we will try to move the start stop to stop with number 2. It's easy to see that the last visited stop (as long as bus must visit m stops) will move to the next stop. So we need to modulate bus way to another one stop from first stop and from last stop to change the starting stop to another (it makes maximum of four counts to be updated). It could be done in O(1) time.

This way we need to move starting stop to every variant (its count is equal to 2n - 2) and for every variant update the answer if needed. Average solution works in O(n) time.

Jury's solution: 10705354

534F - Simplified Nonogram

This task has several solution algorithms.

One of them could be described next way. Let's divide n × m field into two parts with almost same number of columns (it will be n × k and n × (m - k)). Let's solve the puzzle for every part of the field with brute-force algorithm (considering column constraints on number of blocks) with memorization (we do not need same solutions with same number of blocks in rows). Then we will use meet-in-the-middle approach to match some left part with right part to match constraints on n × m field.

Another solution could be profile dynamic programming, where the profile is the number of blocks in the row.

Jury's solution uses both ideas: 10705343