6 алгоритмов решения задач по спортивному программированию

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

Сортировка подсчетом

Сортировка подсчетом − наиболее частый способ решения задач по спортивному программированию. Этот алгоритм сортировки работает для данных, ключи которых находятся в некотором известном числовом диапазоне. Его идея заключается в том, чтобы подсчитать количество элементов, соответствующих каждому ключу, и записать это количество в ячейку массива (индекс ячейки − это ключ, значение − подсчитанная частота ключа), а после − вывести элементы нужное количество раз по порядку.

Пример: сортировка массива чисел

Дан массив чисел и известен числовой диапазон, в котором они располагаются. Например, массив: 1, 4, 1, 2, 7, 5, 2. Нам известно, что эти числа принадлежат промежутку от 0 до 9.

1. Заведем массив, в котором будем подсчитывать, сколько раз встречается то или иное число.

Индекс (ключ):     0 1 2 3 4 5 6 7 8 9
Количество:     0 2 2 0 1 1 0 1 0 0

2. Распечатываем каждое число столько раз, сколько мы получили при подсчете:

1 1 2 2 4 5 7

Важно отметить

1. Сортировка подсчетом достаточно эффективна, если диапазон чисел массива не сильно превосходит количество самих чисел. Поразмышляйте над такой ситуацией: [10000, 5000, 5, 10] и диапазон [5; 10000] соответственно.
2. Временная сложность алгоритма составляет O(n), сложность по памяти пропорциональна размеру диапазона.
3. Если диапазон не известен заранее, его можно определить также за линейное время, выполнив поиск минимума и максимума в массиве.

Пример кода

void counting_sort(int* arr, unsigned int len, int min, int max)
{
 	int* count = new int[max - min + 1];
 
 	for (int i = min; i <= max; ++i)
 		count[i - min] = 0;
 
 	for (int i = 0; i < len; ++i)
 		++count[arr[i] - min];
 
 	for (int i = min; i <= max; ++i)
 		for(int j = count[i - min]; j > 0; j--)
 			*arr++ = i;
 
 	delete[] count;
}

SPFA

Shortest Path Faster Algorithm − это усовершенствованный алгоритм Беллмана-Форда, часто применяющийся на соревнованиях по спортивному программированию. Он вычисляет кратчайшие пути от стартовой вершины до всех остальных во взвешенном ориентированном графе. Считается, что алгоритм хорошо работает на случайных разреженных графах и подходит для графов, содержащих отрицательные веса.

Асимптотика SPFA в худшем случае такая же, как у алгоритма Беллмана-Форда (а именно − O(|V||E|)). Для графов без рёбер отрицательного веса предпочтительнее использовать алгоритм Дейкстры.

Основная идея

Идея SPFA напоминает идею алгоритма Беллмана-Форда. Каждая вершина используется в качестве кандидата для релаксации смежных вершин. Улучшение по сравнению с последним заключается в следующем: вместо слепой проверки всех вершин, SPFA поддерживает очередь вершин-кандидатов и добавляет вершину в очередь только в том случае, если эта вершина была релаксирована. Процесс повторяется до тех пор, пока не останется вершин, которые могли бы быть релаксированы.

Пример кода

SPFA(v):
    for each vertex i
        d[i] = inf
    d[v] = 0
    queue q
    q.push(v)
    while q is not empty
        u = q.front()
        q.pop()
        for each i in adj[u]
            if d[i] > d[u] + w(u,i)
                d[i] = d[u] + w(u,i)
                if i is not in q
                    q.push(i)

Алгоритм Косарайю (Kosaraju)

Этот алгоритм также известен как алгоритм Косарайю-Шарира. Он решает задачу выявления компонента сильной связности в ориентированном графе и делает это за линейное время. Идея алгоритма опирается на тот факт, что транспонированный граф (направление каждого ребра исходного графа изменено на противоположное) имеет точно такие же сильно связанные компоненты, что и исходный.

Алгоритм

1. Отсортировать граф топологически, то есть:
   1. выполнить DFS, сохраняя время выхода для каждой вершины;
   2. отсортировать вершины в порядке убывания по времени выхода − это и получится топологически отсортированный граф.
