A div2. Куда свернуть?

Посмотрим на векторное произведение на , численно равное . Знак векторного произведения определяется знаком синуса ориентированного угла между векторами (т.к. векторное произведение также равно ), а именно этот-то знак нам и нужно узнать.

Если произведение равно нулю, то это в данной задаче означает, что A, B и C лежат на одной прямой, а значит ответ — <>.

Если произведение больше нуля, то ответ — <>.

И, наконец, если оно меньше нуля, то ответ — <>.

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

Решение

B div2. Эффективный подход

Пусть число t стоит на позиции ind_t в первоначальной перестановке. Тогда, очевидно, пробегом слева направо это число будет найдено за ind_t сравнений, а пробегом справа налево — за n - ind_t + 1 сравнений. Заведем доп.массив, в i-й ячейке которого будет стоять число j такое, что a_j = i. Этот массив позволит обрабатывать каждый запрос за O(1) при помощи указанных выше формул. Доп. массив строится за O(n) пробегом по массиву a. Таким образом, окончательная асимптотика решения O(n + m).

Решение

C div2 — A div1. Отсеки летающей тарелки.

Обозначим за F_n ответ на задачу, где n — число инопланетян. Давайте предположим, что мы уже решили задачу для n - 1 инопланетянина, т.е. знаем значение F_n - 1. Попытаемся найти его для n инопланетян. Заметим, что младший по рангу (далее — просто младший) инопланетянин сможет покинуть 3-й отсек только тогда, когда все остальные инопланетяне перейдут в 1-й отсек. Значит, первые F_n - 1 действий нам известны. Далее младший инопланетянин может перейти во второй отсек. Чтобы он попал в 1-й отсек, требуется, чтобы остальные вернулись в первый. Значит, требуется еще F_n - 1 действий. Наконец, после того, как младший инопланетянин перейдет в 1-й отсек требуется еще F_n - 1 действий на возвращение n - 1 инопланетянина в 1-й отсек из 3-го. Таким образом, F_n = F_n - 1 + 1 + F_n - 1 + 1 + F_n - 1. Это уже позволяет найти F_n быстрым возведением матрицы в степень, но мы пойдем чуть дальше. Прибавим по 1 к левой и правой части равенства и после элементарных преобразований получим F_n = 3·(F_n - 1 + 1) - 1. Теперь легко угадать решение рекуррентного соотношения: F_n = 3ⁿ - 1.

Осталось научиться быстро вычислять значение F_n. В этом нам поможет бинарное возведение в степень. Асимптотика решения — O(log n).

Осталось упомянуть один "подводный камень": если 3ⁿ mod m = 0, необходимо не забыть, что ответ равен m - 1, а не  - 1, и разобрать этот случай.

И напоследок маленькая аналогия: перед вами только что была задача о Ханойских башнях с модификацией, заключающейся в том, что переносы дисков разрешены только между двумя парами стержней.

Решение

D div2 — B div1. Непослушные кучки камней

Рассмотрим следующую интерпретацию задачи: кучкам камней соответствуют вершины. Операции добавить кучку a к кучке b соответствует операция подвешивания поддерева вершины b к вершине a. Числа, записанные на вершинах, — размеры кучек. Задача — добиться такой конфигурации дерева, чтобы к каждой вершине было подвешено не более k поддеревьев, а сумма произведений чисел, записанных на вершинах, на глубину вершин (где глубина корня равна 0) минимальна. Чтобы добиться минимальности, требуется, во-первых, чтобы вершина с большим числом находилась не ниже, чем вершина с меньшим (иначе их можно просто поменять и получить меньшую сумму), а во-вторых, чтобы у каждой внутренней вершины, кроме, может быть, одной было ровно k потомков (второе условие также доказывается методом от противного). Осталось научиться быстро считать для такой конфигурации саму сумму. Для этого отсортируем массив размеров кучек, а затем будем действовать так: вначале прибавим к ответу сумму размеров кучек с 1-й по k-ю (в 0-индексированном, отсортированном в порядке невозрастания массиве), домноженную на 1; затем сумму размеров следующих k^2 кучек, домноженную на 2; и т.д. до конца массива. Чтобы быстро отвечать на запрос о сумме на отрезке, предподсчитаем суммы на префиксах сразу после того, как отсортируем массив. Теперь при k > 1 мы умеем находить ответ на запрос за O(log n). Если тем же соображениям следовать при k = 1, ответ на запрос будет занимать O(n) операций, а потому решение получит TL, если в большей части запросов k будет равно 1. Поэтому следует заранее посчитать ответ для k = 1 и запомнить его, чтобы отвечать на такие запросы за O(1).

Асимптотика решения — O(n · log n  +  q · log n).

Решение

E div2 — C div1. Юбилей

Сначала докажем ключевое утверждение: НОД(F_n, F_m) = F_{НОД(n, m)}.

Начнем издалека: выразим F_n + k через F_n и F_k. Получим следующую формулу: F_n + k = F_k·F_n + 1 + F_k - 1·F_n. Эта формула доказывается по индукции.

