Заключительный этап VIII

открытой олимпиады
по программированию
Разбор задач первого дня
Задача «Пляжный волейбол»

Автор идеи: Елена Андреева

Разработчик и автор разбора: Антон Полднев
Формальная постановка
Дана перестановка из чисел от до В конце
очередного шага минимальное из первых двух
чисел перемещается в конец
Нужно для каждого из запросов с номером шага
определить какие два числа будут в начале массива
на этом шаге
1 группа: N, K1 ≤ 2000, 1 запрос
раз проделаем над исходным массивом
описанную на предыдущем слайде процедуру
с помощью цикла переместим минимальное
из первых двух чисел в конец
Сложность баллов
2 группа: N, Ki ≤ 105, Q ≤ 10
Как и в первой группе реализуем моделирование
для каждого из запросов смоделируем
соответствующее число шагов выполняя каждый
шаг не за линейное время а за константу
Как выполнять один шаг за Для начала
отсортируем первые два числа по возрастанию
теперь нужно лишь научиться за константное
время перемещать первое число массива в конец
2 группа: N, Ki ≤ 105, Q ≤ 10
Способ Встроенный дек
Способ Изначально заведём массив размера
исходный массив сохраним в первые позиций
Чтобы переместить нулевой элемент в конец сделаем
просто индексация с и запомним что
наш массив теперь начинается с а не с Далее

Сложность баллов
Оптимизируем: N, Ki ≤ 105, Q ≤ 105
В решении на баллов мы моделировали
последовательность игр для каждого запроса
отдельно Зачем
Смоделируем последовательность игр один раз
до максимального и запомним силы игравших
на каждом шаге команд
Теперь используя запомненные значения на каждый
запрос отвечаем за О
Сложность баллов
 Полное решение: N, Q ≤ 105, Ki ≤ 1018
1324
3241
Заметим что как только самая сильная командаа
3412
4123
окажется в начале очереди остальные будут
4231
4312
ходить по циклу и проигрывать Пусть первый шаг
4123
4231
на котором сильнейшая команда стоит в начале
4312
4123 очереди имеет номер
4231
4312 Ответ для всех можно найти как
4123
4231 в предыдущем решении
4312
4123
4231
Как находить ответ за запрос ≥
4312
 Полное решение: N, Q ≤ 105, Ki ≤ 1018
1324
3241
Как находить ответ за запрос ≥
3412
4123 Все команды кроме сильнейшей при ≥ будут
4231
4312
ходить по циклу На м шаге с сильнейшей командой
4123
4231
будет играть команда которая на м шаге стояла на
4312
4123
позиции − − если нумеровать позиции с
4231
4312
нуля
4123
4231
Сложность
4312
4123 ≤ баллов
4231
4312 Не забыли про баллов
 Задача «Путешествие»

Автор идеи и разбора: Михаил Пядеркин

Разработчик: Павел Кунявский
Формальная постановка
Дан граф вершины которого имеют некоторые веса
Необходимо найти простой путь максимального
суммарного веса состоящий из не более чем вершин
Добавляя фиктивные вершины веса можно свести задачу
к поиску пути ровно из вершин
Будем обозначать число вершин графа буквой а число
ребер графа буквой
Простейшее решение
Будем перебирать все четверки вершин и если пары
и соединены ребром то пробуем обновить
ответ
for a=1..V:
for b=1..V:
for c=1..V:
for d=1..V:
if ((a, b), (b, c), (c, d) соединены ребром
и вершины a, b, c, d различны) then обновить текущий
ответ
и баллов
Почувствуйте разницу!
for a=1..V:
for b - смежная (соединенная ребром) с a:
for c - смежная с b:
for d - смежная с c:
if (вершины a, b, c, d различны) then
обновить текущий ответ
Такое решение работает за так как каждая пара ребер
будет рассмотрена не более раз
баллов
Ключевая идея
Давайте переберем центральное ребро
a d

b c

После этого можно перебрать вершину В качестве

вершины логично выбрать самую красивую вершину
смежную с и не совпадающую ни с одной из множества

Таким образом среди соседей вершины нас интересуют

