Роман Удовиченко
Преподаватель олимпиадного программирования
от А до ЯОлимпиадное программирование
Учащиеся направления олимпиадного программирования будут поделены на 2 группы, в соответствии с уровнем знаний.
Предлагаем ознакомиться с учебным планом для обеих групп.
Начинающие
- Арифметика. Решето Эратосфена. Факторизация числа. Количество и сумма делителей.
- Функция Эйлера. Арифметика по простому модулю. Китайская теорема об остатках.
- Наибольший общий делитель. Алгоритм Евклида. Расширенный алгоритм Эвклида. Решение линейных диофантовых уравнений.
- Комбинаторика. Число размещений, сочетаний (с повторениями и без повторений). Бином Ньютона.
- Формула включений и исключений.
- Сортировка. Сортировка слиянием. Быстрая сортировка.
- Бинарные поиск. Порядковые статистики.
- Структуры данных. Массив, список, очередь, стек.
- Корневое дерево. Бинарное поисковое дерево. Обходы дерева. Двоичная куча. Биномиальная куча.
- Динамическое программирование. Просмотр вперед и назад. Рекурсивная реализация с запоминание.
- Динамическое программирование по подмножествам, по профилю. Динамическое программирование на дереве.
- Графы. Хранение графов. Обход в ширину. Обход в глубину.
- Поиск кратчайшего пути. Минимальное остовное дерево.
- Топологическая сортировка. Компоненты сильной связности.
- Двусвязные компоненты. Паросочетание в двудольном графе.
Продолжающие
- Корневые деревья. Поисковые деревья. Обходы деревьев. Эйлеров обход дерева. Бинарное поисковое дерево.
- 2-3 дерево. Splay-дерево. Красно-черное дерево.
- Декартово дерево. Декартово дерево по неявному ключу. Операция reverse на отрезке.
- Наименьший общий предок. Двоичный подъем. RMQ. Связь задач LCA и RMQ.
- Кучи. Двоичная куча. Биномиальная куча. Система непересекающихся множеств.
- Дерево отрезков. Сжатое дерево отрезков. Дерево отрезков для 2D операций.
- Дерево Фенвика. Двухмерная версия
- Строки. Поиск подстрок. KMP. z-функция.
- Хеширование строк. Хеширование подматриц.
- Суффиксный массив. Построение суффиксного массива. Использование хешей. LCP.
- Бор. Множественный поиск подстрок.
- Графы. Обход графа в глубину. Двухсвязные компоненты. Компоненты сильной связности.
- Поиск кратчайшего пути. Различные функции расстояний в графе.
- Системы линейных уравнений. Метод Гаусса. Метод Гаусса в поле вычетов по простому модулю.
- Персистентные структуры данных. Стек. Куча. Декартово дерево. Дерево отрезков.
О преподавателе
Разработчик в группе разработки геосервисов компании «Яндекс».
Серебряный призер международной олимпиады школьников по информатике. Серебряный призер студенческого командного чемпионата мира. Многократный финалист различных международных соревнований по программированию. Профиль на codeforces.
