Ниже мы собрали несколько интересных алгоритмов для решения задач по спортивному программированию, которые можно применить на соревнованиях.
Сортировка подсчетом
Сортировка подсчетом − наиболее частый способ решения задач по спортивному программированию. Этот алгоритм сортировки работает для данных, ключи которых находятся в некотором известном числовом диапазоне. Его идея заключается в том, чтобы подсчитать количество элементов, соответствующих каждому ключу, и записать это количество в ячейку массива (индекс ячейки − это ключ, значение − подсчитанная частота ключа), а после − вывести элементы нужное количество раз по порядку.
Пример: сортировка массива чисел
Дан массив чисел и известен числовой диапазон, в котором они располагаются. Например, массив: 1, 4, 1, 2, 7, 5, 2. Нам известно, что эти числа принадлежат промежутку от 0 до 9.
- Заведем массив, в котором будем подсчитывать, сколько раз встречается то или иное число.
Индекс (ключ): 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
Важно отметить
- Сортировка подсчетом достаточно эффективна, если диапазон чисел массива не сильно превосходит количество самих чисел. Поразмышляйте над такой ситуацией: [10000, 5000, 5, 10] и диапазон [5; 10000] соответственно.
- Временная сложность алгоритма составляет O(n), сложность по памяти пропорциональна размеру диапазона.
- Если диапазон не известен заранее, его можно определить также за линейное время, выполнив поиск минимума и максимума в массиве.
Пример кода
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)
Этот алгоритм также известен как алгоритм Косарайю-Шарира. Он решает задачу выявления компонента сильной связности в ориентированном графе и делает это за линейное время. Идея алгоритма опирается на тот факт, что транспонированный граф (направление каждого ребра исходного графа изменено на противоположное) имеет точно такие же сильно связанные компоненты, что и исходный.
Алгоритм
- Отсортировать граф топологически, то есть:
- выполнить DFS, сохраняя время выхода для каждой вершины;
- отсортировать вершины в порядке убывания по времени выхода − это и получится топологически отсортированный граф.
- Транспонировать граф.
- Обойти граф с помощью DFS или BFS, выбирая вершины согласно топологическому порядку.
- все достижимые вершины добавляются в список, соответствующий текущей компоненте связности;
- как только встретится вершина, из которой не существует пути в еще не посещенную вершину, нужно добавить новую компоненту связности и сохранять последующие вершины там.
Нужно отметить
- Алгоритм Косарайю выполняет два обхода графа. Его сложность составляет O(|V| + |E|).
- Этот алгоритм очень прост, но алгоритм Тарьяна для той же задачи на практике работает эффективнее.
- Если граф представлен как матрица смежности, то время его работы квадратично.
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]).
- Если i > R, то мы можем утверждать, что нет такой префиксной подстроки, которая начиналась бы до i и заканчивалась после i; если бы она существовала, интервал [L, R] был бы другой. Поэтому вычисляем новые L и R путем посимвольного сравнения S[0...] и S[i...]. Z[i] принимаем за R − L + 1.
- Если же i ≤ R, то мы можем использовать уже вычисленные значения Z. Пусть K = i − L. Мы знаем, что Z[i] ≥ min(Z[K], R − i + 1), потому что S[i...] соответствует S[K...] по крайней мере в R − i + 1 символов (они находятся в [L, R], который, как мы знаем, является префиксной подстрокой).
- Если Z [K] < R − i + 1, то не существует более длинной префиксной подстроки, начинающейся с S[i] (иначе Z [K] был бы больше). Отсюда, Z[i] = Z[K] и интервал [L, R] остается таким же.
- Если 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 части.
- Выбираем ось, относительно которой мы будем сортировать точки. Пусть это будет ось Х. Получаем: (2,3), (5,4), (7,2), (8,1), (9,6)
- Выбираем в качестве корня дерева медиану отсортированного набора − (7,2)
- На построение левого поддерева отдаем все точки с x ≤ 7 (то есть фактически делим пространство по оси Х), а на построение правого поддерева − х > 7, соответственно.
Повторяем приведенные выше шаги, меняя разделяющую ось. Мы получим вот такое дерево:
А если изобразить алгоритм выше на плоскости, получится вот такая картина:
Поиск ближайшего элемента (nearest neighbour)
Заключительный алгоритм решения задач по спортивному программированию: дано множество точек, мы хотим эффективно находить ближайшую точку этого множества к некоторой данной нам точке (будем называть ее исходной).
- Строим k-d дерево.
- Начиная с корневого узла, рекурсивно спускаемся по дереву. Выбираем правое или левое поддерево в зависимости от того, является исходная точка «большей» или «меньшей», чем текущий узел (как мы помним, в узел записывалась медианная по некоторой оси точка).
- Как только алгоритм достигает листа дерева, этот узел сохраняется как текущее лучшее значение (current best).
- Алгоритм разворачивается и начинает «подниматься» по дереву, выполняя следующие шаги на каждом узле:
- Если текущий узел ближе, чем current best, то он становится current best.
- Алгоритм проверяет, могут ли быть какие-либо точки на другой стороне секущей плоскости, которые ближе к исходной точке, чем current best. Поскольку секущие плоскости у нас всегда выровнены по оси, это можно реализовать как сравнение. Мы смотрим значение координаты, по которой проведена секущая плоскость, и сравниваем его с значением этой же координаты у исходной точки, а после сравниваем разность между ними с разностью по этой же координате между исходной точкой и current best.
- Если разность меньше, есть основания полагать, что на другой стороне секущей плоскости могут быть точки ближе, чем current best. Тогда алгоритм должен исследовать соответствующую ветвь k-d дерева тоже, двигаясь вниз от текущего узла и повторяя описанный выше рекурсивный процесс.
- Иначе, алгоритм продолжает движение вверх по дереву, а ветвь с другой стороны этого узла не принимается во внимание.
- Когда алгоритм завершит этот процесс для корневого узла, поиск завершен.
Пример кода: построение 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;
Важно отметить
- В среднем временная сложность алгоритма поиска ближайшего соседа с помощью k-d дерева − О(log(n)). Построение дерева выполняется за О(kn log n) в худшем случае (k измерений, n точек). Такая сложность обусловлена тем, что на этапе построения каждого узла алгоритм вынужден сортировать точки для того, чтобы найти медиану (хотя есть и другие подходы к выбору точки в узле).
- В пространствах высокой размерности вступает в силу так называемое «проклятие размерности». По сравнению с пространствами низкой размерности, алгоритм посещает большее количество ветвей. В частности, когда количество точек лишь немного превосходит число измерений, алгоритм отрабатывает едва ли лучше простого перебора.
Понравилась подборка материалов по спортивному программированию? Возможно, вас заинтересуют следующие статьи:
- Про алгоритмы для новичков
- Объясняем известные алгоритмы сортировки на пальцах
- Алгоритмы и структуры данных: развернутый видеокурс
Источники: Алгоритмы для соревнования по спортивному программированию on Quora; советы по спортивному программированию by Rohan Verma
Комментарии