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

Revision ru3, by Edvard, 2016-04-09 01:05:26

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).

652E - Pursuit For Artifacts

Задача предложена пользователем Lewin Gan Lewin.

Рассмотрим некоторую подпоследовательность длины k > 0 (пустые подпоследовательности можно учесть отдельно, прибавив в конце к ответу число mn) и посчитаем количество последовательностей в которых она будет учтена. Нам это нужно сделать аккуратно, чтобы всё посчитать ровно по одному разу. Пусть x1, x2, ... , xk это наша подпоследовательность. Тогда в исходной последовательности перед элементом x1 могли находиться ещё числа, но число x1 не могло встретиться (поскольку мы хотим всё посчитать по разу, варианты когда x1 уже встречалось нам не нужно учитывать). Таким образом, у нас (m - 1) вариант для каждого из чисел перед x1. Аналогичо, между числами x1 и x2 могут находиться некоторые числа (но не может находиться число x2). И так далее. После числа xk может находиться ещё некоторое количество чисел (пусть их j штук), причём на них не накладывается никаких ограничений (то есть m вариантов для каждого числа). Мы зафиксировали, что в конце стоит j чисел, значит n - k - j чисел нужно распределить между числами перед x1, между x1 и x2, \ldots , между xk - 1 и xk. Легко видеть, что это можно сделать способами (это просто биномиальный коэффициент с повторениями). Количество последовательностей x1, x2, ... , xk, конечно, равно mk. Таким образом, ответ это . Последнюю сумму легко преобразовать к виду . Заметим, что последняя внутренняя сумма легко суммируется с помощью известной формулы параллельного суммирования: . Таким образом, ответ равен: . Можно далее сворачивать сумму, чтобы получить логарифмическое решение (закнутую формулу), но в задаче это не требовалось.

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

Сложность: O((n + m)log MOD), где MOD = 109 + 7.

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 Первая редакция (опубликовано)