Сегодняшний пост будет посвящён алгоритмам. Я составлю основной список алгоритмов, разделю их по примерному уровню сложности и расскажу, в каком порядке и как их лучше изучать. Также немного поговорю о недостатках чисто алгоритмического подхода к программированию и о том, почему одного знания алгоритмов недостаточно.

Как и в предыдущем посте, я выделю следующие основные, на мой взгляд, темы: конструктивные и ad hoc задачи, строки, графы и деревья, структуры данных, динамическое программирование, комбинаторика и теория чисел, математика, жадные алгоритмы, метод отжига и открытые тесты.

Уровень I — базовые алгоритмы, необходимые для школьных и районных (муниципальных) олимпиад, а также для написания brute-force решений.

Уровень II — основные алгоритмы среднего уровня, необходимые для успешного прохождения и выступления на областных (региональных) олимпиадах. Этот уровень предполагает знание наиболее важных и базовых алгоритмов из каждой темы.

Уровень III — продвинутые алгоритмы, необходимые для того, чтобы занимать призовые места на финалах национальных олимпиад и большинстве сильных перечневых олимпиад.

Уровень IV — специализированные алгоритмы и продвинутые техники для решения особо сложных олимпиадных задач.

СТРОКИ:

• Префиксное дерево (бор) — II
• Полиномиальное хеширование — II
• Префикс-функция — III
• Z-функция — III
• Алгоритм Манакера — III
• Суффиксный массив — IV
• Алгоритм Ахо-Корасик — IV
• Суффиксный автомат — IV

СТРУКТУРЫ ДАННЫХ:

• C++ Standard Library (STL) — I
• Префиксные суммы — I
• Скользящее окно — II
• Битсеты — II
• Сканирующая прямая (Scanline) — II
• Система непересекающихся множеств (DSU) — II
• Дерево отрезков — II
• Дерево Фенвика — II
• Разреженная таблица (Sparse Table) — II
• Корневая декомпозиция и корневые эвристики — II
• Разделяй и властвуй — II
• Meet-in-the-Middle — II
• Дерево отрезков с массовыми операциями и отложенным обновлением (Lazy Propagation) — II
• Алгоритм Мо — III
• Декартовы деревья — IV
• Персистентные деревья — IV
• Двумерное дерево отрезков — IV

ГРАФЫ:

• Поиск в глубину (DFS) — II
• Поиск в ширину (BFS) — II
• Поиск цикла — II
• Топологическая сортировка — II
• Алгоритм Дейкстры — II
• Алгоритм Флойда-Уоршелла — II
• Минимальное остовное дерево — II
• Эйлеров цикл — III
• Компоненты сильной связности — IV
• Алгоритм Куна и паросочетания — IV
• Потоки — IV

ДЕРЕВЬЯ:

• LCA — II
• Метод двоичных подъёмов — II
• Мосты и точки сочленения — II
• Small-to-Large — II
• Центроидная декомпозиция — III
• Heavy-Light Decomposition (HLD) — IV

МАТЕМАТИКА:

• Быстрое возведение в степень — II
• Модульная арифметика — II
• Решето Эратосфена — II
• Факторизация — II
• Принцип включений-исключений — II
• Функция Эйлера — III
• Диофантовы уравнения — IV
• Китайская теорема об остатках — IV

ВАЖНЫЕ ОБЩИЕ АЛГОРИТМЫ:

• Асимптотический анализ — I
• Различные методы сортировки — II
• Бинарный поиск — II
• Тернарный поиск — II
• Метод двух указателей — II
• Сжатие координат — II
• Битовое представление чисел и битовые операции — II
• Жадные алгоритмы — II
• Мемоизация — II
• Подходы динамического программирования — II
• Методы быстрой проверки числа на простоту — III
• Быстрое возведение матрицы в степень — III
• Методы решения игровых задач — III
• Метод отжига — III
• Теория Шпрага — Гранди — IV
• Convex Hull Trick — IV
• Оптимизация Кнута — IV

СОВЕТЫ:

1. Изучайте алгоритмы по мере необходимости и в первую очередь те, которые вы действительно сможете использовать на важных для вас олимпиадах. Нет большого смысла учить сложные алгоритмы, если задачи конкретного соревнования в основном ориентированы, например, на конструктивные подходы. Так же не стоит слишком рано уходить в продвинутые алгоритмы, если вы пока не сможете применить их в реальной задаче. Обычно задача строится не вокруг одного алгоритма, а вокруг нескольких идей, и чем сложнее алгоритм, тем чаще он используется вместе с другими нетривиальными подходами. Поэтому важно не просто знать алгоритм, а быть готовым применить его как часть полноценного решения.

2. При чисто алгоритмическом подходе со временем можно начать искать решение задачи только среди уже известных вам алгоритмов и перестать замечать более простые идеи. В результате решение нередко получается намного сложнее, чем могло бы быть. Поэтому важно изучать не только сами алгоритмы, но и общие подходы к решению задач, учиться рассматривать условие с разных сторон и прежде всего искать простую идею, а уже затем думать о применении более сложных алгоритмов. С другой стороны, знание алгоритмов нередко позволяет быстрее прийти к решению: иногда проще сразу применить знакомый более сложный алгоритм, чем долго искать более простую альтернативу. Поэтому лучше развиваться сразу в двух направлениях: изучать алгоритмы и одновременно учиться находить хорошие идеи для решения задач.

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

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

ЗАКЛЮЧЕНИЕ

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

Этот список не является полным: существует ещё множество алгоритмов, в том числе более сложных и специализированных — например, алгоритмы вычислительной геометрии, свёртки и многие другие. Здесь я постарался отразить прежде всего основные и наиболее востребованные алгоритмы, которые считаю важными для большинства олимпиадных задач.

Также это разделение алгоритмов по уровням условное и отражает мой личный взгляд. Решайте самостоятельно, какие алгоритмы вам действительно стоит изучать, ориентируясь на их практическую необходимость и востребованность именно на тех олимпиадах, в которых вы участвуете. У каждого соревнования своя специфика и характер задач, поэтому универсального порядка изучения алгоритмов не существует.

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