Антти Лааксонен - Олимпиадное программирование

например,
максимальные потоки, игра ним и суффиксные массивы.

20  Глава 1. Введение

Многие темы олимпиадного программирования обсуждаются в стандартных учебниках по алгоритмам, но есть и отличия. Например, во многих
книгах реализация алгоритмов сортировки и основных структур данных
рассматривается с нуля, но такие знания на олимпиаде несущественны,
потому что можно пользоваться средствами из стандартной библиотеки.
С другой стороны, некоторые темы хорошо известны в олимпиадном сообществе, но редко встречаются в учебниках. Примером может служить
дерево отрезков – структура данных, которая используется для решения
многих задач без привлечения более хитроумных алгоритмов.
Одна из целей этой книги – документировать приемы олимпиадного
программирования, которые обычно обсуждаются только на форумах
и в блогах. Там, где возможно, даются ссылки на научную литературу
по таким методам. Но сделать это можно не всегда, потому что многие
методы ныне стали частью фольклора, и никто не знает имени первооткрывателя.
Книга организована следующим образом.
• В главе 2 рассматриваются средства языка программирования C++,
а затем обсуждаются рекурсивные алгоритмы и поразрядные операции.
• Глава 3 посвящена эффективности: как создавать алгоритмы, способные быстро обрабатывать большие наборы данных.
• В главе 4 обсуждаются алгоритмы сортировки и двоичного поиска с
упором на их применение в проектировании алгоритмов.
• В главе 5 дается обзор избранных структур данных в стандартной
библиотеке C++: векторов, множеств и отображений.
• Глава 6 представляет собой введение в один из методов проектирования алгоритмов – динамическое программирование. Здесь же
приводятся примеры задач, которые можно решить этим методом.
• В главе 7 рассматриваются элементарные алгоритмы на графах, в
т. ч. поиск кратчайших путей и минимальные остовные деревья.
• В главе 8 речь пойдет о более сложных вопросах проектирования алгоритмов, в частности об алгоритмах с параллельным просмотром
разрядов и амортизационном анализе.
• Тема главы 9 – эффективная обработка запросов по диапазонам
массива, таких как вычисление сумм элементов и нахождение минимальных элементов.
• В главе 10 представлены специальные алгоритмы для деревьев, в
т. ч. методы обработки запросов к дереву.
• В главе 11 обсуждаются разделы математики, часто встречающиеся
в олимпиадном программировании.

1.3. Сборник задач CSES  21
• В главе 12 описываются дополнительные алгоритмы на графах, например поиск компонент сильной связности и вычисление максимального потока.
• Глава 13 посвящена геометрическим алгоритмам, в ней описаны
методы, позволяющие удобно решать геометрические задачи.
• В главе 14 рассматриваются методы работы со строками, в т. ч. хеширование, Z-алгоритм и суффиксные массивы.
• В главе 15 обсуждаются избранные дополнительные темы, например алгоритмы, основанные на идее квадратного корня, и оптимизация динамического программирования.

1.3. Сборник задач CSES
В сборнике задач CSES представлены задачи для практики в олимпиадном
программировании. Расположены они в порядке возрастания трудности,
а в этой книге обсуждаются все методы, необходимые для их решения.
Сборник задач доступен по адресу:
https://cses.fi/problemset/.
Посмотрим, как решить первую задачу из него. Она называется «Странный алгоритм» и формулируется следующим образом.
Рассмотрим алгоритм, принимающий на входе целое положительное
число n. Если n четно, то алгоритм делит его на два, а если нечетно, то умножает на три и прибавляет 1. Например, для n = 3 получается следующая
последовательность:
3 → 10 → 5 → 16 → 8 → 4 → 2 → 1.
Ваша задача заключается в том, чтобы промоделировать выполнение
этого алгоритма для любого заданного n.
Вход
Единственная строка, содержащая целое число n.
Выход
Печатает строку, содержащую все значения, вычисляемые алгоритмом.
Ограничения
• 1 ≤ n ≤ 106
Пример
Вход:
3
Выход:
3 10 5 16 8 4 2 1

22  Глава 1. Введение

Эта проблема имеет отношение к знаменитой гипотезе Коллатца, которая утверждает, что описанный выше алгоритм завершается для любого
n. До сих пор она остается недоказанной. Но в этой задаче мы знаем, что
начальное значение n не превышает миллиона, что существенно упрощает проблему.
Это простая задача моделирования, не требующая глубоких размышлений. --">