Правила opencup'а с тех пор поменялись, теперь prewritten code разрешён =)

(ну а про фразу в посте — это разумеется полу-шутка: просто C у нас писать никому не хотелось, и поэтому от нечего делать страдали фигнёй с извлечением текста из pdf)

Это стандартный алгоритм на пересечение двух ДКА.

Да. Для каждой вершины будем хранить её двоичный подъем. Операции с деревом устроены так, что все двоичные подъемы всех вершин без проблем быстро пересчитываются. Чтобы узнать ответ на запрос, делаем бинпоиск (по ответу). Нас интересует, верно ли, что при подъеме на высоту K всех вершин каждая вершина-результат получилась из некоторых вершин вдоль одного пути. Как это проверять? Отсортируем все вершины по такому параметру: (вершина, где оказались в результате подъема; исходная глубина). Условие, что все вершины-результаты имеют нужный вид — при фиксированном первом параметре, когда глубина увеличивается, очередная вершина — потомок предыдущей. Все это легко делается при помощи двоичного подъема, в итоге N*log^2, проблем с TL-ем не было.

А можно подробнее про D? Вот нашёлся цикл. Насколько сильно его вычитать надо? Какой-то eps был? Или градиентный спуск?

А расскажите поподробнее про свой аллокатор. Что конкретно делаете и как это помогает?

В дорешивание Петрозаводска сдал решение за n*log(n) — то, что, видимо, и рассказывалось на разборе. Построим дерево разбора, в вершине хранится бинарная операция (/значение, если лист) + есть ли отрицание. У нас все бинарные операции коммутативны, поэтому детей можно переставлять. Размер поддерева = сумма размеров множеств (по числу элементов) по листьям в этом поддереве. Сразу договоримся, что размер правого поддерева меньше размера левого, а исходные числа сжаты (различных чисел всяко меньше 5*10^6, хотя, конечно, гораздо меньше). Теперь самое интересное. Для каждой вершины результат вычислений честно будем хранить в некотором массиве, своем для каждой вершины. Причем мы будем заботиться только о том, чтобы ответ располагался компактно — все числа шли бы подряд в любом порядке. Вычисления в дереве производим в таком порядке: сначала вычисляем для правого поддерева, потом для левого. Есть три вида операций — (l/!l)&r, l|r, l&!r. В первом случае в качестве ответа будет массив для правого поддерева, только из него кое-что нужно выкинуть (при выкидывании образуется дырка, её нужно заполнить последним элементом). Честно пройдем по нему и выкинем (как проверять, есть ли элемент в l? об этом позже). Во втором случае ответом будет ответ для l, к которому что-то из r приписали — честно проходимся по r, если в l нет, дописываем в конец. В третьем случае проходимся по r и честно из l удаляем. Как же проверять, есть ли элемент в l и если есть, то на какой позиции? Очень просто, заведем глобальный массив, в котором для каждого числа будем хранить, есть ли оно в последнем ответе, и если есть, то на какой позиции (легко понять, как это дело пересчитывается — используйте счетчики). Почему же это работает: да просто когда мы хотим воспользоваться этими глобальными массивами, то последняя операция была с левым ребенком, и они там насчитался правильно. Почему nlog(n)? Потому что всегда меньшее к большему. Код: http://pastebin.com/TDyCrf2E

Рекурсивный разбор можно сдать, если при рекурсивном спуске внутрь скобок за один раз обработать все "лишние" скобки типа таких: ((( ... ))).

Понятно, что по всем стоящим рядом одинаковым буквам всё разбивается на независимые куски. Для каждого куска надо посчитать все возможные расстояния между парами разных букв. В голову сразу приходит 26 FFT, но к счастью всё гораздо проще :) Если немного подумать, то для куска длины l расстояния 1 ≤ i ≤ l не бывает только если i — какой-то из периодов куска. Считаем все периоды при помощи префикс-функции и решаем задачу.

Нужно разбить все состояния на пары соседних и каждым ходом переходить в другое состояние в той же паре. Если общее количество состояний чётное, то играть за Алису, иначе за Боба (тогда нужно разбить на пары все состояния, кроме начального). n = 1 — особый случай.