624A - Спасти Люка

За единицу времени ширина полосы уменьшается на v₁ + v₂. Это значит, что она уменьшится от L до d за . Тот момент, когда ширина стала равна d — последний, когда Люк еще живет, значит t — это ответ.

624B - Составить строку

Отсортируем кол-ва букв по невозрастанию.
Очередную букву берем столько раз, сколько можно, но строго меньше, чем предыдущую. Не забываем, что если предыдущая буква не взята вообще, то все следующие тоже взяты не будут.

623A - Граф и строка

Заметим, что вершины "b" связаны со всеми остальными вершинами в графе. Найдём все подобные вершины и отметим их символом "b". После этого найдём любую непомеченную вершину V, пометим её символом "a". Все непомеченные вершины, которые связаны с V, тоже должны быть помечены символом "a". Все остальные непомеченные вершины в графе отметим символом "c".

Теперь нужно проверить корректность графа, т.е. убедиться, что все вершины "a" связаны только между собой и с вершинами "b". Аналогично проверим все вершины "c".

623B - НОД массива

Хотя бы один из концов (a₁ или a_n) изменится не больше, чем на 1. А это значит, что если gcd будет не равен 1, то он будет делиться на один из простых делителей одного из чисел a₁ - 1, a₁, a₁ + 1, a_n - 1, a_n, a_n + 1. Переберём это простое.

Пусть фиксировано простое p, тогда для каждого числа мы знаем, что оно, либо уже делится на p, либо его можно поправить за b, либо оно должно входить в массив-результат.

После этого, можно запустить динамику dp[кол-во чисел, которое рассмотрели][отрезок для изменения за a еще не начался/начался/закончился] = минимальная стоимость

Итоговая сложность O(Nd) = O(NlogN), где d — количество простых делителей для перебора

623C - Электрические заряды

Рассмотрим сперва отдельно случаи, когда все точки спроецированы на одну ось (Тогда ответ — разница между максимумом и минимумом по одной из координат)

Далее, рассмотрим самую левую и самую правую точку из тех, что спроецированы на ось x. Пусть их координаты x_L и x_R. Заметим, что все точки с координатами x_L ≤ x ≤ x_R также можно спроецировать на ось x, это не увеличит диаметр. Таким образом, если отсортировать точки по x-координате, можно считать, что точки спроецированные на ось x образуют подотрезок (непрерывный подмассив).

Запустим бинарный поиск, теперь нам нужно проверять, что можно спроецировать точки так, что диаметр <= M.

Зафиксируем самую дальнюю от 0 по x-координате точку, которая в итоге будет спроецированной на ось x. Она может быть слева или справа от нуля. Случаи будут симметричны, для примера рассмотрим случай, когда эта точка меньше 0. Пусть ее координата равна x_L < 0. Заметим, что все точки, для которых 0 ≤ x - x_L ≤ M и |x| ≤ |x_L| можно спроецировать на ось x и от этого диаметр не увеличится, а все оставшиеся нужно спроецировать на ось y. Среди оставшихся точек нужно найти минимум и максимум по y координате и тогда ответ "можно", если расстояние между этими точками не превосходит M и расстояние от них до (x_L, 0) не превосходит M.
Теперь предподсчитаем минимум и максимум y координат на префиксе и суффиксе все точек. Будем перебирать левую границу отрезка точек спроецированных на x, а правую будем искать бинпоиском или поддерживать методом двух указателей.

Таким образом одна проверка работает за O(M) или , и общая сложность или .

623D - День Рождения

Обозначим q_i = 1 - p_i.

Идея решения: сначала нужно назвать каждого друга хотя бы по разу, потом на каждом шаге максимизируем вероятность закончить игру не позже, чем на данном шаге. Моделируем 300000 шагов, считая по ходу дела сумму . , где k_i — количество раз, когда мы называли i-го друга ().

Заметим, что матожидание с небольшой погрешностью равно при достаточно большом N (это легко видеть, раскрыв скобки в приведенном выше выражении). Поэтому нам достаточно доказать, что

1) Приведенная выше жадная стратегия дает максимальные значения всех Pr(t).

2) На 300000 шаге погрешность меньше 10^- 6.

Доказательство:

1) Предположим, что для какого-то t набор l_i (), отличный от полученного жадным алгоритмом набора k_i, дает наибольшее значение Pr(t). Возьмем какое-нибудь k_a < l_a и k_b > l_b (такие найдутся, если наборы не совпадают, а их суммы равны t), тогда легко показать, что если в наборе l_i заменить l_b на l_b + 1, l_a на l_a - 1, то будет достигнуто еще большее значение Pr(t), что противоречит предположению о максимальности набора l_i.

2) Заметим, что q_i ≤ 0.99. Возьмем набор k_i такой, что для всех i выполняется , он даст вероятность завершения игры за t шагов не большую, чем оптимальный набор. Тогда Pr(t) ≥ (1 - 0.99^t / 100)¹⁰⁰ ≥ 1 - 100·0.99^t / 100. Погрешность оценки не превосходит , что оценивается, как сумма геометрической прогрессии, и при N ≥ 300000 получим погрешность меньше 10^- 7.

623E - Преобразование последовательности Для начала заметим, что если последовательность префиксных ксоров строго возрастает, то на каждом шаге a_i имеет хотя бы один новый бит по сравнению с предыдущими элементами. Так как битов всего k, длина последовательности не может быть больше k. Поэтому если n > k, то ответ 0.

Решим сначала задачу за O(k³). Посчитаем dp[n][k] — количество последовательностей длины n таких, что a₁|a₂|... |a_n имеет ровно k битов. Переход — добавить l новых битов и выбрать произвольно значения k битов, которые уже вошли в префиксный ксор. Значит, dp[n + 1][k + l] должно быть увеличено на dp[n][k]·2^k·C_k + l^l. Биномиальный коэффициент соответствует выбору добавляемых l битов из k + l, которые будут представлены в a₁|a₂|... |a_n + 1.

Заметим, что переход не зависит от n, поэтому попробуем применить идею бинарного возведения в степень. Пусть мы хотим слить динамики dp₁[k], dp₂[k], где k — количество битов в a₁|a₂|... |a_left и b₁|... |b_right соответственно. Хотим посчитать dp[k] для массивов размера left + right. Формула получается такая:

Здесь l соответствует битам в ксоре левой части, и для каждого числа из правой части эти l битов можно выбрать произвольно. Перепишем формулу так:

Значит, мы можем посчитать dp[k] для всех k, перемножив многочлены и . Коэффициенты первого получаются из коэффициентов второго за . Значит, мы можем посчитать динамику для всех длин — степеней двойки за , используя быстрое преобразование Фурье. На самом деле, удобнее насчитывать , используя то же самое равенство. Далее, используя ту же стратегию слияния, можно найти ответ для данного n, используя динамику для степеней двойки. Получили решение за .

Мы решили попросить ответ по модулю 10⁹ + 7, чтобы участники не смогли легко догадаться, что это задача на FFT :) Поэтому для получения ОК нужно было реализовать один из методов перемножения многочленов по большому модулю с использованием FFT. Другой подход состоял в применении алгоритма Карацубы, наша его реализация не укладывалась в ТЛ, однако jqdai0815 каким-то образом смог заставить свое решение с Карацубой пройти :)