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

0
11651
Добавить в избранное

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

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

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

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

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

Пример кода

SPFA

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

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

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

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

Пример кода

Алгоритм Косарайю (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].

Пример кода

И где тут 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 дерева

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

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

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

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

Интересуетесь алгоритмами?

Подпишитесь на нашу рассылку, чтобы получать больше интересных материалов:

И не беспокойтесь, мы тоже не любим спам. Отписаться можно в любое время.




Оставьте комментарий