593A - 2Char
Для каждой буквы будем поддерживать суммарную длину слов (
Unable to parse markup [type=CF_TEX]
), в которых встречается она одна, а для каждой пары букв будем поддерживать суммарную длину слов, в которых встречаются только они(Unable to parse markup [type=CF_TEX]
).Для каждой строки определим количество различных букв в ней. Если она одна, то добавим к этой букве длину этого слова. Если их две, то добавим к этой паре букв длину этого слова.
Переберем пару букв, которая будет ответом. Для пары букв
Unable to parse markup [type=CF_TEX]
ответом будетUnable to parse markup [type=CF_TEX]
. Среди всех таких пар найдем максимум и выведем его.Решение за O(суммарная длина всех строк + 26 * 26)
593B - Антон и прямые
Заметим, что если i-я прямая пересекаются с j-й в данной полосе, а при
Unable to parse markup [type=CF_TEX]
i-я прямая находится выше, то приUnable to parse markup [type=CF_TEX]
выше окажется j-я прямая.То есть отсортируем прямые по координате y при
Unable to parse markup [type=CF_TEX]
, и приUnable to parse markup [type=CF_TEX]
. Проверим, что порядок прямых в обоих случаях совпадает. Если существует такая прямая, что ее индекс в первом случае не совпадает со вторым, то выведем Yes. В другом случае выведем No.Единственное, что может нам помешать это пересечение на границах, так как в таком случае порядок сортировки не определен. Тогда прибавим к нашей границе x1 бесконечно малую величину eps, а от x2 отнимем eps, и порядок сортировки будет задан однозначно.
Решение за O(nlogn)
593C - Красивая функция
Одним из ответов будет являться сумма таких выражений для каждой окружности по координате x и аналогично по координате y:
Unable to parse markup [type=CF_TEX]
Пусть a = 1,
Unable to parse markup [type=CF_TEX]
, тогда это можно записать какUnable to parse markup [type=CF_TEX]
Рассмотрим
Unable to parse markup [type=CF_TEX]
:если
Unable to parse markup [type=CF_TEX]
, тоUnable to parse markup [type=CF_TEX]
,если a > b, то
Unable to parse markup [type=CF_TEX]
теперь рассмотрим, что такое a > b:
Unable to parse markup [type=CF_TEX]
Unable to parse markup [type=CF_TEX]
, иUnable to parse markup [type=CF_TEX]
.При целом i это возможно лишь в случае
Unable to parse markup [type=CF_TEX]
.То есть эта скобка не обнуляется лишь при
Unable to parse markup [type=CF_TEX]
.Рассмотрим
Unable to parse markup [type=CF_TEX]
. ТогдаUnable to parse markup [type=CF_TEX]
отличается от нужной координаты не более чем на 1, но так как все радиусы не меньше 2, то эта точка принадлежит окружности.Решение за O(n).
593D - Деревянный День Рождения
Рассмотрим задачу без запросов второго типа. Заметим, что в графе, где все числа на ребрах > 1 максимальное количество присвоений
Unable to parse markup [type=CF_TEX]
до того, как x превратится в 0, не превышает 64. Действительно, если всеUnable to parse markup [type=CF_TEX]
, то количество операций можно оценить какUnable to parse markup [type=CF_TEX]
. Подвесим дерево за какую-нибудь вершину и назовем ее корнем.Научимся решать задачу при условии, что для любого v
Unable to parse markup [type=CF_TEX]
и нет запросов второго типа. Для каждой вершины кроме корня мы определили ее предка как соседа наиболее близкого к корню. Пусть у нас был запрос первого типа от вершины a до вершины b с иходным числом x. Разобьем путь на две вертикальные части, одна из которых приближается к корню, а другая отдаляется. Найдем все ребра на этом пути. Для этого посчитаем глубину каждой вершины как расстояние до корня. Теперь будем параллельно подниматься в дереве из обеих вершин, пока не встретимся в общей. Если в ходе такого подъема мы прошли более 64 ребер, то в ходе заменUnable to parse markup [type=CF_TEX]
мы получим x = 0 и мы можем на текущем шаге остановить алгоритм поиска. Таким образом, мы совершим не болееUnable to parse markup [type=CF_TEX]
операций.Перейдем к задаче, где
Unable to parse markup [type=CF_TEX]
. Заметим, что наше предыдущее решение в таком случае может работать за O(n). Так как при прохождении по ребру сUnable to parse markup [type=CF_TEX]
наше значение не меняется. Сведем эту задачу к выше рассмотренной. Сожмем граф, то есть уберем все единичные ребра. Для этого запустим dfs от корня и будем хранить самое глубокое ребро на пути от корня до вершины сUnable to parse markup [type=CF_TEX]
.Вспомним, что у нас были запросы уменьшения
Unable to parse markup [type=CF_TEX]
. Будем поддерживать ближайшего предкаUnable to parse markup [type=CF_TEX]
cUnable to parse markup [type=CF_TEX]
. Воспользуемся идеей сжатия путей. При ответе на запрос первого типа будем пересчитыватьUnable to parse markup [type=CF_TEX]
. Введем рекурсивную функциюUnable to parse markup [type=CF_TEX]
. Которая возвращает v, еслиUnable to parse markup [type=CF_TEX]
, иначе выполняет присвоениеUnable to parse markup [type=CF_TEX]
и возвращаетUnable to parse markup [type=CF_TEX]
. Каждое ребро мы удалим 1 раз, значит суммарно вызов всех функцийUnable to parse markup [type=CF_TEX]
работает O(n).Итоговое время работы O(logx) на запрос первого типа и O(1) в среднем на запрос второго типа.
593E - Странные вычисления и кошки
Научимся решать задачу для маленьких t. Воспользуемся стандартной динамикой
Unable to parse markup [type=CF_TEX]
= количеству способов попасть в клетку (x; y) в момент времени t. Пересчет это сумма по всем допустимым способам попасть в клетку (x; y) в момент времени t – 1.Заметим, что такую динамику можно считать при помощи возведения матрицы в степень. Заведем матрицу переходов,
Unable to parse markup [type=CF_TEX]
, если мы можем попасть из клетки i в клетку j. Пусть у нас был вектор G, гдеUnable to parse markup [type=CF_TEX]
равно количеству способов попасть в клетку i. Тогда новый вектор G' черезUnable to parse markup [type=CF_TEX]
секунд G' = G *Unable to parse markup [type=CF_TEX]
.Таким образом мы научились решать задачу без изменений за O(log
Unable to parse markup [type=CF_TEX]
), где dt — момент времени, S – площадь.Рассмотрим, что происходит в момент добавления и удаления кота. При таких запросах изменяется матрица переходов. Между этими запросами T постоянная, значит мы можем возводить матрицу в степень. Таким образом, в момент изменения мы пересчитываем T, а между изменениями возводим матрицу в степень.
Решение за O(
Unable to parse markup [type=CF_TEX]
logUnable to parse markup [type=CF_TEX]
), m – количество запросов
