На этой странице собраны разные материалы, которые помогут тебе в подготовке как к отборочным раундам, так и к финальному этапу.

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

Полезная литература:

  • «Олимпиадное программирование» (Антти Лааксонен)
  • «Competitive Programming 3.» (Halim S., Halim F.)
  • «Справочник спортивного программиста. Часть 1» (В.А. Демиденко, М.Д. Кормышов)
  • «Программирование – это так просто. Программирование – это так сложно. Современный учебник программирования.» (Е.В. Андреева)

Онлайн-курсы:

Онлайн-ресурсы с описанием алгоритмов и структур данных:

Для успешного участия в олимпиаде, полезно повторить следующие темы:

Тема 1. Теория чисел.

Модульная арифметика. Рекурсивные алгоритмы. Факторизация целых чисел. Разложение числа на множители. НОД, НОК. Алгоритм Евклида. Решето Эратосфена. Сравнение чисел по модулю. Вычисление факториала по модулю.

Тема 2. Рекурсия.

Генерация перестановок. Расширенный алгоритм Евклида. Тест простоты Ферма (Малая теорема Ферма). Быстрое возведение в степень по модулю.

Тема 3. Сортировки и поиск.

Сортировка слиянием, быстрая сортировка. Подсчёт количества инверсий. Вещественный бинарный поиск. Целочисленный бинарный поиск. Бинарный поиск по ответу. Тернарный поиск.

Тема 4. Динамическое программирование.

Динамическое программирование один параметр. Динамическое программирование два параметра параметр. Наибольшая неубывающая подпоследовательность. Наибольшая общая подпоследовательность. Задача о рюкзаке. Динамическое программирование на подмножествах и подотрезках. Динамическое программирование на поддеревьях

Тема 5. Структуры данных и их применение.

Стек. Очередь. Дек. Правильные скобочные последовательности. Префиксная нотация.

Тема 6. Строки.

Хэш функция. Z-функция. Префикс-функция. Бор. Суффиксные массивы. Алгоритм Ахо - Корасика.

Тема 7. Запросы на подотрезках массива. Бинарная куча. Дерево поиска. Задача RMQ и RSQ.

Массив частичных сумм. Sqrt-декомпозиция. Разреженная таблица (sparse table). Дерево отрезков. Дерево отрезков с массовыми обновлениями. Двоичное дерево поиска. АВЛ - дерево. Красно-черное дерево. Декартово дерево по явному и не явному ключу. Дерево Фенвика.

Тема 8. Теория графов.

Основные понятия: граф, дерево. Представление сетей в компьютере. Поиск в глубину. Поиск в ширину. Диаметр дерева. Радиус дерева. Центр дерева. Система непересекающихся множеств. Задача нахождения минимального остовного дерева. Алгоритм Краскала.  Задача нахождения дерева кратчайших расстояний. Алгоритм Дейкстры. Алгоритм Беллмана-Форда. Алгоритм Флойда.