Задачи, которые не успели написать, разберу кратко. Задавайте вопросы.

233A - Идеальная перестановка

Идея: Gerald Реализация: tunyash Разбор: fdoer

Эту задачу можно было решать разными способами, например, таким: рассмотрим перестановку p, в которой p_i = i, то есть просто последовательность чисел от 1 до n. Очевидно, для неё условие p_pi = i выполняется всегда. Осталось только преобразовать её таким образом, чтобы выполнялось и второе условие: p_i ≠ i. Для этого поменяем местами каждые два соседних элемента, т.е. для каждого k: k * 2 ≤ n поменяем местами значения p_2k - 1 и p_2k. Нетрудно убедиться, что для полученной перестановки оба условия выполняются всегда.

233B - Неквадратное уравнение

Идея: tunyash Реализация: tunyash, Gerald Разбор: fdoer

Для начала найдем диапазон значений, которые может принимать s(x). Так как из уравнения x² ≤ n, а по условию n ≤ 10¹⁸, x ≤ 10⁹, иначе говоря, десятичная запись любого решения не длиннее 10 цифр. Значит, максимальное значение s_max = s(9999999999) = 10·9 = 90 (на самом деле это грубая оценка, s_max даже меньше, но нам достаточно и её).

Переберем значение s(x): 0 ≤ s(x) ≤ 90. Получаем обычное квадратное уравнение относительно переменной x. Осталось решить его и проверить равенство того значения s(x), что мы зафиксировали, сумме цифр в разрядах полученного корня. Если корень нашелся и равенство выполнено, обновим ответ.

Пожалуй, самое важное в этой задаче — аккуратно и без ошибок вычислений считать дискриминант.

Подчеркну, что для решения задач div2.A и div2.B не требовалось знание массивов.

232A - Циклы

Идея: tunyash, fdoer Реализация: tunyash Разбор: tunyash

