К каждой задаче присутствует challenge — бонусная задача на тему, которую можно порешать just for fun и обсудить в комментариях. =)

496A - Минимальная сложность

Переберем все элементы, которые можем выкинуть, пройдем по оставшимся элементам и посчитаем максимальную разность среди соседних. Это решение имеет сложность O(n²). Можно заметить, что при удалении элемента ответ либо не поменялся, либо стал равен разности тех элементов, которые являлись соседями только что удаленного, поэтому ответ можно получить за O(1), а итоговое решение будет иметь сложность O(n). Ограничения позволяли сдать любое из этих решений или даже менее эффективное.

Challenge: пусть мы удаляем не один элемент, а k любых элементов (первый и последний, как и раньше, удалять нельзя). Какую минимальную максимальную разность между соседними элементами мы можем получить? Решите задачу в ограничениях 1 ≤ k ≤ n - 2, n ≤ 10⁵, a_i ≤ 10⁹.

496B - Секретный код

Заметим, что нам неважно, в каком порядке применяются операции: мы можем сперва выполнить все сдвиги, а затем все прибавления. После n сдвигов мы получаем исходную последовательность, поэтому достаточно рассмотреть только варианты, где сдвиги выполняются менее n раз. Аналогично, после десяти прибавлений единицы ко всем цифрам получим исходную последовательность, поэтому рассмотрим только варианты, где прибавления выполняются менее десяти раз. Для каждого из 10n вариантов определим результат применения всех операций; сохраним лучший результат и для каждого из вариантов сравним с лучшим. Сравнения осуществляются за O(n) операций, поэтому итоговое количество элементарных операций имеет порядок 10n². От константы 10 можно избавиться, если заметить, что при фиксированном сдвиге первую цифру всегда выгодно сделать нулем, и это однозначно определяет количество прибавлений; однако, чтобы сдать задачу, эта оптимизация не требовалась.

Challenge: можете ли вы решить задачу за время ? O(n)?

496C - Удаление столбцов/497A - Удаление столбцов

Посмотрим на первый столбец таблицы. Если буквы в нем не упорядочены по алфавиту сверху вниз, его нельзя оставить ни в каком корректном варианте оставить некоторые столбцы. С другой стороны, пусть буквы в первом столбце упорядочены, но в ответ мы его не взяли. Добавим его к ответу; несложно видеть, что в новом варианте оставить столбцы все строки также упорядочены сверху вниз по алфавиту.

Будем рассматривать столбцы слева направо. Если мы попробовали добавить текущий столбец к ответу и лексикографический порядок строк где-то нарушился, мы обязаны его удалить; если же все в порядке, возьмем его в ответ. Рассуждение, аналогичное предыдущему абзацу, показывает, что такой жадный алгоритм приводит к оптимальному (и более того, единственному среди оптимальных) ответу. Итоговая сложность — O(n²).

Challenge: сколько существует таблиц n × m, для которых ответ на эту задачу равен k? Придумайте как можно более оптимальное решение.

496D - Игра в теннис/497B - Игра в теннис

Фиксируем t; теперь мы можем проэмулировать ход партии и убедиться, что запись является корректной, а также определить соответствующее s; выведем все подходящие пары s и t. Такое решение работает за O(n²), попробуем его соптимизировать.

Если после окончания очередного сета мы обработали k розыгрышей, то позицию окончания следующего сета можно определить так: найти t-ую позицию после k-ой, в которой записано 1, аналогично, найдем t-ую позицию, содержащую 2. Если позиция t-ой единицы встретилась раньше, то следующий сет выигрывает первый игрок, и позиция окончания сета совпадает с позицией t-ой единицы; аналогично разбирается случай, если раньше идет t-ая двойка. Если партия еще не кончилась, но в оставшейся части и единиц, и двоек менее t, то запись некорректна. Позицию t-ой единицы или двойки после заданной позиции можно определять за бинпоиском, или за O(1) при помощи предподсчитанного массива позиций.

