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. Если диапазон не известен заранее, его можно определить также за линейное время, выполнив поиск минимума и максимума в массиве.

Пример кода

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

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

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

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

Пример кода

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

Алгоритм

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

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

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

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].

Пример кода

И где тут pattern searching?

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

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

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 дерева

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

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

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

Источник: proglib.io

Комментарии: