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

Теперь рассмотрим медленное решение: занумеруем пары вида ($$$t$$$ — момент времени, $$$v$$$ — вершина) в порядке возрастания моментов времени, теперь по этим событиям будем писать следующее ДП: $$$dp_i$$$ — максимальное кол-во леденцов, которое мы можем собрать, если последний леденец заберем в событии с номером $$$i$$$.

Построим граф переходов в ДП между точками. Ребро между точками $$$j$$$ и $$$i$$$ будет тогда, когда $$$t_i - t_j \ge dist(v_i, v_j)$$$. Такой граф будет DAG-ом (так как каждое ребро ведет от события с меньшим временем в событие с большим временем), и мы можем написать по нему ДП. Но в таком графе будет много ребер, поэтому нужно уменьшить их количество.

Построим центроидную декомпозицию и сохраним для каждой вершины список её центроидов. Теперь для каждого события вида $$$(t, v)$$$ рассмотрим все центроиды $$$c$$$ вершины $$$v$$$ и добавим события $$$(t - dist(v, c), c)$$$ и $$$(t + dist(v, c), c)$$$, то есть, моменты, которые обозначают следующее: "мы еще не вошли в вершину $$$v$$$" и "мы уже вышли из вершины $$$v$$$". Мы можем так сделать из тех соображений, что у любых двух вершин будет минимум один общий центроид. Теперь свяжем события $$$(t - dist(v, c), c)$$$ и $$$(t, v)$$$ а также события $$$(t, v)$$$ и $$$(t + dist(v, c), c)$$$ ребрами, также внутри каждого центроида свяжем все события цепочкой в порядке возрастания времени. Теперь граф переходов содержит $$$O(m \cdot \log n)$$$ ребер, пишем то же ДП.

Асимптотика: $$$O(m \cdot \log^2 n)$$$.

Пусть $$$val_i$$$ — текущее количество предметов в $$$i$$$-м шкафе. Давайте поддерживать дерево отрезков на максимум по $$$val_i - lim_i$$$ и его позицию. Прибавление на отрезке делается с помощью ленивого обновления. После каждого прибавления нужно взять максимум во всём массиве, и до тех пор, пока он не меньше нуля, повалить соответствующий шкаф и установить на соответствующую позицию в дереве отрезков $$$-\infty$$$.

Чтобы эффективно валить шкафы, можно поддерживать ordered set из ещё целых шкафов. Тогда если мы хотим повалить шкаф, мы можем за $$$O(\log n)$$$ найти ближайший права целый шкаф и проверить, падает ли текущий шкаф на него. Если падает, то добавим этот шкаф в очередь и позже повторим с ним тот же алгоритм. Отвечать на запрос количества целых шкафов можно за $$$O(\log n)$$$ с помощью функции order_of_key.

Асимптотика: $$$O(n \cdot \log n)$$$.

Сумма $$$a_i$$$ всегда входит в ответ, значит её можно не рассматривать. Пусть перестановка $$$p$$$ описывает порядок, в котором мы едим куски пиццы: $$$p_i$$$ — это момент времени, в который мы съедим $$$i$$$-й кусок. Тогда задача сводится к минимизации суммы $$$b_i \cdot p_i$$$. Заметим, что всегда выгодно отсортировать $$$b_i$$$ по убыванию и в таком порядке назначать $$$p_i$$$ по возрастанию.

Асимптотика: $$$O(n \cdot \log n)$$$.

Вначале давайте решим немного другую игру: пусть изначально в каждой вершине лежит либо не лежит камень, за один ход можно выбрать любую вершину, в которой есть камень, удалить его и добавить по одному камню во все вершины на расстоянии $$$\le k$$$. Эта задача решается методом Шпрага-Гранди. Обозначим за состояние камень, лежащий в определённой вершине. Тогда значение Шпрага-Гранди для этого состояния равна сумме независимых игр — вершин, лежащих на расстоянии $$$\le k$$$.

Теперь поймём, почему эта и исходная игры эквивалентны. В исходной игре тоже прибавляются камни в вершины на расстоянии $$$\le k$$$, но после хода количество камней в каждой вершине берётся по модулю $$$2$$$. Это означает удаление каждой пары одинаковых игр. На самом деле эти пары никак не влияют на значение Шпрага-Гранди: если какой-то игрок делает ход в одной игре пары, другой игрок всегда может сделать такой же ход во второй игре, следовательно значение Шпрага-Гранди для суммы этих двух игр равно $$$0$$$.

Асимптотика: $$$O(n^2)$$$.

В тестах $$$1$$$ и $$$2$$$ у всех рёбер $$$p_i = 100\%$$$. Чтобы решить эти тесты, можно найти кратчайший путь алгоритмом Дейкстры и $$$q$$$ раз интерактивно пройтись по этому пути.

В тесте $$$3$$$ у всех рёбер $$$a_i = x$$$, $$$b_i = x + 1$$$, то есть граф представляет собой цепь с мультирёбрами. В этом тесте всегда оптимально брать ребро с минимальным весом из достижимых из текущей вершины.

Тест $$$4$$$ представляет собой несколько непересекающихся цепей из вершины $$$1$$$ в вершину $$$n$$$. Давайте посчитаем матожидание длины пути для каждой цепи и в начале каждого взаимодействия будем выбирать цепь с минимальным матожиданием из доступных.

Матожидание длины пути равно сумме матожиданий весов рёбер из $$$x$$$ в $$$x + 1$$$ для всех $$$x$$$ в цепи. Чтобы посчитать матожидание длины ребра из $$$x$$$ в $$$x + 1$$$, отсортируем все такие рёбра по возрастанию веса. Пусть $$$i$$$-е по возрастанию веса ребро имеет вес $$$w_i$$$ и вероятность $$$p_i$$$. Тогда матожидание равно $$$\sum_{i = 1}^{k} (w_i \cdot p_i \cdot \prod_{j = 1}^{i - 1} (1 - p_j))$$$.

В тестах $$$5$$$ и $$$6$$$ у всех рёбер $$$a_i < b_i$$$, то есть дан направленный ациклический граф. На нём можно посчитать $$$dp_i$$$ — матожидание длины пути из вершины $$$i$$$ в вершину $$$n$$$, и во время взаимодействия каждый раз переходить по ребру с минимальным $$$w + dp_b$$$. Формула ДП схожа с формулой матожидания в $$$4$$$ тесте: отсортируем исходящие рёбра по возрастанию $$$w + dp_b$$$, тогда матожидание равно $$$\sum_{i = 1}^{k} ((w_i + dp_{b_i}) \cdot p_i \cdot \prod_{j = 1}^{i - 1} (1 - p_j))$$$.

В тестах $$$7 - 10$$$ нет дополнительных ограничений. Авторское решение выбирает подмножество рёбер, образующее направленный ациклический граф, в котором для каждой вершины $$$v$$$ есть ребро в вершину $$$u$$$ c $$$u > v$$$ и $$$p = 100\%$$$, и запускает для этого подграфа решение для тестов $$$5$$$ и $$$6$$$.

Генерировать корректные подмножества можно так: заранее добавим все необходимые рёбра в граф, остальные рёбра случайным образом перемешаем. Будем проходиться по ним в этом порядке и добавлять очередное ребро, если оно не образует циклов. Локально сгенерируем много таких графов и выберем тот, у которого $$$dp_1$$$ максимально, запишем его топологическую сортировку в код решения, и в решениии будем учитывать только те рёбра, у которых $$$pos_a < pos_b$$$ ($$$pos_v$$$ — позиция вершины $$$v$$$ в топологической сортировке).

Посчитаем $$$add_{i, c}$$$ — сколько прибавится к общему количеству подпалиндромов, если символ на позиции $$$i$$$ заменить на $$$c$$$. Тогда ответ равен общему количеству подпалиндромов плюс максимум по $$$add_{i, c}$$$.

Переберём позицию центра палиндрома и посчитаем вклад палиндромов с таким центром в $$$add$$$. Разберём решение для палиндромов нечётной длины, для чётной решается аналогично. Пусть центр палиндрома находится в позиции $$$i$$$. С помощью хешей и двоичного поиска найдём минимальные $$$x$$$ и $$$y$$$ такие, что $$$s_{i - x} \ne s_{i + x}$$$ и $$$s_{i - x - y} \ne s_{i + x + y}$$$. Если мы изменением одного символа сделаем $$$s_{i - x} = s_{i + x}$$$, то к общему количеству подпалиндромов прибавится $$$y$$$.

Также, если мы поменяем любой символ в отрезке $$$[i - x + 1; i + x - 1]$$$ кроме центрального, количество подпалиндромов уменьшится на расстояние от позиции изменения до ближайшей из $$$i - x$$$ и $$$i + x$$$. Это прибавление арифметической прогрессии на отрезке, его можно делать при помощи двойного разностного массива.

Асимптотика: $$$O(n \cdot \log n)$$$.

Скоро будет.

Скоро будет.