542A - Здесь могла быть ваша реклама

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

Определить наличие накрывающего ролика просто — достаточно отсортировать ролики в порядке возрастания левой границы, и, идя по ним слева направо, поддерживать минимальную правую границу, достигнутую к текущему моменту. Если, проходя через окно j, мы видим, что текущее значение максимума не меньше, чем b_j, то есть ролик, накрывающий наше окно, а значит ответ для данного окна можно установить равным (r_i - l_i)·c_i.

Среди всех вкладывающихся роликов надо найти тот, который имеет максимальную длину. Это можно сделать похожим образом, но чуть-чуть сложнее. Воспользуемся методом сканирующей прямой. Проходя через правую границу ролика r_i, будем присваивать в некоторой структуре данных (например, дереве отрезков), значение r_i - l_i в точку l_i. Проходя через правую границу окна, будем считать ответ для него как максимум на отрезке [a_j, b_j]. Таким образом мы учтём вложенные ролики.

Также можно определить наличие частично накрывающего ролика слева. Проходя через правую границу ролика r_i, будем писать в точку l_i значение r_i. Проходя через правую границу телеканала b_j, посчитаем для него ответ как максимум на отрезке [a_j, b_j] минус a_j.

Среди всех ответов для всех роликов выберем наиболее выгодный. Таким образом, выходит решение за .

Упражнение А если веса есть не только на окнах, но и на роликах, и они перемножаются? Решите задачу за , получите виртуальную медаль!

542B - Охота на уток

Будем приближаться к решению задачи постепенно. Во-первых, скажем, что у нас утки неподвижны, а охотник топает вправо со скоростью 1. Определим величину F[x][s] как минимальное количество уток среди тех, правые концы которых расположены не позже x, которых мы не сможем подстрелить, если последний выстрел был сделан ровно в точку s. В частности, в величину F[x][s] включены все утки, расположенные в отрезке [s + 1, x]. Значения F[x][s] для s > x будем считать неопределёнными.

Будем смотреть на F[x] как на функцию от s. Эта функция определена на всех s от 0 до x включительно. Ключевая идея заключается в исследовании того, как отличается F[x + 1][·] от F[x][·].

Давайте сначала предположим, что если в точке x + 1 не заканчивается ни одна утка, то в определении F[x + 1][·] фигурируют те же самые утки, что и в определении F[x][·]. Это значит, что все значения F[x][s] для s ≤ x остаются теми же. Интереснее дело обстоит с F[x + 1][x + 1]. Нетрудно видеть, что выстрел в точку x + 1 не может подбить ни одну из уток, заканчивающихся не правее x + 1 (так как мы только что предположили, что таких уток нет). Значит, F[x + 1][x + 1] = min F[x + 1][0... x + 1 - r] = min F[x][0... x + 1 - r].

Теперь давайте предположим, что в точке x + 1 заканчивается утка [l, x + 1]. В таком случае, можно смело сказать, что ко всем значениям D[x + 1][0... l - 1] можно прибавить 1 (потому что к моменту выстрела в точку s < l утку [l, x + 1] подбить ещё никак не возможно). В то же время, все значения D[x + 1][l... x + 1] останутся прежними, потому как последний выстрел и подобьёт новодобавленную утку.

Теперь давайте постепенно понимать реализационную сторону вопроса. Функция F[x][·] является кусочно-постоянной, а значит, её можно хранить в декартовом дереве в виде набора пар (начало отрезка, значение на отрезке). Такое хранение позволит нам легко прибавлять 1 на отрезке и брать минимум на префиксе функции.

Теперь будем считать, что функция F[x][·], определена на всей положительной полуоси, просто значения F[x][s] для s > x не удовлетворяют определению функции F[x][s]. Можно мысленно представить, что последний отрезок в структуре F[x] просто продляется до бесконечности вправо.

Будем идти сканирующей прямой по переменной x. Заметим, что функция F[x + 1][·] по сравнению с функцией F[x][·] меняется очень редко. Например, значение F[x + 1][x + 1] практически всегда совпадает с F[x][x + 1] (которое, в свою очередь, совпадает с F[x][x], о чём сказано абзацем выше). Действительно, в предположении, что в x + 1 не заканчивается ни одна утка, F[x][x] = min(F[x][0... x - r]) и F[x + 1][x + 1] = min(F[x + 1][0... x + 1 - r]) = min(F[x][0... x + 1 - r]) ≤ min(F[x][0... x - r]). Таким образом, интересное для нас событие возникает, когда значение F[x][x - r + 1] меньше всего префикса перед ним. Однако, величина min(F[x][0... x - r]) может не более n раз увеличиться на 1 (каждый раз, когда x проходит через правый конец утки), а значит, и уменьшиться может не более n раз (так как это неотрицательная величина).

