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

Правка ru7, от Edvard, 2016-04-09 21:38:53

660A - Взаимнопростый массив

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

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

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

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

660B - Рассадка в автобусе

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

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

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

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

660C - Сложный процесс

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

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

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

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

660D - Количество параллелограммов

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

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

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

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

660E - Различные подмножества по всем кортежам

Задача предложена пользователем 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.

660F - Медведь и боулинг 4

Задача предложена пользователем Kamil Debowski Errichto.

Далее приводится разбор моего решения. Также вы можете посмотреть разбор от автора задачи в английском треде.

Применим метод разделяй и властвуй. Рассмотрим отрезок [l, r] и найдём в нём подотрезок с максимальной взвешенной суммой. Для этого разобьём отрезок на две части [l, md - 1] и [md, rg], где . Согласно методу разделяй и властвуй посчитаем рекурсивно ответ, если он лежит целиком в левой или правой половине. Теперь нужно учесть отрезки, пересекающие середину. Рассмотрим некоторый отрезок [i, j], i < md, md ≤ j. Взвешенная сумма на ней равна: , где --- взвешенная сумма в подотрезке [i, md], — взвешенная сумма на подотрезке [md + 1, r], а srj — просто сумма на подотрезке [md + 1, r]. Знак  ×  применяется в смысле геометрического псевдовекторного произведения. Таким образом, у нас есть набор векторов вида (md - i, 1) и некоторый набор точек и для каждого вектора первого набора нужно найти точку из второго набора, максимизирующую значение векторного произведения. Это легко сделать, построив выпуклую оболочку по множеству точек и далее, двигая указатель по выпуклой оболочке.

Обратите внимание, что в данном решении есть проблема переполнения значений векторного произведения. Эту проблему можно обойти, если сначала сравнивать значение векторного произведения в типе long double или double и только потом в типе long long. Оригинальное решение автора задачи не имеет такой проблемы.

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

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

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