лишь самые красивые вершины
и баллов
А что, собственно, осталось?
На предыдущем слайде мы выяснили что при
фиксированном ребре нас интересуют лишь самых
красивых соседа вершины
Однако в силу симметрии то же верно и для вершины
Таким образом необходимо заранее для каждой вершины
найти самых красивых соседа затем перебрать ребро
а затем перебрать и среди самых красивых у вершин
и
баллов
Задача «Шустрая черепашка»

Автор идеи: Глеб Евстропов

Разработчик и автор разбора: Максим Ахмедов
Формальная постановка
В задаче требуется ответить на некоторое количество
запросов следующего вида: «может ли черепашка
добраться из клетки ai в клетку ci, если клетка bi
заблокирована».
В зависимости от группы тестов, количество запросов
достигает 1000, 1 000 000 и 20 000 000.
Также меняется размер поля от 100x100 до 150x150.
Простая симуляция: 30 баллов
Будем на каждый запрос блокировать
соответствующую клетку и запускать любой
алгоритм поиска пути на табличке (обход
в ширину/глубину).
Запросов — 1000, каждый запрос
обрабатываем за 100 ⋅ 100.
Подобное решение с запасом укладывается
в ограничение по времени.
Верхний и нижний путь
Будем отвечать на все запросы,
заканчивающиеся в фиксированной клетке c.
Посчитаем из каждой клетки «самый верхний»
и «самый нижний путь», идущий в c. Это
понятие корректно: если есть два пути, среди
которых непонятно, кто выше, то можно взять
огибающий путь выше их обоих.
Утверждение: если есть какой-то путь, не
проходящий через b, то один из этих двух
путей подходит.
60 баллов: считаем пути
Пойдём из клетки c во все клетки вверх и влево. Про каждую
посещенную клетки мы знаем, что из неё можно добраться до c.
Теперь, используя эти пометки, мы для каждого запроса (a, b) можем
пойти только по верхнему и только по нижнему пути из a.
| while i != c.i and j != c.j:
| | if flag[i][j + 1]:
| | | j += 1 ← программа, идущая по “верхнему” пути

| | else:
| | | i += 1
Если оба этих пути содержат клетку b то NO, иначе YES.
O(N4) предподсчёт, O(N) на запрос. Лучше писать с O(N2) памяти.
100 баллов #1: считаем количества
Обозначим за P(x, y) количество путей из клетки x в клетку y.
Путей из a в c, проходящих через клетку b — P(a, b) ⋅ P(b, c).
Всего путей — P(a, c).
Нас спрашивают — равны ли эти два числа? Числа — большие, но
мы будем считать их по некоторому большому простому модулю.
Вероятность “случайного” совпадения крайне мала.
Посчитаем эти количества динамическим программированием за O
(N4).
Считаем оптимально, используем только O(N2) памяти для динамики
и 3 ⋅ Q памяти, чтобы сохранить посчитанные значения.
Сложность — O(N4 + Q).
100 баллов #2: разрезы и битовое сжатие
Что означает, что есть путь “в обход” клетки b? Рассмотрим
диагональный разрез доски, проходящий через клетку b. a
Нам надо, чтобы существовала клетка x на той же диагонали, которая
достижима из a и из которой достижима c. x

Воспользуемся битовым сжатием: будем хранить информацию о b

достижимости из вершины в массиве из пяти 32-битных чисел.
Обозначим from[a][i] — маска достижимых вершин на i-й диагонали из с
клетки a, to[c][i] — маска вершин на i-й диагонали, из которых достижима
c.
Тогда мы должны рассмотреть (from[a][i] AND to[c][i]), где AND —
попарное битовое “И” двух массивов, и проверить, есть ли на нём хотя
бы одна единица на некотором отрезке кроме одной клетки b. Это
условие проверяется за O(N / 32) битовых операций, что даёт нам
сложность — O(N4 / 32 + QN / 32). На практике это решение даже быстрее
предыдущего!
Задача «„Чапаев“ на дереве»

Автор идеи, разработчик и автор разбора

