Всем привет!

Любители ли вы задачи, которые расчитаны на Ad Hoc решение? Я — терпеть не могу! Поэтому я решил сделать подборку идей, которые могут быть применены к достаточно большому классу задач. Добавляйте ещё, если о чём-то забыл. :)

1. Слияние множеств за амортизированно. Если у нас есть некоторые множества, которые нам потом нужно будет соединять, поддерживая промежуточные результаты, то можно делать это в лоб, всегда добавляя меньшее множество к большему. Таким образом, каждый элемент будет перенесён в какое-то другое множество не более, чем раз, так как новое множество для него каждый раз будет увеличиваться хотя бы в два раза. На этом, в частности, основана одна из версий общеизвестного DSU. Из применений — можно сливать множества внутри обхода дерева в глубину и таким образом можно для каждой вершины в какой-то момент времени подержать в руках множество всех элементов её поддерева.

2. Подвохи в задачах. Часть 1. Ни для кого не секрет, что иногда авторы пытаются скрыть важные детали условия. Так, я однажды встретил в разделе input ограничения . И сразу и не скажешь, что на самом деле .

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

    int a[n];
    ...
    map<int, int> sub_gcd[n];
    /*
    Ключ - gcd,
    Значение - наибольшая длина такая что gcd(a[i - len], ..., a[i]) равно ключу.
    */
    sub_gcd[0][a[0]] = 0;
    for(int i = 1; i < n; i++)
    {
        sub_gcd[i][a[i]] = 0;
        for(auto it: sub_gcd[i - 1])
        {
            int new_gcd = __gcd(it.first, a[i]);
            sub_gcd[i][new_gcd] = max(sub_gcd[i][new_gcd], it.second + 1);
        }
    }

4. От статичного множества к расширяемому за . Пусть для какого-то статичного множества мы умеем вычислять функцию, такую что , где — функция, которую мы также можем быстро вычислять. Например, — количество элементов множества, меньших , . Или — количество вхождений строк из в строку , — всё ещё операция суммы.

Ценой дополнительного в асимптотике мы можем научиться добавлять в множество новые элементы и всё ещё уметь вычислять эту функцию. Для этого заведём не пересекающихся множеств, дающих в объединении исходное и чтобы при этом размер -го множества был равен либо , либо . Теперь при добавлении элемента добавим его в -ое множество и будем перестраивать все множества так, чтобы указанное ограничение выполнялось. Таким образом -ое множество будет потреблять операций на каждые шагов, где — стоимость построения множества из элементов с нуля, обычно что-то порядка . Об этой оптимизации я узнал от Burunduk1.

5. -подмножества. Допустим, у нас есть множество чисел и мы хотим что-то узнать о том, что представляют собой исключающие или (xor) их подмножеств. Тогда мы можем представить числа как вектора в пространстве -мерных векторов над полем остатков по модулю 2. Оно интересно в частности тем, что в нём применимы основные алгоритмы линейной алгебры. Например, здесь показано, как, поддерживая базис в хорошем виде отвечать на запросы добавления нового вектора в множество и поиска k-го в порядке возрастания возможного xor подмножества элементов: link. (Задача от PrinceOfPersia с Hunger Games)

6. Циклы в графе как линейное пространство. Сопоставим каждому набору простых циклов в графе -мерный вектор линейного пространства на , у которого единица обозначает наличие соответствующего ребра в наборе. Можно ввести комбинацию циклов как сумму векторов в этом пространстве. Тогда можно показать, что множество циклов, получаемых добавлением одного ребра к дереву обхода в глубину будет содержать базис этого пространства. Комбинацию циклов можно трактовать как единый цикл, который проходит по рёбрам из вектора нечётное число раз, а по остальным — чётное, в такой интерпретации мы можем разложить любой не обязательно простой цикл на набор простых, а любой путь — на комбинацию простого пути и набора простых циклов. Это оказывается полезным если нас интересуют пути, в которых повторный проход по ребру аннулирует его вклад — например, если нас интересуют xor на путях. Пример задачи: 724G - Xor-матическое число графа

7. Алгоритм Мо. Вариант sqrt-декомпозиции. Не вдаваясь в подробности, основная идея в том, что если мы умеем неамортизированно добавлять элемент в множество (то есть, с возможностью отката), то мы можем разбить наш массив на группы по sqrt элементов, а запросы разбросать по блокам, в которых лежат их левые половины. Затем для каждого блока можно начать добавлять элементы с его границы и до конца массива. При этом, если мы наткнулись на правую границу запроса, добавим в множество элементы, которых не хватает до левой границы запроса, ответим на него, а затем откатим добавленные элементы.

