Разбор задач отбора: Engine

1310A — Рекомендации

В задаче нам дан массив a_1, …, a_n, мы можем увеличивать любые a_i на один, заплатив t_i, и мы хотим сделать все a_i различными с минимальным суммарным штрафом.

Отсортируем a_i в неубывающем порядке (и соответственно переставим t). Посмотрим на минимальное значение в массиве, a_1. Если оно уникально, то есть a_1 ≠ a_2, то с ним ничего не нужно делать, оно ни с чем не сможет совпасть, если мы его не увеличим. В этом случае мы можем пропустить a_1 и решать меньшую задачу уже без a_1.

Иначе, предположим, что есть j > 1, такое, что a_1 = a_2 = … = a_j. Очевидно, мы можем оставить текущее значение не больше, чем у одного из них, и увеличить остальные j − 1 чисел на один. Какое число следует оставить? Следует оставить a_l(1 ≤ l ≤ j) с максимальным t_l, так как это минимизирует суммарный штраф. Таким образом, алгоритм заключается в том, чтобы удалить элемент с максимальным t_l среди всех элементов с минимальным a_l и увеличить остальные минимумы на 1. Это сводит задачу к меньшей, уменьшая n на один.

Так мы получаем решение за O(n²) — n раз выкидываем один минимум и увеличиваем остальные. Можно соптимизировать это решение, похранив в мультисете все t_l для минимальных aₗ и посчитав их сумму. На каждой итерации нужно добавить несколько минимумов в мультисет (если количество минимумов увеличивается), выбросить из мультисета один максимум и добавить к ответу сумму в мультисете. Продолжаем процесс, пока массив не опустеет. Это работает уже за O(n log n).

1310B — Двойное выбывание

Главное наблюдение в этой задаче — для всех множеств игроков, полностью лежащих в поддереве какой-либо вершины двоичного дерева верхней сетки, ровно один игрок из этого множества выиграет все матчи в верхней сетке, и ровно один игрок выиграет все матчи в нижней сетке. Можно задать это множество игроков (в 0-индексации вместо 1-индексации из условия) как [a ⋅ 2^t;(a + 1) ⋅ 2^t) для некоторых 1 ≤ t ≤ n, 0 ≤ a < 2^n / 2^t. Также можно заметить, что для каждого фиксированного t игроки с различными значениями id / 2^t не играют друг с другом в первых раундах, и их верхние и нижние сетки независимы до какого-то момента.

Для каждого из этих множеств команд нам важно лишь количество интересных матчей между ними и правда ли, что мы болеем за команды-победители в верхней и нижней сетке. Это приводит к следующему решению динамическим программированием:

dp[l…r][f_up][f_lower] — наибольшее возможное количество интересных игр между игроками с номерами [l;r), при этом f_up∈{0,1} равно 1, если мы болеем за победителя в верхней сетке, и f_lower∈{0,1} равно 1, если мы болеем за победителя в нижней сетке. Опять же, l…r — это особый подотрезок: l = a ⋅ 2^t, r = (a + 1) ⋅ 2^t − 1 для некоторых 1 ≤ t ≤ n, 0 ≤ a < 2^n / 2^t.

dp[l…r][f_up][f_lower] может быть пересчитано через dp[l…(l + r) / 2][f^l_up][f^l_lower] и dp[l + r2…r][f^r_up][f^r_lower] — мы просто перебираем все возможные f^l_up, f^l_lower, f^r_up, f^r_lower и результаты всех трёх матчей (один в верхней и два в нижней сетке).

В конце концов мы используем dp[0…2^n][f_up][f_lower] для подсчёта последнего матча, гранд-финала.

Данное решение работает примерно за O(2^n ⋅ 2^7), потому что в нём используется 2^n интересных отрезков.

1310C — Красный мост

Выпишем все различные подстроки, отсортируем и переберём двоичным поиском минимальную строку в ответе. Теперь нужно посчитать количество разбиений на подстроки, где каждая подстрока не меньше, чем фиксированная в бинпоиске.

Это можно сделать динамическим программированием dp_(pos,count) — количество путей разбить суффикс, начинающийся с позиции pos, на count подстрок, каждая из которых не меньше заданной. Найдём первую букву, где текущий суффикс отличается от фиксированной строки. Если следующий символ суффикса меньше, чем в выбранной строке, то все префиксы этого суффикса меньше заданной строки, и значение динамики равно нулю. Иначе, любая подстрока такой длины или больше подходит, и нам нужно посчитать

что может быть сделано за O(1) времени с помощью суффиксных сумм и предпросчёта lcp для всех пар суффиксов. Предпросчитать lcp всех пар суффиксов можно за O(n²) — lcp двух суффиксов равно 0, если у них разные первые буквы, и равно lcp двух меньших суффиксов +1 иначе.

1310D — Путешествие

Есть два подхода к решению этой задачи.

Первый — можно перебрать все чётные вершины на пути. Это может быть сделано за O(n^(k / 2 − 1)). После этого нужно соединить соседние вершины минимальными путями длины 2, не проходящими через выбранные вершины. Это может быть сделано путём предпросчёта шести минимальных путей длины 2 между каждой парой вершин и игнорированием не больше пяти лучших, пока не найдётся путь, не проходящий через выбранные вершины.

Другое решение рандомизированное. Возьмём случайную покраску вершин в два цвета. Можно найти наилучший путь с учётом данной раскраски вершин в два цвета за O(k ⋅ E) времени с помощью динамического программирования. С вероятностью 1 / 512 лучший путь удовлетворяет этой раскраске. Из этого следует, что после повторения этого алгоритма 512 ⋅ 20 раз, вероятность ошибки будет порядка (511 / 512)^(512 ⋅ 20) ≈ e^(−20) ≈ 2 ⋅ 10^(−9), что должно проходить все тесты.

