Олимпиадная информатика

Программа курса

1. 1 Введение в олимпиадное программирование

   1. Как устроены олимпиады и онлайн-судьи

      Что такое олимпиадное программирование, как читать вердикты онлайн-судьи (OK, WA, TLE, MLE, RE) и как устроены тесты.

   2. Быстрый ввод и вывод в Python

      Почему input() и print() медленны на больших данных и как читать через sys.stdin, выводить одним блоком и обходить рекурсию и лимиты Python.

   3. Асимптотика: O-нотация и оценка «уложусь ли по времени»

      Что такое O-большое, как оценивать число операций по размеру входа и как по ограничениям n заранее выбрать допустимую сложность алгоритма.

2. 2 Базовые приёмы решения задач

   1. Полный перебор и его границы

      Когда полный перебор (brute force) — правильное решение, как перебирать подмножества и перестановки и где проходит граница применимости по n.

   2. Бинарный поиск: по массиву и по ответу

      Классический бинарный поиск в отсортированном массиве, lower_bound/bisect и мощнейший приём «бинпоиск по ответу» для задач на минимизацию и максимизацию.

   3. Два указателя и скользящее окно

      Техника двух указателей и скользящего окна: как за один проход O(n) решать задачи на пары, подотрезки и подстроки вместо квадратного перебора.

   4. Префиксные суммы и разности

      Префиксные суммы для ответа на запрос суммы отрезка за O(1) и массив разностей для быстрых диапазонных прибавлений. Базовый приём предобработки.

   5. Сортировка и жадные алгоритмы

      Жадные алгоритмы: как сортировка по правильному ключу даёт оптимум, на примере выбора заявок, и как доказывать корректность жадности (приём обмена).

3. 3 Структуры данных

   1. Стек, очередь и дек

      Три базовые линейные структуры: стек (LIFO), очередь (FIFO) и дек. Реализация в Python, задача о правильных скобках и приём «ближайший больший элемент».

   2. Словари и множества: хеши на службе скорости

      Хеш-таблицы в Python (dict, set, Counter): доступ за O(1) в среднем, подсчёт частот, проверка наличия, приём «два числа с заданной суммой» за линию.

   3. Система непересекающихся множеств (DSU)

      Структура DSU (Union-Find): объединение множеств и проверка связности почти за O(1) благодаря сжатию путей и объединению по рангу. Применения в графах.

   4. Дерево отрезков: запросы и обновления за O(log n)

      Дерево отрезков (segment tree) для суммы/минимума на отрезке с точечным обновлением. Идея, итеративная реализация на массиве и анализ сложности.

   5. Куча (heapq): приоритетная очередь

      Двоичная куча и модуль heapq: извлечение минимума за O(log n). Применения — k наименьших, слияние списков, основа алгоритма Дейкстры.

4. 4 Графы

   1. Представление графа

      Что такое граф и как его хранить: список смежности и матрица смежности. Когда какое представление выбрать и как читать граф из ввода.

   2. Обходы графа: BFS и DFS

      Два фундаментальных обхода: в ширину (BFS) даёт кратчайшие пути в невзвешенном графе, в глубину (DFS) — рекурсия и стек. Реализации и применения.

   3. Компоненты связности

      Как разбить граф на компоненты связности обходом, посчитать их число и пометить вершины. Применение на сетках (заливка) и в задачах на «острова».

   4. Кратчайшие пути: Дейкстра и 0-1 BFS

      Алгоритм Дейкстры на куче для кратчайших путей во взвешенном графе и приём 0-1 BFS на деке для рёбер с весами 0 и 1. Когда какой применять.

   5. Топологическая сортировка

      Топологический порядок вершин ориентированного ациклического графа (DAG): алгоритм Кана на входящих степенях. Применение к зависимостям и обнаружению циклов.

   6. Минимальный остов: алгоритм Краскала на DSU

      Минимальное остовное дерево (MST): зачем нужно и как его строит алгоритм Краскала — сортировка рёбер плюс DSU. Корректность и сложность.

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

   1. Идея динамического программирования и одномерные ДП

      Что такое динамическое программирование: подзадачи, переход и мемоизация. Одномерные ДП на примерах чисел Фибоначчи, лесенки и способов размена.

   2. Рюкзак (knapsack)

      Задача о рюкзаке 0/1: динамика по вместимости. Наивная двумерная таблица и оптимизация до одномерного массива с обратным проходом. Анализ сложности.

   3. ДП на подпоследовательностях: LIS и LCS

      Наибольшая возрастающая подпоследовательность (LIS) за O(n log n) и наибольшая общая подпоследовательность (LCS) двух строк. Два классических ДП.

   4. ДП на подотрезках (интервальное ДП)

      Интервальное ДП: состояние — отрезок [i, j], переход — выбор точки разбиения. Классика на примере оптимального умножения цепочки матриц.

   5. Восстановление ответа в ДП

      Как по таблице ДП вывести не только значение оптимума, но и сам ответ: хранение выбора (parent/choice) и обратный проход. Примеры на размене и рюкзаке.

6. 6 Математика и строки

   1. НОД, НОК и быстрое возведение в степень

      Алгоритм Евклида для НОД и формула НОК через НОД. Бинарное возведение в степень за O(log n) — основа модулярной арифметики и многих формул.

   2. Решето Эратосфена и факторизация

      Решето Эратосфена находит все простые до N за O(N log log N). Разложение числа на простые множители за O(sqrt(N)). Базовые приёмы теории чисел.

   3. Модулярная арифметика

      Зачем ответы берут по модулю 10^9+7, как корректно складывать/умножать/вычитать по модулю и как делить через обратный элемент по малой теореме Ферма.

   4. Комбинаторика для олимпиад

      Перестановки, размещения и сочетания; биномиальные коэффициенты C(n,k). Предподсчёт факториалов и обратных для вычисления C(n,k) по модулю за O(1).

   5. Строки: хеши и алгоритм КМП

      Полиномиальный хеш строки для сравнения подстрок за O(1) и префикс-функция (алгоритм Кнута-Морриса-Пратта) для поиска образца за O(n+m).

7. 7 Стратегия и практика

   1. Как читать условие и выбирать алгоритм

      Алгоритм работы над задачей: разбор условия, чтение ограничений, оценка нужной сложности и выбор подходящего приёма. Чек-лист и типичные паттерны.

   2. Отладка и стресс-тестирование

      Как ловить баги без скрытых тестов: стресс-тестирование сравнивает быстрое решение с медленным эталоном на случайных данных и находит контрпример.

   3. Разбор задач от идеи до кода и куда двигаться дальше

      Три полных разбора олимпиадных задач: от чтения условия через выбор приёма к рабочему коду. Сводная карта приёмов курса и план дальнейшего роста.