На этой странице собраны разные материалы, которые помогут тебе в подготовке как к отборочным раундам, так и к финальному этапу.
Для эффективной подготовки мы также рекомендуем ознакомиться с задачами и разборами прошлых лет, а также принятие участие в ознакомительном раунде.
Подготовка
Полезная литература
- «Олимпиадное программирование» (Антти Лааксонен)
- «Competitive Programming 3.» (Halim S., Halim F.)
- «Справочник спортивного программиста. Часть 1» (В.А. Демиденко, М.Д. Кормышов)
- «Программирование – это так просто. Программирование – это так сложно.
- Современный учебник программирования.» (Е.В. Андреева)
Онлайн-курсы
Старт в олимпиадном программировании с VK Education
Программирование для школьников от VK Education. Базовый в Python // Алгоритмы и структуры данных
Алгоритмы: теория и практика
Быстрый старт в спортивное программирование
Быстрый старт в спортивное программирование. Часть 2
Основы C/C++ для спортивного программирования
Быстрый старт в искусственный интеллект
Основы Теории Графов для спортивного программирования
Онлайн-ресурсы с описанием алгоритмов и структур данных
Для успешного участия в олимпиаде, полезно повторить следующие темы
Модульная арифметика. Рекурсивные алгоритмы. Факторизация целых чисел. Разложение числа на множители. НОД, НОК. Алгоритм Евклида. Решето Эратосфена. Сравнение чисел по модулю. Вычисление факториала по модулю.
Генерация перестановок. Расширенный алгоритм Евклида. Тест простоты Ферма (Малая теорема Ферма). Быстрое возведение в степень по модулю.
Сортировка слиянием, быстрая сортировка. Подсчёт количества инверсий. Вещественный бинарный поиск. Целочисленный бинарный поиск. Бинарный поиск по ответу. Тернарный поиск.
Динамическое программирование один параметр. Динамическое программирование два параметра параметр. Наибольшая неубывающая подпоследовательность. Наибольшая общая подпоследовательность. Задача о рюкзаке. Динамическое программирование на подмножествах и подотрезках. Динамическое программирование на поддеревьях.
Стек. Очередь. Дек. Правильные скобочные последовательности. Префиксная нотация.
Хэш функция. Z-функция. Префикс-функция. Бор. Суффиксные массивы. Алгоритм Ахо - Корасика.
Массив частичных сумм. Sqrt-декомпозиция. Разреженная таблица (sparse table). Дерево отрезков. Дерево отрезков с массовыми обновлениями. Двоичное дерево поиска. АВЛ - дерево. Красно-черное дерево. Декартово дерево по явному и не явному ключу. Дерево Фенвика.
Основные понятия: граф, дерево. Представление сетей в компьютере. Поиск в глубину. Поиск в ширину. Диаметр дерева. Радиус дерева. Центр дерева. Система непересекающихся множеств. Задача нахождения минимального остовного дерева. Алгоритм Краскала. Задача нахождения дерева кратчайших расстояний. Алгоритм Дейкстры. Алгоритм Беллмана-Форда. Алгоритм Флойда.