2. Транспонировать граф.
3. Обойти граф с помощью DFS или BFS, выбирая вершины согласно топологическому порядку.
   1. все достижимые вершины добавляются в список, соответствующий текущей компоненте связности;
   2. как только встретится вершина, из которой не существует пути в еще не посещенную вершину, нужно добавить новую компоненту связности и сохранять последующие вершины там.

Нужно отметить

1. Алгоритм Косарайю выполняет два обхода графа. Его сложность составляет O(|V| + |E|).
2. Этот алгоритм очень прост, но алгоритм Тарьяна для той же задачи на практике работает эффективнее.
3. Если граф представлен как матрица смежности, то время его работы квадратично.

Z-алгоритм

Z-алгоритм решает задачу поиска всех вхождений некоторого шаблона P в строке S и делает это за линейное время.

Z-функция строки

Имея строку S длины n на входе, алгоритм составляет Z-массив, в котором Z[i] является длиной наибольшей подстроки, которая начинается в S[i] и также является префиксом S. Далее мы будем называть такую строку подстрокой-префиксом.

Вот пример Z-массива:

Индекс массива:     0 1 2 3 4 5 6 7 8 9 10 11
Строка S:     a a b c a a b x a a a z
Z-массив:     X 1 0 0 3 1 0 0 2 2 1 0

Z[1]: 1, потому что длина максимальной по размеру подстроки, начинающейся с этого символа и одновременно являющейся префиксом S, равна 1 − «а».

Z[2]: 0, поскольку S[2] != S[1].

…

Z[4]: 3, потому что совпадают S[4:6] и S[0:2]: «aab».

Как построить Z-массив?

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

Идея заключается в следующем: в течение работы алгоритма мы храним интервал [L, R] такой, что 1 ≤ L ≤ i ≤ R, а S[L, R] − это самая правая подстрока-префикс S. На шаге i = 1 мы можем сосчитать L и R, просто сравнив S[0…] и S[1…] (и заодно получив значение Z[1]).

1. Если i > R, то мы можем утверждать, что нет такой префиксной подстроки, которая начиналась бы до i и заканчивалась после i; если бы она существовала, интервал [L, R] был бы другой. Поэтому вычисляем новые L и R путем посимвольного сравнения S[0...] и S[i...]. Z[i] принимаем за R − L + 1.
2. Если же i ≤ R, то мы можем использовать уже вычисленные значения Z. Пусть K = i − L. Мы знаем, что Z[i] ≥ min(Z[K], R − i + 1), потому что S[i...] соответствует S[K...] по крайней мере в R − i + 1 символов (они находятся в [L, R], который, как мы знаем, является префиксной подстрокой).
   1. Если Z [K] < R − i + 1, то не существует более длинной префиксной подстроки, начинающейся с S[i] (иначе Z [K] был бы больше). Отсюда, Z[i] = Z[K] и интервал [L, R] остается таким же.
   2. Если Z[K] ≥ R − i + 1, то возможна ситуация, что S[0…] и S[i…] совпадают в более чем R − i + 1 символах. Так, нам нужно обновить интервал [L, R], положив L = i и проверив совпадения после S[R+1] для получения нового значения R. В процессе вычисляется значение Z[i].

Пример кода

int L = 0, R = 0;
for (int i = 1; i < n; i++) {
  if (i > R) {
    L = R = i;
    while (R < n && s[R-L] == s[R]) R++;
    z[i] = R-L; R--;
  } else {
    int k = i-L;
    if (z[k] < R-i+1) z[i] = z[k];
    else {
      L = i;
      while (R < n && s[R-L] == s[R]) R++;
      z[i] = R-L; R--;
    }
  }
}

И где тут pattern searching?

Внимательный читатель заметит, что в алгоритме выше никак не фигурирует поиск паттернов. Для решения этой задачи сделаем хитрость: составим новую строку Sn = P + $ + S, где P − паттерн; $ − символ-разделитель, который не встречается ни в P, ни в S; S − исходная строка и вычислим Z-массив для Sn.

Нетрудно заметить, что если Z[i] = length(P), то паттерн входит в эту строку начиная с символа i.

k-d (k-dimentional, k-мерное) дерево

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

Пример: построение k-d дерева

Для простоты возьмем двумерную плоскость и предположим, что нам дан следующий набор точек: (2,3), (5,4), (9,6), (8,1), (7,2).

