Editorial of Educational Codeforces Round 10

Revision en2, by Edvard, 2016-03-26 21:37:54

652B - z-сортировка

The problem was suggested by Smaug.

Easy to see that we can z-sort any array a. Let be the number of even positions in a. We can assign to those positions k maximal elements and distribute other n - k elements to odd positions. Obviously the resulting array is z-sorted.

C++ solution

Complexity: O(nlogn).

652C - Враждебные пары

This is one of the problems suggested by Bayram Berdiyev bayram, Allanur Shiriyev Allanur, Bekmyrat Atayev Bekmyrat.A.

Let's precompute for each value x its position in permutation posx. It's easy to do in linear time. Consider some foe pair (a, b) (we may assume posa < posb). Let's store for each value a the leftmost position posb such that (a, b) is a foe pair. Denote that value as za. Now let's iterate over the array a from right to left and maintain the position rg of the maximal correct interval with the left end in the current position lf. To maintain the value rg we should simply take the minimum with the value z[lf]: rg = min(rg, z[lf]). And finally we should increment the answer by the value rg - lf + 1.

C++ solution

Complexity: O(n).

652D - Вложенные отрезки

The problem was suggested by Alexey Dergunov dalex.

This problem is a standard two-dimensional problem that can be solved with one-dimensional data structure. In the same way a lot of other problems can be solved (for example the of finding the maximal weighted chain of points so that both coordinates of each point are greater than the coordinates of the predecessing point). Rewrite the problem formally: for each i we should count the number of indices j so that the following conditions are hold: ai < aj and bj < aj. Let's sort all segments by the left ends from right to left and maintain some data structure (Fenwick tree will be the best choice) with the right ends of the processed segments. To calculate the answer for the current segment we should simple take the prefix sum for the right end of the current segment.

So the condition ai < aj is hold by sorting and iterating over the segments from the right to the left (the first dimension of the problem). The condition bj < bj is hold by taking the prefix sum in data structure (the second dimension).

C++ solution

Complexity: O(nlogn).

Tags education round 10, editorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English Edvard 2016-04-27 18:10:38 50 Tiny change: 'on $b_j < b_j$ is hol' -> 'on $b_j < a_j$ is hol'
en9 English Edvard 2016-03-27 16:06:27 50 Tiny change: 'xity: $O(n)$.\n\n###' -> 'xity: $O(n+m)$.\n\n###'
ru7 Russian Edvard 2016-03-27 16:06:01 50 Мелкая правка: 'ость: $O(n)$.\n\n###' -> 'ость: $O(n+m)$.\n\n###'
en8 English Edvard 2016-03-27 16:03:49 52 Tiny change: 'se and $a > b$ &mdash' -> 'se and $a \le b$ &mdash'
ru6 Russian Edvard 2016-03-27 16:03:35 52 Мелкая правка: 'нено и $a > b$ &mdash' -> 'нено и $a \le b$ &mdash'
ru5 Russian Edvard 2016-03-27 15:58:06 51 Мелкая правка: 'ac{h_2-h_1}{12(a-b)}' -> 'ac{h_2-h_1-8a}{12(a-b)}'
en7 English Edvard 2016-03-27 15:56:28 51 Tiny change: 'ac{h_2-h_1}{12(a-b)}' -> 'ac{h_2-h_1-8a}{12(a-b)}'
ru4 Russian Edvard 2016-03-26 22:10:56 195
en6 English Edvard 2016-03-26 22:07:39 4829
en5 English Edvard 2016-03-26 21:54:41 44 Tiny change: 'mary="Not short C++' -> 'mary="Not too short C++'
en4 English Edvard 2016-03-26 21:52:57 3626
ru3 Russian Edvard 2016-03-26 21:43:57 50 Мелкая правка: '\n2. Первой условие н' -> '\n2. Первое условие н'
en3 English Edvard 2016-03-26 21:43:25 1057
en2 English Edvard 2016-03-26 21:37:54 62
en1 English Edvard 2016-03-26 13:36:55 4497 Initial revision for English translation
ru2 Russian Edvard 2016-03-26 13:32:24 13014 Мелкая правка: 'за время $r\mod m$. З' -> 'за время $t\mod m$. З' (опубликовано)
ru1 Russian Edvard 2016-03-25 17:00:25 1081 Первая редакция (сохранено в черновиках)