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

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

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

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

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

• Алгоритмы: теория и практика
• Быстрый старт в спортивное программирование
• Быстрый старт в спортивное программирование. Часть 2
• Основы C/C++ для спортивного программирования
• Быстрый старт в искусственный интеллект
• Основы Теории Графов для спортивного программирования

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

• MAXimal
• Викиконспекты ИТМО
• Информатикс
• Алгоритмика

Архивы задач с возможностью онлайн-проверки решений:

• Timus Online Judge

Сайты, на которых проводятся онлайн-соревнования:

• All Cups
• Codeforces
• AtCoder

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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