Теперь воспользуемся полученной формулой и заметим, что НОД(F_n + k, F_n) = НОД(F_k, F_n).

Осталось заметить в последней формулой аналогию с алгоритмом Евклида и осознать, что мы получили требуемое нам соотношение для НОД двух чисел Фибоначчи.

Итак, мы свели задачу к следующей: найти в заданном множестве подмножество из k (или хотя бы из k) элементов с максимально возможным НОД. А точнее, найти сам НОД такого подмножества.

Пусть ответ равен q. Тогда должно выполняться  -  ⌉ + 1 ≥ k (1).

Заметим, что для каждого из слагаемых из левой части неравенства существует отрезков, на которых его значение постоянно. Причем мы можем найти все эти отрезки и значения за . Точнее, нас интересуют такие q, что в q - 1 значение хотя бы одного из слагаемых меняется (очевидно, увеличивается). Таких значений тоже . Осталось перебрать их все и каждое попробовать в роли ответа (т.е., для каждого проверить неравенство (1)), а из подошедших выбрать максимум. Ответ всегда будет, т.к. единица подходит на роль q при любых входных данных.

Таким образом, мы нашли индекс искомого числа Фибоначчи. Само же число можно вычислить, быстро возведя матрицу в степень.

Решение

Асимптотика решения — .

D div1. Всего лишь таблица.

Научимся получать ответ. Поступим следующим образом: будем находить любую строку или столбец с отрицательной суммой и инвертировать его/ее. Заметим, что сумма всех чисел в таблице после таких операций неизменно будет возрастать. Очевидно, что возрастать бесконечно сумма не может. За один шаг сумма возрастает хотя бы на 2, а максимальное возможное изменение суммы относительно начальной — 200·n·m. Таким образом, всего потребуется не более 100·n·m операций (применения заклинания), каждая из которых выполняется за время O(n) или O(m). Итак, мы научились получать нужную таблицу за ~ 100⁴ действий.

Осталось восстановить ответ. Легко понять, что в него войдут те строки и столбцы, которые мы инвертировали нечётное число раз.

Решение

E div1. Путь благородного рыцаря

Решение 1

Нетрудно догадаться, что замки образуют дерево. Построим на этом дереве heavy-light decomposition. Над каждым путем построим персистентное дерево отрезков на сумму. В вершине дерева отрезков будет храниться 0, если замок на текущий момент не тронут варварами, и 1 в противном случае.

Каждый путь рыцаря можно при помощи нахождения lca разбить на не более чем два подпути, лежащие на пути от одного из концов маршрута к корню. Теперь будем решать задачу для каждого из подпутей отдельно. Будем последовательно обрабатывать пути из heavy-light decomposition и одиночные вершины, принадлежащие подпути. Нас интересует количество вершин на подпути, которые не посещались с года y + 1 по текущий, т.е. (в случае пути из декомпозиции) таких, что разность между значениями в текущей версии персистентного дерева и в версии, соответствующей году y (требуемая версия ищется бинпоиском в списке версий) равна нулю (случай с одиночной вершиной тривиальнее: достаточно просто хранить время посещения вершины). Как только количество подходящих вершин станет не меньше k, нам останется синхронно спуститься по двум версиям дерева, чтобы получить ответ.

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

Асимптотика решения: O(m·log² n) — в каждом запросе первого типа нам может потребоваться обновить какое-нибудь дерево отрезков, на что уйдет O(log n) операций; в каждом запросе второго типа нам встречается O(log n) путей декомпозиции, каждый из которых обрабатывается за O(log n) (вначале бинпоиск по версиям, затем запрос к дереву/спуск по дереву).

Реализация

Решение 2

Обойдем дерево dfs'ом, записывая в массив номер вершины в моменты входа и выхода (аналогия с правильными скобочными последовательностями). Причем как записи о входе, так и записи о выходе сопоставим 0. На этом массиве построим персистентное дерево отрезков.

Теперь, когда нам будет поступать запрос первого типа, будем сопоставлять позиции первого вхождения вершины в массив  + 1, а позиции последнего вхождения —  - 1.

Для того чтобы научиться обрабатывать второй запрос, заметим, что для нахождения количества посещенных вершин на произвольном подпути между вершинами a и b такими, что обе вершина a лежит на пути от вершины b до корня, нам требуется найти сумму чисел, сопоставленных позициям между первыми вхождениями вершин в созданном обходом в глубину массиве.

Теперь на каждом из подпутей в отдельности запустим двоичный поиск по ответу — позиции искомого замка. Для проверки ответа воспользуемся приведенным в предыдущем абзаце соображением.

Асимптотика решения: O(m·log² n) — в каждом запросе первого типа нам может потребоваться обновить дерево отрезков, на что уйдет O(log n) операций; в каждом запросе второго типа O(log n) итераций бинпоиска по ответу, каждая из которых обрабатывается за O(log n).

Реализация

upd. Исправил маленькую неточность в неравенстве в разборе E div2 — C div1. В левой части добавился +1.