Во время выполнения алгоритма строится бинарное дерево, которое на каждом этапе рекурсии делит пространство на 2 части.

1. Выбираем ось, относительно которой мы будем сортировать точки. Пусть это будет ось Х. Получаем: (2,3), (5,4), (7,2), (8,1), (9,6)
2. Выбираем в качестве корня дерева медиану отсортированного набора − (7,2)
3. На построение левого поддерева отдаем все точки с x ≤ 7 (то есть фактически делим пространство по оси Х), а на построение правого поддерева − х > 7, соответственно.

Повторяем приведенные выше шаги, меняя разделяющую ось. Мы получим вот такое дерево:

А если изобразить алгоритм выше на плоскости, получится вот такая картина:

Поиск ближайшего элемента (nearest neighbour)

Заключительный алгоритм решения задач по спортивному программированию: дано множество точек, мы хотим эффективно находить ближайшую точку этого множества к некоторой данной нам точке (будем называть ее исходной).

1. Строим k-d дерево.
2. Начиная с корневого узла, рекурсивно спускаемся по дереву. Выбираем правое или левое поддерево в зависимости от того, является исходная точка «большей» или «меньшей», чем текущий узел (как мы помним, в узел записывалась медианная по некоторой оси точка).
3. Как только алгоритм достигает листа дерева, этот узел сохраняется как текущее лучшее значение (current best).
4. Алгоритм разворачивается и начинает «подниматься» по дереву, выполняя следующие шаги на каждом узле:
   1. Если текущий узел ближе, чем current best, то он становится current best.
   2. Алгоритм проверяет, могут ли быть какие-либо точки на другой стороне секущей плоскости, которые ближе к исходной точке, чем current best. Поскольку секущие плоскости у нас всегда выровнены по оси, это можно реализовать как сравнение. Мы смотрим значение координаты, по которой проведена секущая плоскость, и сравниваем его с значением этой же координаты у исходной точки, а после сравниваем разность между ними с разностью по этой же координате между исходной точкой и current best.
      1. Если разность меньше, есть основания полагать, что на другой стороне секущей плоскости могут быть точки ближе, чем current best. Тогда алгоритм должен исследовать соответствующую ветвь k-d дерева тоже, двигаясь вниз от текущего узла и повторяя описанный выше рекурсивный процесс.
      2. Иначе, алгоритм продолжает движение вверх по дереву, а ветвь с другой стороны этого узла не принимается во внимание.
5. Когда алгоритм завершит этот процесс для корневого узла, поиск завершен.

Пример кода: построение k-d дерева

function kdtree (point_t *pointList, int depth){
   // Выбираем ось, основываясь на глубине рекурсии 
 int axis := depth mod k;
      
   // Сортируем список точек относительно выбранной оси и выбираем медиану в качестве опорного элемента (pivot)
   pivot = medianFinder(pointList, axis);
      
   // Создаем узел и строим поддерево
   node.location := pivot; // Копируем координаты опорного элемента
   node.leftChild := kdtree(points в pointList до pivot, depth + 1);
   node.rightChild := kdtree(points в pointList после pivot, depth + 1);
   return node;

Важно отметить

1. В среднем временная сложность алгоритма поиска ближайшего соседа с помощью k-d дерева − О(log(n)). Построение дерева выполняется за О(kn log n) в худшем случае (k измерений, n точек). Такая сложность обусловлена тем, что на этапе построения каждого узла алгоритм вынужден сортировать точки для того, чтобы найти медиану (хотя есть и другие подходы к выбору точки в узле).
2. В пространствах высокой размерности вступает в силу так называемое «проклятие размерности». По сравнению с пространствами низкой размерности, алгоритм посещает большее количество ветвей. В частности, когда количество точек лишь немного превосходит число измерений, алгоритм отрабатывает едва ли лучше простого перебора.

Понравилась подборка материалов по спортивному программированию? Возможно, вас заинтересуют следующие статьи:

• Про алгоритмы для новичков
• Объясняем известные алгоритмы сортировки на пальцах
• Алгоритмы и структуры данных: развернутый видеокурс

Источники: Алгоритмы для соревнования по спортивному программированию on Quora; советы по спортивному программированию by Rohan Verma