Максим Ахмедов
Формальная постановка
В задаче фактически ведётся речь о следующей игре.
● У нас имеется корневое дерево.
● Каждая вершина покрашена либо в белый (шашка
есть), либо в черный цвет (шашки нет)
● За один ход можно взять любую белую вершину и
покрасить весь путь от неё до корня в чёрный цвет.
● Определить, кто выигрывает при некоторых
определёных начальных расположениях.
20 баллов: O(2N ⋅ N2), простейший анализ
Так как N ≤ 20, можно определить для всех 2N возможных
состояний выигрышность/проигрышность.
Каждое состояние — маска чёрных вершин. Можно
воспользоваться динамическим программированием, можно
написать перебор с запоминанием.
win[msk] = OR(!win[msk | path[x]])
где path[x] — это маска вершин, лежащих на пути от x до корня
дерева, а OR берётся по всем вершинам x, куда ещё можно
сходить, т. е. для которых соответствующий бит в msk — нулевой.
Сложность решения — 2N ⋅ N ⋅ N, на практике — гораздо меньше.
Важное соображение
Для дальнейшего продвижения необходимо
заметить важный факт.
Рассмотрим дерево, в котором все вершины
белые. После произвольного хода образуется
несколько поддеревьев, подвешенных за
образовавшиеся чёрные вершины.
Утверждение: дальнейшая игра будет происходить
независимо в каждом из этих поддеревьев, причём
можно считать, что каждое из этих поддеревьев
«отвалилось» и стало самостоятельным.
Важное соображение
Действительно, после этого любой ход затрагивает
лишь вершины из того подерева, куда мы попали.
Такая особенность означает, что после каждого
хода исходная игра распадается в прямую сумму
игр, происходящих на некоторых поддеревьях
исходного дерева.
В частности, исходная игра по условию
представляет собой прямую сумму игр на
поддеревьях некоторой вершины Root.
Это означает, что для анализа игры можно
использовать теорию Шпрага — Гранди.
Использование функции Гранди
Обозначим за G[v] функцию Гранди игры на
поддереве вершины v.
Тогда функция Гранди для начального положения,
Root
задаваемого вершиной Root — G[r1] xor G[r2]
xor … xor G[rk], где r1, r2, …, rk — дети вершины r1 r2 rk

Root (так как игра ведется по ним независимо).

Если величина выше — не ноль, то игра выигрышная,
G[r 1] G[r 2] G[r k]
иначе — проигрышная.
 Вычисление функции Гранди
Как вычислить функцию Гранди от вершины v — G v
[v]?
G[v] = MEX(S(u1,v), S(u2,v), … , S(um,v)), где
u1,u2,…,um— все вершины в поддереве v, а S(ui,v)—
xor всех поддеревьев, “подцепленных” за путь ui -> v.
S(ui,v)можно посчитать, воспользовавшись
формулой:
S(ui,v) = xor(G[x] if parent[x] on ui —> v),
где x пробегает поддерево v, при этом включаются ui
только те вершины x, которые “подцеплены” за путь ui
-> v.
 3
40 баллов: O(N ), считаем в лоб
Будем считать фукнцию Гранди, как только что было
описано.
перебираем v в порядке DFS: // функция DFS(v)
| перебираем u в поддереве v: // функция DFS2(v, u)
| | xor_val = 0;
| | перебираем x в поддереве u: // функция DFS3(v, u, x)
| | | if (parent[x] on u —> v):
| | | | xor_val = xor_val xor G[x]
| | val[u] = xor_val
| G[v] = MEX(val[])
Как нетрудно видеть, полученное решение работает за O(N3).
Мы считаем одно и то же много раз!
Соптимизируем предыдущее решение. Заметим,
что подсчёт xor всех поддеревьев, подцепленных
за путь (третий цикл) работает неоптимально.
Идея: когда мы сдвигаемся из u в дочернюю
вершину w множество зацепленных за путь
поддеревьев меняется несильно, а мы
пересчитываем их все заново.
Давайте это исправим.
Исследуем изменение
При спуске из вершины u в вершину w значение
меняется на G[w] xor childrenG[w], где childrenG[w] —
xor-сумма гранди-значений всех поддеревьев вершины w
v v

w u
 2
