Codeforces Round #329 (Editorial)

Revision ru1, by josdas, 2015-11-04 22:24:34

593A - 2Char

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

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

Переберем пару букв, которая будет ответом. Для пары букв ci, cj ответом будет cnt1ci + cnt1cj + cnt2ci, cj. Среди всех таких пар найдем максимум и выведем его.

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

593B - Anton and Lines

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

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

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

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

593C - Beautiful Function

Одним из ответов будет являться сумма таких выражений для каждой окружности по координате 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 - Happy Tree Party

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

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

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

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

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

593E - Strange Calculation and Cats

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

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

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

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

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

Tags 329, сложнаааааа

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English josdas 2015-11-04 23:10:55 128 Tiny change: 'ase we don`t know the sort`s order. T' -
en1 English josdas 2015-11-04 23:03:22 6102 Initial revision for English translation
ru1 Russian josdas 2015-11-04 22:24:34 5795 Первая редакция (опубликовано)