Ага, мы тоже задавали до бродкаста, нам ответили Read the problem statement.

M: возьмём и положим все полиномы в мультисет с компаратором, сравнивающим значение полинома A в точке x_A и полинома B в точке x_B (начинается всё из x = 1), а дальше будем составлять последовательность по условию задачи: забираем из мультисета полином с наименьшим значением и вычисляем, плюсуем его точечку и кладём обратно, и так ещё k - 1 раз.

В B я придумал какую-то глупость, не знаю, насколько она близка к реальности. Диагонали разного цвета не пересекаются, посчитаем количество клеток каждого цвета под боем, думая о диагоналях, как о строчках (/) и столбцах (\) в прямоугольной матрице, тогда количество клеток под боем можно посчитать по формуле включений-исключений: rows * n + columns * m - rows * columns. Из этого надо ещё вычесть «лишние» клетки, потому что диагонали на самом деле все разной длины.

Пусть мы циклически сдвинули последовательность 1,2,3..n на k вправо, тогда последовательность примет вид k+1,k+2...n-1,n,1,2,3..k можно убедится что при каждом ходе в раунде мы переходим на к клеток вправо циклически, так мы переходим пока не попадем на перевернутую карту, то есть можно подсчитать, что на каждом раунде убирается lcm(n,k)/k тогда нужно сыграть n/(lcm(n,k)/k) = n*k/lcm(n,k) = gcd(n,k) раундов.

Can you explain in more details problem K?

K can be done by dp with a convex hull trick.

I would call it "divide and conquer" rather than "meet in the middle".

Можно по-подробнее про А? Мы потратили немало времени на то, чтобы понять, как по набору множеств потомков за O(N^2) получить список пар, которые одновременно находятся хотя бы в одном множестве — не вышло, написали решение, которое описал Madiyar комментом выше.

Вместо баланса можно хранить сколько пар уже взято, это более понятно :)

Мы решали А похожей идеей. Правда граф не конденсировали. Честно пускали дфс из каждой вершины, если в ней еще не были, и за дфс запихивали в битсет(назовем его Cur) все вершины, которые мы прошли в этом дфс. Пройдем по всем единичкам в битсете Cur и к битсетам(у нас для каждой вершины есть битсет вершин, с которыми эта вершина ассоциативна) всех вершин, в которых единички сделаем Or битсета Cur. Понятно, что если мы запустили из этой вершины дфс, из всех вершин, до которых мы добрались, запускать дфс бессмысленно, так как ответ останется таким же. Оценивать это решение не умею, может быть что-то около O(N^2)

H — будем считать ожидание времени до конца — величину D[components][v], где components — отсортированный вектор размеров компонент связности (таких всего 627, кстати), и мы стоим в вершине v. Формула пересчета — линейная, но внутри группы с одним components зависимости циклические, поэтому внутри группы будем считать Гауссом. А по components группы состояний образуют ациклический граф, поэтому получается решение а-ля динамика с Гауссом, которая работает за 627 запусков Гаусса.

Построим суффиксное дерево. С помощью двоичных подъёмов можно для каждой строки определить вершину, в которую ведёт ребро, в середине которого мы бы оказались если бы искали её в суфф дереве как в боре. Давай в каждой вершине дерева хранить список длин "хороших" подстрок, которые кончаются в ребре, которое ведёт в неё. Выпишем вершины в порядке захода в них. Тогда когда к нам приходит запросов можно рассмотреть два случая:

1. Ответ лежит на ребре. Находим его.
2. Иначе вычитаем из k число хороших строк, которые длиннее нашей и лежат на ребре. Задача свелась к k-статистике на подотрезке in[v] + 1, out[v]. Это можно делать с помощью дерева отрезков, храня в каждой вершине ДО сет из длин, которые встречаются на подотрезке и выписывая из каждой вершины с разбиения отрезка первые k чисел.

Итого решение работает за . При желании можно хитрыми махинациями переписать k-статистику за и решение станет не зависеть от k, то есть, .

Код: #1zLpMn

P.S. Видимо, альтернативно можно решать суффиксным массивом. Для этого можно определять лексикографические границы заданной подстроки. Это всё ещё будет k-статистика на отрезке, однако это решение представляется мне громоздким и более сложным в реализации.

Идейно простое решение (немного не успели на контесте, но в дорешку зашло): возьмём все подстроки из запросов (а из запросов 3 типа — дополнительно подстроки + большой символ в конце), и тупо посортим (хешами, итоговая сортировка за ).

Поверх посорченного массива сделаем дерево интервалов, которое умеет добавлять элемент за и считать k-ую статистику на отрезке за . Итого получается .

Бин. поиск по ответу. Степени, которые  > 4 очень быстро заканчиваются. Их быстро смерджим и в бин. поиске используем lower_bound. Для остальных, если они есть, можно посчитать число элементов оттуда, меньше середины отрезка в бин. поиске с помощью формулы включений-исключений.

Код: #aWIhkW

P.S. Теоретически должно заходить и когда мерджим последовательности с  > 3, но на деле это получает TL. По крайней мере у меня.

Я тоже минут 40 смотрел. За это время успел посчитать на бумажке ответ, и он у меня сошелся с моим решением. Ну я забил и решил так отправить.

Переберем, какая вершина будет нижней, а из них самой левой в многоугольнике. Отсортируем все вершины, которые выше или на той же высоте и правее по углу относительно неё. Дальше динамика: до какой вершины дошёл многоугольник, какое подмножество цветов уже покрыто, добавляем по одному треугольнику.

Ни кто не знает?