8. Алгоритм Диница за . Данный алгоритм за и без того летает на большинстве тестов. Однако, буквально двумя новыми строчками можно существенно улучшить его асимптотику. Для этого достаточно добавить к алгоритму идею масштабирования — перебираем сверху вниз некоторую степень двойки и, пока это возможно, рассматриваем только рёбра, веса которых не меньше, чем . Данная оптимизация и ведёт к озвученной асимптотике.

9. От расширяемого множества к динамическому за . Пусть мы для некоторого множества умеем выполнять неамортизированную операцию добавления элемента и считать какие-то запросы. Тогда мы можем за дополнительный времени научиться также обрабатывать в оффлайне запросы удаления из множества. Давайте для каждого добавления элемента x множества сопоставим момент, в который этот элемент покинет множество. То есть, определим для каждого элемента отрезок времени , на протяжение которого элемент присутствует в множестве. Теперь введём рекурсивную процедуру, обрабатывающую отрезок времени с тем условием, что когда мы в неё входим, в множество уже добавлены все элементы, отрезки которых целиком покрывают . Далее, поддерживая этот инвариант, мы рекурсивно запускаемся в половинки отрезка. Наконец, когда мы доберёмся до базы, отрезка длины 1, мы сможем выполнить запрос так, будто перед нами готовое статичное множество. Об этой идее мне также поведал Burunduk1, о чём я написал отдельный пост (про dynamic connectivity).

10. Линейные комбинации и матрицы. Часто, особенно в задачах динамического программирования нам нужно считать величину, которая является линейной комбинацией других величин. Что-то в духе . В таких случаях мы можем записать коэффиценты в матрицу и воспользоваться бинарным возведением в степень. Таким образом мы сможем получить асимптотику вместо . Как мы видим, разница весьма существенна.

11. Оптимизация матричного возведения в степень. Допустим, есть матрица A размера , и нам нужно часто вычислять значения , где x — какой-то вектор. Наивное решение требовало бы от нас операций. Однако, мы можем заранее посчитать двоичные степени матрицы A, чтобы затем сделать умножений матрицы на вектор, а не матрицы на матрицу. Тогда решение уже будет иметь асимптотику , что может оказаться существенным. Об этой идее в одном из своих комментариев поделился AlexanderBolshakov.

12. Магия эйлерова обхода. Рассмотрим такую задачу: дано дерево. Поступают запросы добавить число на поддереве и посчитать сумму на пути между заданной парой вершин. HLD? Как бы не так! Строим два обхода для дерева — в одном мы записываем сначала вершину, а затем её поддерево, а во втором наоборот — сначала поддерево, затем вершину. Можно заметить, что тогда разность префиксов из первого и второго обхода, включающих поддерево вершины v будет содержать исключительно те вершины, которые лежат на пути от неё к корню. Таким образом, задача сводится к прибавлению числа на подотрезке и сумме на префиксе. Эту идею мне рассказал Kostroma. Стоит также отметить альтернативное решение — хранить в каждой вершине дерева линейную функцию от её высоты и обновлять её у всех потомков вершины при запросе. Впрочем, оно, кажется, плохо обобщается.

13. Подвохи в задачах. Часть 2. Если дано k множеств, заданных явно списками, следует обратить внимание, что максимальное количество различных размеров таких множеств не превышает , где s — их суммарный размер. Имеет место также более сильное утверждение — не более объектов имеют размер, превышающий . Очевидный пример — когда нам даны несколько строк суммарной длины s. Менее очевидный пример — в разложении перестановки на циклы можно встретить не больше различных длин. Эта идея также имеет своё отражение в ряде теоретико числовых задач. Например, нам нужно посчитать что-то по всем числам, не превышающим большое число k, например, . Рассматриваем отдельно две группы чисел — числа, меньшие перебираем, а для остальных перебираем результат операции и считаем количество чисел, которые дадут такой результат целочисленного деления.
Ещё одно интересное следствие этой идеи — если в алгоритме Ахо-Корасик мы будем рассматривать пути до корня в дереве суффиксных ссылок, которые используют только вершины, являющиеся терминальными, то есть, соответствующие исходным строкам бора, то любой такой путь будет иметь длину .

14. Convex hull trick. Пусть мы имеем некоторую динамику вида , то мы можем поддерживать выпуклую оболочку линейных функций, которые здесь имеются, а затем искать максимум с помощью тернарного поиска или бинарного поиска по углу вектора нормали к линейным функциям.

