Олимпиадное программирование

Учебный план для начинающих

1. Арифметика. Решето Эратосфена. Факторизация числа. Количество и сумма делителей.
2. Функция Эйлера. Арифметика по простому модулю. Китайская теорема об остатках.
3. Наибольший общий делитель. Алгоритм Евклида. Расширенный алгоритм Эвклида. Решение линейных диофантовых уравнений.
4. Комбинаторика. Число размещений, сочетаний (с повторениями и без повторений). Бином Ньютона.
5. Формула включений и исключений.
6. Сортировка. Сортировка слиянием. Быстрая сортировка.
7. Бинарные поиск. Порядковые статистики.
8. Структуры данных. Массив, список, очередь, стек.
9. Корневое дерево. Бинарное поисковое дерево. Обходы дерева. Двоичная куча. Биномиальная куча.
10. Динамическое программирование. Просмотр вперед и назад. Рекурсивная реализация с запоминание.
11. Динамическое программирование по подмножествам, по профилю. Динамическое программирование на дереве.
12. Графы. Хранение графов. Обход в ширину. Обход в глубину.
13. Поиск кратчайшего пути. Минимальное остовное дерево.
14. Топологическая сортировка. Компоненты сильной связности.
15. Двусвязные компоненты. Паросочетание в двудольном графе.

Учебный план для продолжающих

1. Корневые деревья. Поисковые деревья. Обходы деревьев. Эйлеров обход дерева. Бинарное поисковое дерево.
2. 2-3 дерево. Splay-дерево. Красно-черное дерево.
3. Декартово дерево. Декартово дерево по неявному ключу. Операция reverse на отрезке.
4. Наименьший общий предок. Двоичный подъем. RMQ. Связь задач LCA и RMQ.
5. Кучи. Двоичная куча. Биномиальная куча. Система непересекающихся множеств.
6. Дерево отрезков. Сжатое дерево отрезков. Дерево отрезков для 2D операций.
7. Дерево Фенвика. Двухмерная версия
8. Строки. Поиск подстрок. KMP. z-функция.
9. Хеширование строк. Хеширование подматриц.
10. Суффиксный массив. Построение суффиксного массива. Использование хешей. LCP.
11. Бор. Множественный поиск подстрок.
12. Графы. Обход графа в глубину. Двухсвязные компоненты. Компоненты сильной связности.
13. Поиск кратчайшего пути. Различные функции расстояний в графе.
14. Системы линейных уравнений. Метод Гаусса. Метод Гаусса в поле вычетов по простому модулю.
15. Персистентные структуры данных. Стек. Куча. Декартово дерево. Дерево отрезков.