Теперь заметим, что для данного t партия из n розыгрышей не может содержать больше n / t сетов, поскольку каждый из них содержит как минимум t розыгрышей. Если мы просуммируем количество сетов в партии по всем возможным t, мы получим не более (известная сумма гармонического ряда). В зависимости от способа обработки одного сета итоговая сложность составляет либо ; любой из этих способов с запасом укладывается в ограничение.

Очевидно, что для каждого t существует не более одного варианта s; однако, для данного s может существовать более одного варианта t. Первый тест с таким случаем — претест 12. В условии требуется выводить ответ в лексикографическом порядке пар; здесь легко допустить ошибку и вывести пары с равными s по убыванию t (если в конце просто переворачивать массив).

Challenge: при подготовке этой задачи я столкнулся с тем, что не могу построить тест с большим количеством пар в ответе; в тестах к задаче максимальное количество — 128 = количество делителей числа 83160. Сможете ли вы побить этот рекорд? Хвастайтесь в комментариях, сколько пар вы умеете получать при n ≤ 10⁵; если у вас есть соображения, как оценить максимальное количество пар теоретически, тоже прошу делиться.

496E - Распределение партий/497C - Распределение партий

Отсортируем все партии и всех актеров вместе по возрастанию нижней границы (при равенстве сначала идут все актеры, потом все партии); пойдем в этом порядке по возрастанию нижней границы. Будем поддерживать множество актеров, которые уже <<начались>>, т.е. встретились в этом порядке раньше; если мы встретили актера, добавим его в это множество. Если мы встретили партию (a_j, b_j), из множества допустимых актеров нам нужно выбрать такого, у которого d_i ≥ b_j (требование c_i ≤ a_j гарантируется тем, что i-ый актер встретился раньше, чем j-ая партия); если таких актеров в множестве нет, мы не можем получить ответ. Если таких актеров несколько, нам выгоднее брать того из них, у которого d_i минимально (интуитивно, он нам в дальнейшем меньше пригодится). Сопоставим текущую партию выбранному актеру и уменьшим его k_i на единицу; если теперь k_i = 0, мы больше не можем пользоваться этим актером и должны выкинуть его из множества.

Чтобы уложиться в ограничения, множество текущих актеров приходится поддерживать в эффективной структуре данных (например, std::set или декартово дерево). Сложность итогового решения .

Challenge: пусть каждая песня присутствует в количестве q_j (1 ≤ q_j ≤ 10⁹), и каждой копии надо сопоставить своего актера. можете ли вы решить задачу в тех же ограничениях (поскольку ответ теперь очень большой, достаточно проверить его существование)?

497D - Шестерни

Если в какой-то момент произошло столкновение, это значит, что какая-то вершина одного из многоугольников попала на одну из сторон другого многоугольника. Рассмотрим систему отсчета, в которой многоугольник A неподвижен. В этой системе многоугольник B перемещается параллельно сам себе, и каждая его точка описывает окружность. Если мы пересечем все окружности, которые описывают вершины B, со всеми сторонами A, мы можем проверить, попадает ли какая-то из вершин B на границу A. Аналогично, перейдем в систему отсчета, связанную с B, и проверим, попадает ли вершина A на границу B. Ограничения на координаты позволяют выполнять проверки абсолютно точно.

Другой подход к тому же самому по сути решению: пусть в системе отсчета, связанной с A, произошло столкновение. Тогда выполнено векторное равенство x + y = z, где z — вектор с началом в точке P и концом где-то на границе A, x — вектор с началом в точке Q и концом где-то на границе B, y — вектор с началом в P и концом где-то на окружности с центром в P, проходящей через Q. Если переписать это равенство как y = z - x, можно увидеть, что все возможные значения z - x пробегают сумму Минковского многоугольников A и зеркального отражения B (с точностью до сдвига), y пробегает известную окружность. Сумму Минковского можно представить в виде объединения nm параллелограммов, каждый из которых — сумма двух сторон разных многоугольников; в конечном итоге, пересечем все границы всех параллелограммов с окружностью.