Значит, событий вида "мы прошли через правый конец утки" и "нам надо нетривиально посчитать F[x][x] в сумме линейное количество. Каждое из них обрабатывается с помощью обращения к декартову дереву, которое происходит за . А значит, мы получили решение, работающее за . Ура!

542C - Идемпотентная функция

Для решения этой задачи полезно разобраться, как выглядит граф, отвечающий функции из множества {1, ..., n} в себя. Рассмотрим граф на вершинах 1, ..., n, где из вершины i ведёт ребро в вершину f(i). Такой граф всегда выглядит как набор циклов, в которые ведут деревья. Как же должен выглядеть граф, отвечающий инволюции? Нетрудно понять, что в таком графе все циклы должны быть длины 1, а все вершины, которые не являются циклами длины 1 (т. е. неподвижными точками), должны сразу вести в какую-то неподвижную точку.

Значит, мы должны соблюсти два условия. Во-первых, все циклы должны стать длины 1 — для этого, как нетрудно понять, k должно делиться на [c₁, c₂, ..., c_m], где c_i — длины всех циклов. Во-вторых, все вершины, не лежащие на циклах, должны стать переходящими в вершины, лежащие на циклах. Иными словами, k должно быть не меньше, чем расстояние от любой вершины x до цикла, в которую она попадает (или, что то же самое, длины предпериода в последовательности f(x), f(f(x)), f(f(f(x))), ...).

Значит, наша задача свелась к тому, чтобы найти минимальное число k, делящееся на A, и не меньшее, чем B, что совсем несложно сделать.

Упражнение Какой максимальный ответ достигается в этой задаче? (Ответ: раз два)

542D - Супергеройская работа

Первым делом в этой задаче стоит разобраться, что из себя представляет функция Джокера. Одним из главных её свойств является мультипликативность: J(ab) = J(a)J(b) для (a, b) = 1, что даёт нам возможность записать значение функции, зная её значение на простых множителях аргумента: J(p₁^k₁p₂^k₂... p_m^k_m) = J(p₁^k₁)J(p₂^k₂)... J(p_m^k_m) = (p₁^k₁ + 1)(p₂^k₂ + 1)... (p_m^k_m + 1). Воспользуемся этим знанием, чтобы решить задачу методом динамического программирования.

Обозначим за P множество тех простых чисел p, что скобка с их участием может встретиться в A = J(x). Таких простых немного — для каждого делителя d числа A он может соответствовать не более, чем одному простому, а именно, тому, чьей степенью является число d - 1 (если вообще является). Составим множество P, запомнив также для каждого простого числа p в нём, в каких степенях k скобка (p^k + 1) делит A.

Теперь можно посчитать величину D[p][d], которая равна количеству способов получить делитель d числа A в виде произведения скобок от первых p простых чисел в множестве P. Такую величину можно посчитать методом динамического программирования за , где — количество делителей числа A (так как выше было показано, что ). Значит, общая сложность решения — .

Упражнение Как себя ведёт с ростом A? Например, какое максимальное значение по всем A ≤ 10¹²? (Ответ: . Полезная оценка, не являющаяся, тем не менее, точной асимптотикой, заключается в том, что )

Упражнение А какой максимальный ответ достигается в этой задаче? Если получится сгенерировать тест, в котором ответ больше миллиона, с меня большой респект!

542E - Игра на графе

Заметим, что если исходный граф — недвудольный, то ответ — (-1). Действительно, любой нечётный цикл, будучи стянутым по паре вершин, всегда порождает нечётный цикл меньшего размера, в результате чего мы получим треугольник, с которым уже никак справиться нельзя.

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

Последним шагом остаётся заметить, что ответ — сумма ответов для отдельных компонент, которые можно по очереди подцепить друг другу. Таким образом, ответ — сумма диаметров компонент связности, если они все двудольные, иначе — (-1). Решение имеет сложность O(E + VE) (первое слагаемое — проверка на двудольность, второе слагаемое — подсчёт диаметра путём запуска BFS из каждой компоненты связности).

542F - Квест

Эту задачу можно было решать массой способов. Самый прямолинейный — динамическое программирование. Условие задачи можно переформулировать таким образом, что мы хотим выбрать какое-то множество вершин в качестве листов, для каждого потенциального листа известно верхнее ограничение на его глубину, и также известны стоимости каждого листа.

Будем идти по дереву снизу вверх. Посчитаем величину D[h][c] — максимальная возможная стоимость, которую можно получить, если, находясь на уровне h, мы имеем c вершин. Для перехода переберём, сколько листов именно имеющейся глубины мы возьмём (понятно, что из них выгоднее всего взять несколько максимальных), пусть, мы возьмём k. Тогда из этого состояния можно сделать переход в состояние D[h - 1][⌈(c + k) / 2⌉]. Ответ будет находиться в величине D[0][1] — действительно, придя на глубину 0, мы должны остаться с одной-единственной вершиной — корнем.

Сложность решения — O(n²T).

Упражнение Прокачайте решение выше до . А потом до