Роман Удовиченко

Роман Удовиченко

Преподаватель олимпиадного программирования

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

Учащиеся направления олимпиадного программирования будут поделены на 2 группы, в соответствии с уровнем знаний.

Предлагаем ознакомиться с учебным планом для обеих групп.

Начинающие
  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. Персистентные структуры данных. Стек. Куча. Декартово дерево. Дерево отрезков.
О преподавателе

Разработчик в группе разработки геосервисов компании «Яндекс».
Серебряный призер международной олимпиады школьников по информатике. Серебряный призер студенческого командного чемпионата мира. Многократный финалист различных международных соревнований по программированию. Профиль на codeforces.

 
Inscription_FR-10_1
yandex_logo-240

Кибернетические партнеры

amperka-2
trik-2

Информационные партнеры

RAOR
volnoe_delo