Будем добавлять ребра в порядке сортировки сначала по вершине в меньшим номером, затем с большим (просто два for'a). Если добавление ребра вызывает переполнение кол-ва циклов, не добавляем его. Считать количество циклов, которые добавятся можно за O(n) (могут появиться только циклы, содержащие добавленное ребро, следовательно достаточно перебрать третью вершину). Очевидно, что это найдет какой-то ответ, потому что, добавив два ребра из вершины мы всегда можем получить 1 треугольник. Тогда получается, что ответ всегда есть. Можно довольно просто доказать, что мы уложимся в 100. Асимптотика решения O(n³).

Доказательство

• Первыми несколькими шагами алгоритма мы сгенерируем полный граф. Потому что каждое ребро можно будет добавить
• Полученное количество треугольников — C(p, 3) для какого-то p. C(p, 3) ≤ k при этом p максимально.
• Для данных ограничений p ≤ 85.
• После первой фазы алгоритма, если из некоторой вершины мы добавляем u ребер, то количество треугольников увеличивается на C(u, 2).
• Получается, мы представляем маленькое число  ≤ C(85, 2) в виде суммы C(i, 2).
• Первое число, которое мы вычтем, будет отличаться от нашего не более чем на C(85, 1) = 85, поскольку C(n, k) - C(n - 1, k) = C(n - 1, k - 1).
• Второе число — не более чем на C(14, 1) = 14.
• Далее можно применять данную оценку аналогично.
• Для всех возможных k данный алгоритм укладывается в 90 вершин.

Может быть есть что-то более красивое, но вообще на контесте можно было остановиться пункте на пятом и забить.

232B - Таблица

Идея: tunyash, Skird Реализация: tunyash Разбор: tunyash

• Пусть s_i — количество точек в столбце i.

• На картинке изображены два соседних квадрата n × n, A — количество вершин в левой части рисунка (это один столбец), B — количество точек в средней области и C — количество точек в правой области (это тоже один столбец). По условию, имеем:

• Следовательно A = C.
• Таким образом
• Разделим столбцы на классы эквивалентности по признаку . Для всех a и b из одного класса s_a = s_b.
• cnt_a — количество столбцов в классе с .
• Существует (C_n^k)^cnt_a способов нарисовать по x точек в каждом из столбцов этого класса независимо от других классов.
• dp[i][j] — количество способов заполнить классы 1, ... i таким образом, что .
• cnt_i принимает и . Посчитаем (C_n^a)^cnt_i для всех a и cnt_i и будем использовать при подсчете дп. Получаем сложность O(n²·k).

232C - Графы Доу

Идея: tunyash, Gerald Реализация: tunyash, Gerald Разбор: tunyash

Будем рекурсивно разворачивать граф, сводя задачу к поиску кратч. пути в графаз меньших порядков. Заметим, что вершина |D(n - 1)| + 1 — точка сочленения (кроме случаев n ≤ 2, но для них описанные ниже равенства так же выполняются).

Тогда, если вершины находятся по разные стороны от нее, то путь обязательно через нее проходит.

Пусть dist(a, b, n) — длина кратчайшего пути между a и b в графе порядка n.

Красным обозначены ребра, синим — пути. Записанная формула обозначает, что мы можем пойти из вершины a по пути 1 в вершину 1, затем по прямому ребру в вершину |D(n - 1)| + 1 и по пути 3 в вершину b, либо пойти по пути 2, попасть в вершину |D(n - 1)|, пройти по ребру в вершину |D(n - 1)| + 1, а затем по пути 3 в вершину b. Если обе вершины лежат в меньшей половине графа — то

Если они лежат в большей половине, то нужно дополнительно разобрать случай прохождения пути через точку сочленения, то есть

Если искомый путь проходит через точку сочленения, то для каждой вершины мы можем пройти либо в вершину 1, либо в вершину |D(n - 1)| + 1, а затем по прямому ребру в вершину |D(n - 1)| + 1. Если путь не проходит через точку сочленения, то рассмотрим его в графе меньшего порядка.

Можно заметить, что для каждого k будет не более 4 различных запусков dist(i, j, n).

Как это понять? Во первых, если отбросить запросы, где либо a = 1, либо b = |D(n)|, все запросы получаются из первого последовательным отнятием от изначальной пары (a_i, b_i) одинаковых чисел Фибоначчи (по построению D(i) — числа Фибоначчи). Получается, таких запросов будет O(n). Запросы вида (1, a) и (a, |D(n)|) можно рассмотреть отдельно, они хорошо выражаются из самих себя. Учитывая то, что все другие запросы получаются друг из друга прибавлением или отнятием чисел Фибоначчи, запросы этого вида тоже будут получаться друг из друга таким образом. Таким образом, у нас будет не более O(1) серий по O(n) запросов. Это не совсем строго, но, вроде, понятно. Это довольно нетривиальный момент, рекомендую задавать вопросы, если непонятно.

Получим асимптотику на запрос (логарифм возникает из соображения о том, что размеры графов в зависимости от порядка растут экспоненциально). Важно было запускать алгоритм не для данного n, а для наименьшего n, такого, что max(a, b) ≤ D(n - 1)

232D - Забор

Идея: tunyash, Gerald Реализация: fdoer Разбор: fdoer

В разборе этой задачи подразумевается, что читатель имеет представление о суффиксных массивах и о быстром нахождении lcp (наибольшего общего префикса) двух суффиксов строки. Об этом можно почитать, например, на e-maxx.ru.

Итак, пусть d и d' — массивы такие, что d_i = h_i - h_i + 1, d'_i =  - d_i для любого 1 ≤ i ≤ (n - 1). Тогда мы можем переформулировать условие, при котором два куска забора считаются подходящими, следующим образом:

• куски не пересекаются, то есть, нет ни одной доски, такой, что она содержится в обоих кусках забора;
• куски имеют одинаковую ширину;
• для любого i (0 ≤ i ≤ r₁ - l₁ - 1) выполняется d_l1 + i = d'_l2 + i (если ширина забора — 1, это выполняется всегда).

Отсюда возникает следующая идея: для ответа на запрос нам достаточно узнать, сколько подотрезков массива d' длины (r - l) совпадают с отрезком массива d, соответствующим этому запросу, и при этом не пересекаются с ним ни в каком индексе. Построим суффиксный массив sa на последовательности-конкатенации массивов d и d', между которыми поставим еще разделитель — число, которого ни в одном из этих массивов нет. Запомним также для каждого суффикса d_i его позицию pos_i в суффиксном массиве. При поступлении нового запроса на отрезке l...r все куски забора, подходящие по второму и третьему условиям, будут началами суффиксов, лежащих в суффиксном массиве подряд на позициях bound_left...bound_right, причем bound_left ≤ pos_l ≤ bound_right и lcp(bound_left...bound_right) ≥ (r - l). Поэтому границы этого отрезка можно найти с помощью бинарного поиска. В зависимости от реализации функции lcp для отрезка значения bound мы определим за или за .

Теперь осталось найти число позиций из sa_{boundleft...boundright}, удовлетворяющих еще и первому условию, т.е. таких, которые соответствуют суффиксам d', префикс длины r - l которых не пересекается по индексам с отрезком (l...r - 1). Иными словами, количество i (bound_left ≤ i ≤ bound_right) таких, что либо n + 1 ≤ sa_i ≤ n + l - (r - l) - 1, либо sa_i ≥ n + r (суффиксы d' начинаются в конкатенации с позиции n + 1, т.к. в массиве d (n - 1) элемент, а на n-ном месте расположен разделитель). Это тоже классическая задача поиска количества чисел из заданного диапазона на заданном отрезке массива, она может быть решена за на запрос.