15. xor- and- и or- свёртки. Пусть у нас есть кольцо многочленов, в котором или или . Как и в обычном случае , можно научиться умножать такие многочлены порядка за . Будем интерпретировать его как многочлен от переменных такой, что каждая переменная входит в него со степенью не выше 1 и набор переменных при определяется двоичной записью числа . Например, вместо будем видеть . Теперь заметим, что если рассматривать этот многочлен в вершинах куба , то за счёт того, что , получим, что при произведении двух многочленов в таких точках они будут сворачиваться именно согласно xor соответствующих номеров одночленов. or-свёртка получается аналогичным образом, но теперь мы рассматриваем значения в вершинах куба и потому имеем . and-свёртку предлагается додумать самостоятельно в качестве упражнения.

void transform(int *from, int *to) 
{ 
    if(to - from == 1) 
        return; 
    int *mid = from + (to - from) / 2; 
    transform(from, mid); 
    transform(mid, to); 
    for(int i = 0; i < mid - from; i++) 
    {
        int a = *(from + i);
        int b = *(mid + i);
        *(from + i) = a + b;
        *(mid + i) = a - b;
    }
} 

void transform(int *from, int *to) 
{ 
    if(to - from == 1) 
        return; 
    int *mid = from + (to - from) / 2; 
    transform(from, mid); 
    transform(mid, to); 
    for(int i = 0; i < mid - from; i++) 
        *(mid + i) += *(from + i); 
} 

void inverse(int *from, int *to) 
{ 
    if(to - from == 1) 
        return; 
    int *mid = from + (to - from) / 2; 
    inverse(from, mid); 
    inverse(mid, to); 
    for(int i = 0; i < mid - from; i++) 
        *(mid + i) -= *(from + i); 
}

Напоследок замечу, что or-свёртка даёт в точности сумму по всем подмаскам, а также что обратное преобразование для xor-свёртки совпадает с исходным, за исключением того, что в конце нужно поделить всё на n. Спасибо Endagorion за то, что рассказал мне о такой интерпретации преобразования Уолша-Адамара.

16. Прямое и обратное FFT для двух многочленов одновременно. Пусть — многочлены с действительными коэффициентами. Рассмотрим . Заметим, что , откуда следует, что .

Теперь в обратную сторону — пусть мы знаем для многочленов значения в корнях из единицы, а также знаем, что они имеют вещественные коэффициенты. Посчитаем обратное преобразование Фурье для . Тогда, в силу линейности преобразования Фурье, коэффициенты для окажутся вещественной частью обратного преобразования, а коэффициенты — мнимой.

17. Произведение многочленов по модулю с вещественнозначным FFT. Если модуль большой, нам может не хватать точности. Чтобы этого избежать, разбиваем многочлены и считаем . С учётом предыдущего пункта, это делается за два прямых и два обратных FFT.

18. Хеширование структур. Чаще всего хеширование применяют к строкам (т.е., последовательностям), но хешированию также хорошо поддаются другие классы объектов — в частности, деревья и множества чисел. Так, например, множество чисел можно хешировать многочленом . После этого объединению мультимножеств будет соответствовать сумма входящих хешей. Также можно, например, быстро пересчитать хеш для множества, ко всем элементам которого прибавили какое-то число, просто домножив хеш на основание в степени этого числа. Спасибо 300iq за то, что отметил это.

Корневые деревья можно хешировать следующей известной процедурой: возьмём мультимножество хешей поддеревьев. Затем если такое множество уже встречалось ранее, присвоим вершине соответствующий множеству номер, иначе присвоим вершине и множеству новый номер. Для некорневых деревьев имеет место похожая процедура — просто нужно подвешивать их за центр или центроид.

Кстати, немного о том, почему хеши вообще работают, если кто-нибудь ещё не задумывался — у многочлена степени в поле может быть не больше корней. Поэтому если из множества возможных аргументов мощности мы выбрали один, то вероятность того, что многочлены совпадают, но не равны тождественно (если точнее — их разность не равна тождественно нулю, но равна нулю в точке), не превышает . Соответственно, если у нас есть пар объектов, которых мы сравниваем, то вероятность того, что одна из проверок даст ложноположительный результат можно грубо оценить как . Из этих соображений можно выбирать поле (остатков по модулю), в котором мы будем работать.

Также есть вариант использовать как хеш для одного числа не , а случайно выбранное число и всё ещё суммировать их. Кто-нибудь умеет оценивать вероятность коллизий в таком случае?