1310E — Странная функция

Решение состоит из разбора трёх случаев:

• Если k = 1. Для фиксированного n f(a) может быть любым разбиением числа n на слагаемые. Нужно посчитать количество массивов b_1, b_2, …, b_m таких, что

Это может быть сделано простой динамикой за O(n²) — можно и быстрее, но не нужно.

• Если k = 2. Когда массив b_1 ≥ b_2 ≥ … ≥ b_m может быть получен как значение f²(a) для какого-то массива |a| ≤ n? Когда существует какой-то массив c_1, …, c_l, такой, что

Значения b — количества вхождений чисел в c, так что нам нужно минимизировать

где v_i — множество уникальных чисел в c.

Чтобы минимизировать эту сумму, нужно взять v_1 = 1, …, v_m = m, так что необходимо

Число таких массивов можно посчитать простой динамикой: dp[val][j][sum] — количество префиксов b таких, что в префиксе из j элементов все элементы не меньше, чем val, и

Эта динамика похожа на O(n³), но это иллюзия, на самом деле её можно реализовать за O(n² log n), потому что есть ограничение val ⋅ j ≤ n, и существует O(n log n) таких пар. Для этого случая также есть решение быстрее, чем за квадрат, но не стоит о грустном.

• Если k ≥ 3. Можно заметить, что в массиве f²(a) не больше O(√(2n)) элементов. Используя этот факт, можно перебрать все кандидаты на ответ — все подходящие массивы, это разбиения на слагаемые чисел не больше, чем √(2n) = 64. Таких разбиений на слагаемые несколько миллионов.

Как проверить, может ли массив b_1≥ b_2 ≥ … ≥ b_m быть значением f^k(a)? Оказывается, можно сделать k − 2 итераций обратного алгоритма из пункта k = 2, получить минимальный возможный массив a и проверить, что в нём не больше n элементов. Эта часть работает за O(P√(2n)).

1310F — Плохая криптография

Одним из хорошо известных алгоритмов для задачи дискретного логарифма является алгоритм baby-step giant-step, основанный на идее meet-in-the-middle. Он может решать задачу за время O(√|F|), чего явно недостаточно для поля размера 2^(6)4.

Мультипликативная группа поля имеет размер F = 2^(6)4 − 1 = 3 ⋅ 5 ⋅ 17 ⋅ 257 ⋅ 641 ⋅ 65537 ⋅ 6700417. Как видно, все простые числа в разложении не очень большие. Найдём остаток от деления значения ответа на каждое из этих простых. В таком случае можно будет восстановить ответ по китайской теореме об остатках.

Пусть p — один из делителей. Если x = k ⋅ p + y — это ответ, то a^(kp + y) = b, а значит, a^(kF + yF/p) = b^(F/p). Так как a^F равен 1, то задача эквивалентна поиску такого y, что (a^(F/p))^y = b^(F/p). Это задача дискретного логарифма на подгруппе исходной группы размера p. Её можно решить, используя O(√p) умножения. Это около 6 000 умножений в сумме по всем p.

Если одного из дискретных логарифмов не существует, то и ответа на исходную задачу, очевидно, не существует. Другой крайний случай получается, если оба значения в подзадаче равны 1. Это означает, что по этому модулю подходит любое значение. Кроме того, это значит, что и у a, и у b период меньший максимального, и можно выбрать любое из них.

Вторая часть задачи состоит в том, чтобы сделать перемножение достаточно быстрым. Первая идея, которая для этого пригодится, — необходимо закешировать произведения для всех пар степеней двойки. Такое решение работает около пяти секунд, и, вероятно, с помощью разных хаков его можно уложить в ограничение по времени. Но умножение можно делать асимптотически быстрее. Пусть a = a_1 ⋅ P + a_2, b = b_1 ⋅ P + b_2 — это разложение чисел на первую и вторую половины битов (фактически P — это значение переменной power из функции multiply_powers_of_2). Тогда a ⊙ b = (a_1 ⋅ P + a_2) ⋅ (b_1 ⋅ P + b_2) = (a_1 ⊙ P ⊕ a_2) ⊙ (b_1 ⊙ P ⊕ b_2) = (a_1 ⊙ b_1) ⊙ (P ⊙ P) ⊕ (a_2 ⊙ b_2) ⊕ ((a_1 ⊙ b_2) ⊕ (a_2 ⊙ b_1)) ⊙ P.

Как и в алгоритме Карацубы, эти четыре произведения могут быть выражены через три, если заметить, что (a_1 ⊙ b_2) ⊕ (a_2 ⊙ b_1) = (a_1 ⊕ a_2) ⊙ (b_1 ⊕ b_2) ⊕ (a_1 ⊙ b_1) ⊕ (a_2 ⊙ b_2). Единственное отличие — вместо сдвига для умножения на P ⋅ P придётся делать ещё одно умножение.

Но P ⊙ P = P ⊕ P/2. Можно умножить на эти две части отдельно. Умножение на P делается просто. Вторая часть — умножение на степень двойки, и наивный алгоритм сделает это за линейное время. С другой стороны, можно просто сделать это умножение рекурсивным вызовом. Это будет достаточно быстро, так как большая часть веток в этом поддереве окажется умножением на 0. Кроме того, для ускорения можно предподсчитать все произведения пар чисел не больше 256. Такой алгоритм работает примерно в пять раз быстрее, чем наивное умножение.