Editorial of Educational Codeforces Round 7

Revision en5, by Edvard, 2016-02-11 01:25:11

622A - Infinite Sequence

Let's decrease n by one. Now let's determine the block with the n-th number. To do that let's at first subtract 1 from n, then subtract 2, then subtract 3 and so on until we got negative n. The number of subtractions will be the number of the block and the position in the block will be the last nonnegative number we will get.

С++ solution

Complexity: .

622B - The Time

In this problem we can simply increase a times the current time by one minute (after each increasing we should check the hours and the minutes for overflow).

Another solution is to use the next formulas as the answer: .

C++ solution 1

C++ solution 2

Complexity: O(a) or O(1).

622C - Not Equal on a Segment

This problem is a simplified version of the problem suggested by Mohammad Nematollahi Deemo.

This problem can be solved differently. For example you can use some data structures or sqrt-decomposition technique. But it is not required. We expected the following simple solution from the participants. Let's preprocess the following values pi — the position of the first element to the left from the i-th element such that ai ≠ api. Now to answer to the query we should check if ar ≠ x then we have the answer. Otherwise we should check the position pr.

C++ solution

Complexity: O(n).

622D - Optimal Number Permutation

This problem is suggested by Aleksa Plavsic allllekssssa.

Let's build the answer with the sum equal to zero. Let n be even. Let's place odd numbers in the first half of the array: the number 1 in the positions 1 and n, the number 3 in the positions 2 and n - 1 and so on. Similarly let's place even numbers in the second half: the number 2 in the position n + 1 and 2n - 1, the number 4 in the positions n + 2 and 2n - 2 and so on. We can place the number n in the leftover positions. We can build the answer for odd n in a similar way.

Easy to see that our construction will give zero sum.

C++ solution

Complexity: O(n).

Tags education round 7, editorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English Edvard 2016-02-11 23:46:39 4 Tiny change: 'd modulo $10^9+7$).' -> 'd modulo $MOD=10^9+7$).'
ru8 Russian Edvard 2016-02-11 23:46:22 10
en9 English Edvard 2016-02-11 23:45:57 10
ru7 Russian Edvard 2016-02-11 23:45:25 24 Мелкая правка: 'циклом за линейное время). Если $n' -> 'циклом за $O(klogk)$). Если $n'
en8 English Edvard 2016-02-11 02:07:12 1281
ru6 Russian Edvard 2016-02-11 01:59:16 43
en7 English Edvard 2016-02-11 01:47:06 1130 Tiny change: '{z_{i+1}}=\nmax(d_{z_{' -
en6 English Edvard 2016-02-11 01:26:30 3 Tiny change: 's problem is suggeste' -> 's problem was suggeste'
en5 English Edvard 2016-02-11 01:25:11 79
en4 English Edvard 2016-02-11 01:23:26 700
en3 English Edvard 2016-02-11 01:11:17 460
en2 English Edvard 2016-02-11 00:52:17 446
ru5 Russian Edvard 2016-02-11 00:38:52 2033 Мелкая правка: 'rod\limits{j=1, j\ne' -
ru4 Russian Edvard 2016-02-11 00:04:13 989
en1 English Edvard 2016-02-10 23:45:06 696 Initial revision for English translation
ru3 Russian Edvard 2016-02-10 23:40:09 649
ru2 Russian Edvard 2016-02-10 23:23:31 600 Мелкая правка: 'равентсво с числом $x$, если' -
ru1 Russian Edvard 2016-02-10 23:13:44 883 Первая редакция (опубликовано)