Её можно решать, например, offline с помощью метода scanline и любой структуры данных, поддерживающей запросы суммы на отрезке и увеличения в точке, либо online с помощью персистентных/двумерных структур вроде дерева отрезков.

Таким образом, вкратце алгоритм выглядит примерно так:

• построение массивов d и d'. Построение на конкатенации суффиксного массива.
• препроцессинг для вычисления lcp на отрезке

Для каждого запроса:

• определение промежутка (bound_left...bound_right) с помощью двух бинарных поисков, обращающихся к lcp на отрезке.
• запрос на число суффиксов, которые лежат в суффиксном массиве на этом промежутке и которые соответствуют подотрезкам, не пересекающимся с отрезком запроса.

Если массив строить за , запрос lcp выполнять за O(1) с предподсчетом за (с RMQ на разреженных таблицах), а числа из диапазона искать за на запрос, итоговая асимптотика получается . Однако решения, выполняющие запрос lcp за логарифм с использованием, например, дерева отрезков, тоже укладывались в ограничения.

232E - Быстрая Черепаха

Идея: tunyash Реализация: tunyash, KAN Разбор: tunyash

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

С помощью этих данных мы получим ответы на все запросы, точки которых лежат по разные стороны от выбранного столбца за n/32 на запрос (просто сделаем and битсетов). На картинке кружочками обведены две клетки, через которые может проходить путь между точками запроса.

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

Запросы можно выполнять онлайн, храня для каждой клетки битсетов — множеств доступных клеток на столбцах, выбираемых центральными.

Альтернативное решение от mrNobody. Оно оказалось быстрее и проще авторского, но, к сожалению, он не смог сдать его на контесте.

• Будем считать динамику range[i][j][k] — самую верхнюю и самую нижнюю клетку столбца k, доступную из клетки (i, j). Ее можно считать аналогично динамике из авторского решения.
• Кроме того посчитаем динамику able[i][j][k] — доступна ли хотя бы одна клетка столбца k из клетки (i, j) при движении влево и вверх.
• Обе эти динамики можно посчитать за O(n·m²) времени и памяти (потом будет понятно, что на памяти можно сэкономить).
• Рассмотрим запрос (x₁, y₁) (x₂, y₂). Утверждается, что путь из (x₁, y₁) (x₂, y₂) существует тогда и только тогда, когда и верно able[x₂][y₂][y₁].

• Действительно, рассмотрим три пути. 1 — из (x₁, y₁) в самую верхнюю доступную клетку столбца y₂. 2 — из (x₁, y₁) в самую нижнюю доступную клетку столбца y₂ и 3 — из (x₂, y₂) в одну из клеток столбца y₁. Если эта клетка расположена ниже (x₁, y₁), то путь 3 пересекает путь 2, а значит мы можем пройти по пути два до точки пересечения, а затем по пути 3 до точки (x₂, y₂).
• Случай пересечения путей 1 и 3 аналогичен.
• Мы получили решение за O(n·m² + q) времени и такое же количество памяти, однако можно заметить, что хранить все состояния динамики не обязательно, достаточно только q из них. Пользуясь этим, можно сократить используемую память до O(nm + q).