Сложность обоих решений — O(nm). Как указано выше, существует решение в целых числах; однако, маленькие ограничения на координаты не позволяют легко свалить решения с вещественной арифметикой. Также велик был соблазн написать неточное численное решение; мы постарались отсечь все такие решения, и в итоге ни одно из них не зашло. =)

Многие имели проблемы с 8-ым претестом. Он выглядит так (левая спираль вращается вокруг левой точки, правая вокруг правой):

Challenge: пусть мы хотим завалить решение с вещественной арифметикой. Построим тест, в котором многоугольники не сталкиваются, но проходят очень близко друг к другу. Какое минимальное положительное расстояние мы можем получить в заданных ограничениях на количество вершин и координаты?

497E - Подпоследовательности возвращаются

Пусть дана какая-то строка. Как посчитать количество ее различных подпоследовательностей? Будем приписывать символы к концу по одному и считать, сколько новых подпоследовательностей появилось. Пусть к строке s приписали символ c; в строке s + c на символ c заканчивается столько же подпоследовательностей, сколько их было всего в строке s. Если их прибавить к количеству подпоследовательностей s, каждая подпоследовательность s + c учтется по одному разу, кроме тех, которые заканчиваются на c и присутствовали в строке s: они учтутся дважды. Это приводит к следующему решению: будем хранить, сколько последовательностей заканчивается на каждый из возможных символов — cnt_c, тогда при добавлении символа c значение cnt_c надо заменить на сумму всех cnt плюс один (за пустую последовательность); ответ для всей строки равен сумме всех cnt (плюс один, если нам надо учесть пустую последовательность). Например, рассмотрим первые несколько символов строки Туе-Морса:

• ε — (0, 0)

• 0 — ( 0 + 0 + 1 = 1, 0)

• 01 — (1, 1 + 0 + 1 = 2)

• 011 — (1, 1 + 2 + 1 = 4)

• 0110 — ( 1 + 4 + 1 = 6, 4)

• ...

Легко видеть, что если значения cnt на данном шаге выписать как координаты вектора, и добавить к ним координату, тождественно равную 1, то приписывание одного символа к строке влияет на вектор как умножение на матрицу; естественным образом сопоставим каждой строке описанную матрицу.

Рассмотрим префикс последовательности a_i длины k^m. Если разделить его на k кусков длины k^m - 1, окажется, что i-ый из этих кусков может быть получен из 0-го прибавлением ко всем элементам i по модулю k. Будем насчитывать матрицы для префиксов длины k^m, а также для всех строк, получающихся из префикса прибавлением ко всем его элементам какого-то числа x; обозначим такую матрицу за A_m, x.

Легко видеть, что при m > 0 . Эта формула позволяет нам вычислить A_m, x для всех и x от 0 до k - 1 за время . Теперь, имея все A_m, x, мы легко можем перемножить некоторые из них в нужном порядке, чтобы получить матрицу для префикса a_i длины n.

К сожалению, пока что решение не укладывается в ограничения по времени. Один из способов получить решающее ускорение таков: заметим, что в формуле произведение можно разбить следующим образом: A_{m - 1, x}... A_{m - 1, k - 1} × A_{m - 1, 0}... A_{m - 1, x - 1} (если x = 0, вторая часть произведения пуста). Посчитаем для всех x произведения <<префиксов>> и <<суффиксов>> набора A_m, x: P_m, x = A_m, 0... A_{m, x - 1}, S_m, x = A_m, x... A_{m, k - 1}. Теперь A_m, x = S_{m - 1, x}P_{m - 1, x}. Теперь вычисление A_m, x для всех x при выбранном m сводится к вычислению P_{m - 1, x}, S_{m - 1, x} за O(k) умножений матриц, после чего каждый элемент A_m, x вычисляется за одно перемножение. Таким образом, наше решение теперь работает за , что укладывается в ограничения с запасом.

Challenge: решите задачу при k ≤ 100.