Разбор задач Educational Codeforces Round 11

Revision ru1, by Edvard, 2016-04-09 00:03:25

652A - Габриел и гусеница

Задача предложена пользователем Ali Ibrahim C137.

Заметим, что если есть пара соседних не взаимнопростых чисел, то мы обязаны между ними вставить какое-нибудь число. С другой стороны мы всегда можем вставить число 1.

Решение на С++

Сложность: O(nlogn).

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

Задача предложена пользователем Srikanth Bhat bharsi.

В этой задаче нужно было сделать ровно то, что написано в условии. Никаких хитростей и подвохов.

Решение на C++

Сложность: O(n).

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

Задача предложена пользователем Mohammad Amin Raeisi Smaug.

Назовём отрезок [l, r] хорошим если в нём не более k ноликов. Заметим, что если отрезок [l, r] хороший, то отрезок [l + 1, r] тоже хороший. Таким образом, можно воспользоваться методом двух указателей: один указатель это l, а второй это r. Будем перебирать l слева направо и двигать r пока можем (для этого нужно просто поддерживать количество ноликов в текущем отрезке).

Решение на C++

Сложность: O(n + k).

Tags учебный раунд 11, разбор задач

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English Edvard 2016-04-10 18:47:25 66 Tiny change: ' we have $k-1$\nchoic' -> ' we have $m-1$\nchoic'
en6 English Edvard 2016-04-09 22:13:28 3481
ru7 Russian Edvard 2016-04-09 21:38:53 202
en5 English Edvard 2016-04-09 21:36:44 1097
en4 English Edvard 2016-04-09 21:31:11 1280
en3 English Edvard 2016-04-09 21:28:04 856
en2 English Edvard 2016-04-09 21:17:51 847
ru6 Russian Edvard 2016-04-09 21:09:43 50 Мелкая правка: 'ость: $O(n+k)$.\n\n###' -> 'ость: $O(n)$.\n\n###'
ru5 Russian Edvard 2016-04-09 21:07:54 56
ru4 Russian Edvard 2016-04-09 02:22:21 3780 Мелкая правка: ' log^{2}{n})$.' -
ru3 Russian Edvard 2016-04-09 01:05:26 3539 Мелкая правка: 'mits_{s=1} m^s (m-1)^(n-s) \sum_{k=0' -
en1 English Edvard 2016-04-09 00:38:15 9069 Initial revision for English translation
ru2 Russian Edvard 2016-04-09 00:33:39 1030 Мелкая правка: 'cnt_c-1)}2.\n\n 'cnt_c-1)}2$.\n\n
ru1 Russian Edvard 2016-04-09 00:03:25 2956 Первая редакция (опубликовано)