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

Пример кода

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

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

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

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

Пример кода

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

Алгоритм

  1. Отсортировать граф топологически, то есть:
    1. выполнить DFS, сохраняя время выхода для каждой вершины;
    2. отсортировать вершины в порядке убывания по времени выхода − это и получится топологически отсортированный граф.
    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. Иначе, алгоритм продолжает движение вверх по дереву, а ветвь с другой стороны этого узла не принимается во внимание.

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

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

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

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