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

Правка ru2, от Edvard, 2016-04-09 00:33:39

660A - Co-prime Array

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

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

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

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

660B - Seating On Bus

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

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

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

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

660C - Hard Process

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

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

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

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

660D - Number of Parallelograms

Задачу предложена участником Sadegh Mahdavi smahdavi4.

Как известно диагонали параллелограмма делят друг друга пополам. Переберём пару точек a, b и рассмотрим середину отрезка : c = (a + b) / 2. Для всех середин отрезков посчитаем число cntc — количество пар точек, с этой серединой. Легко видеть, что ответ это .

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

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

Теги учебный раунд 11, разбор задач

История

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