60 баллов: O(N )
Теперь ясно, как следует изменить рекурсивную процедуру
DFS2(v, u), чтобы она работала за O(N) для одного значения v.
DFS2(v, u, xor_val):
| val[u] = xor_val
| for w - сын u:
| | DFS2(v, w, xor_val xor G[w] xor childrenG[w])
Теперь наше решение единожды запускает обход в глубину для
каждой вершины v, а значит работает за O(N2).
We need to go deeper...
Что нам надо?
Давайте поставим цель. Мы хотим обойти дерево в глубину, при
этом в каждой вершине v:
1) получить в каком-нибудь виде множество всех ходов из
вершины v — обозначим его M[v].
2) взять MEX от этого множества.
Под ходом мы понимаем гранди-значение, в которое ведёт ход.
Рассуждаем: как можно получить в вершине множество ходов?
Во-первых, есть ход в корень v, дающий гранди-значение
childrenG[v].
Анализируем множество ходов
Во-вторых, есть множество ходов в дочерние v

поддеревья. Рассмотрим поддерево дочерней

вершины ui. u1 ui uk

Легко пересчитать из уже посчитанного

множества M[ui], какие нам добавятся ходы
в поддерево ui.
g
Утверждение: ход в гранди-значение g
превратится в ход
g xor (childrenG[v] xor G[ui])
(иными словами, сверху прицепятся все
поддеревья кроме самого ui).
Какая нам нужна структура данных?
Подытожим: M[v] = sum(ci xor M[ui]) + {childrenG
[v]}
G[v] = MEX(M[v]).
Значит нам нужна структура данных, которая:
1) содержит множество неотрицательных целых чисел
2) позволяет быстро проксорить всё множество с какой-то
константой
3) позволяет быстро объединять множества
4) позволяет быстро считать MEX по множеству.
Такая структура данных существует! И это…
Битовый бор!
Рассмотрим бор, построенный на двоичной
0
записи содержащихся в множестве чисел. 000
0
Гранди-функции в нашем дереве не 1 001

превзойдут N, значит глубина бора не 0 010

0 1
превосходит logN.
011
Как быстро посчитать MEX на битовом боре?
1 0
Поставим флаг во все вершины бора, 1 101
поддерево которых полное. Тогда с помощью 1
этих пометок легко найти MEX за один
1 111
спуск — идём налево, если левое поддерево
не полное, иначе направо.
Отложенные операции рулят!
Что значит проксорить все числа в боре с какой-то константой c?
Это означает, что надо в некоторых слоях (соответствующих 1 в
двоичной записи c) поменять у всех вершин левого и правого сына
местами.
Всего таких вершин может быть много (например, в последнем
слое их линейное количество).
Нам на помощь приходят… отложенные операции!
В каждой вершине храним число-маску, в соответствии с которой
надо изменить поддерево. Приходя в вершину меняем местами,
если надо, сыновей, раздаём маску детям и двигаемся дальше.
Приливаем меньшее к большему
С объединением дела обстоят труднее. Тут нам поможет идея
приливания меньшего множества к большему.
Утверждение: если сливать множества, соответствующие поддеревьям,
каждый раз добавляя по очереди все элементы меньшего множества к
большему, количество операций вставки в бор будет O(N log N).
Доказательство: проследим за каким-нибудь числом. По ходу своей жизни
оно периодически ксорится с чем-то и меняет своё «место жительства»,
когда мы приливаем бор, содержащий её, в какой-то больший бор.
Заметим, что после каждого переливания размер множества,
содержащего число, увеличивается как минимум в два раза. Значит
каждое число переместится не более O(log N) раз.
Значит, в итоге произойдёт не более O(N log N) переливаний.
 2
100 баллов: O(N log N)!
Таким образом, суммарно мы произведём O(N log N)
операций вставки в бор, каждая из которых работает
за время O(log N).
Не забываем при добавлении числа в бор
пересчитывать флаги.
Операция взятия MEX работает за O(log N) для
каждой вершины.
Это решение, наконец, набирает 100 баллов!
Дальнейшие улучшения
Если хранить бор именно такой глубины, как надо (т. е.
в поддереве размера s он будет иметь глубину log s), то тогда
размер бора будет пропорционален размеру поддерева, а значит
итоговая сложность всего решения будет вообще O(N log N).
Полезная оптимизация: выделять вершины не с помощью
оператора new, а на статически заведённой памяти.
Альтернативный вариант использования бора: можно хранить
числа не от старших бит к младшим, а от младших к старшим.
Тогда можно сразу честно инвертировать детей во всех нужных
вершинах, так как это будет работать за O(min(c, size)), где c —
число, с которым мы ксорим, а size — размер поддерева.