593A - 2Char

Для каждой буквы будем поддерживать суммарную длину слов (cnt1_ci), в которых встречается она одна, а для каждой пары букв будем поддерживать суммарную длину слов, в которых встречаются только они(cnt2_ci, cj).

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

Переберем пару букв, которая будет ответом. Для пары букв c_i, c_j ответом будет cnt1_ci + cnt1_cj + cnt2_ci, cj. Среди всех таких пар найдем максимум и выведем его.

Решение за O(суммарная длина всех строк + 26 * 26)

593B - Антон и прямые

Заметим, что если i-я прямая пересекаются с j-й в данной полосе, а при x = x₁ i-я прямая находится выше, то при x = x₂ выше окажется j-я прямая.

То есть отсортируем прямые по координате y при x = x₁ + eps, и при x = x₂ - eps. Проверим, что порядок прямых в обоих случаях совпадает. Если существует такая прямая, что ее индекс в первом случае не совпадает со вторым, то выведем Yes. В другом случае выведем No.

Единственное, что может нам помешать это пересечение на границах, так как в таком случае порядок сортировки не определен. Тогда прибавим к нашей границе x₁ бесконечно малую величину eps, а от x₂ отнимем eps, и порядок сортировки будет задан однозначно.

Решение за O(nlogn)

593C - Красивая функция

Одним из ответов будет являться сумма таких выражений для каждой окружности по координате x и аналогично по координате y:

Пусть a = 1, b = abs(t - i), тогда это можно записать как

Рассмотрим a - b + abs(a - b):

если a ≤ b, то a - b + abs(a - b) = 0,

если a > b, то a - b + abs(a - b) = 2a - 2b

теперь рассмотрим, что такое a > b:

1 > abs(t - i)

i > t - 1, и i < t + 1.

При целом i это возможно лишь в случае i = t.

То есть эта скобка не обнуляется лишь при i = t.

Рассмотрим 2a - 2b = 2 - 2 * abs(t - i) = 2. Тогда отличается от нужной координаты не более чем на 1, но так как все радиусы не меньше 2, то эта точка принадлежит окружности.

Решение за O(n).

593D - Деревянный День Рождения

Рассмотрим задачу без запросов второго типа. Заметим, что в графе, где все числа на ребрах  > 1 максимальное количество присвоений до того, как x превратится в 0, не превышает 64. Действительно, если все R_v = 2, то количество операций можно оценить как log₂(x). Подвесим дерево за какую-нибудь вершину и назовем ее корнем.

Научимся решать задачу при условии, что для любого v R_v > 1 и нет запросов второго типа. Для каждой вершины кроме корня мы определили ее предка как соседа наиболее близкого к корню. Пусть у нас был запрос первого типа от вершины a до вершины b с иходным числом x. Разобьем путь на две вертикальные части, одна из которых приближается к корню, а другая отдаляется. Найдем все ребра на этом пути. Для этого посчитаем глубину каждой вершины как расстояние до корня. Теперь будем параллельно подниматься в дереве из обеих вершин, пока не встретимся в общей. Если в ходе такого подъема мы прошли более 64 ребер, то в ходе замен мы получим x = 0 и мы можем на текущем шаге остановить алгоритм поиска. Таким образом, мы совершим не более O(log(x)) операций.

Перейдем к задаче, где R_v > 0. Заметим, что наше предыдущее решение в таком случае может работать за O(n). Так как при прохождении по ребру с R_v = 1 наше значение не меняется. Сведем эту задачу к выше рассмотренной. Сожмем граф, то есть уберем все единичные ребра. Для этого запустим dfs от корня и будем хранить самое глубокое ребро на пути от корня до вершины с R_v > 1.

Вспомним, что у нас были запросы уменьшения R_v. Будем поддерживать ближайшего предка P_v c R_Pv > 1. Воспользуемся идеей сжатия путей. При ответе на запрос первого типа будем пересчитывать P_v. Введем рекурсивную функцию F(v). Которая возвращает v, если R_v > 1, иначе выполняет присвоение P_v = F(P_v) и возвращает F(P_v). Каждое ребро мы удалим 1 раз, значит суммарно вызов всех функций F(v) работает O(n).

Итоговое время работы O(logx) на запрос первого типа и O(1) в среднем на запрос второго типа.

593E - Странные вычисления и кошки

Научимся решать задачу для маленьких t. Воспользуемся стандартной динамикой dp_x, y, t = количеству способов попасть в клетку (x; y) в момент времени t. Пересчет это сумма по всем допустимым способам попасть в клетку (x; y) в момент времени t – 1.

Заметим, что такую динамику можно считать при помощи возведения матрицы в степень. Заведем матрицу переходов, T_i, j = 1, если мы можем попасть из клетки i в клетку j. Пусть у нас был вектор G, где G_i равно количеству способов попасть в клетку i. Тогда новый вектор G' через dt секунд G' = G * (T^dt).

Таким образом мы научились решать задачу без изменений за O(log dt * S³), где dt — момент времени, S – площадь.

Рассмотрим, что происходит в момент добавления и удаления кота. При таких запросах изменяется матрица переходов. Между этими запросами T постоянная, значит мы можем возводить матрицу в степень. Таким образом, в момент изменения мы пересчитываем T, а между изменениями возводим матрицу в степень.

Решение за O(m * S³ log dt), m – количество запросов