Подготовка к олимпиадам по программированию для продвинутого уровня, 9-11 кл

Язык C++
Краткий экскурс по языку C++, который является основным языком, используемым на финале ВСОШ по программированию. В разделе обсуждаются важные для олимпиады аспекты языка, контейнеры STL, библиотека algorithm.

• Типы данных
• Битовые операции
• Ввод-вывод данных. Работа с файлами
• Структуры, классы
• Строки
• Контейнеры STL
• Встроенные сортировки

Арифметические алгоритмы
Раздел рассматривает алгоритмы, которые изучаются в математике: проверка числа на простоту, решето

• Эратосфена и другие.
• Проверка на простоту
• Факторизация
• Алгоритм Евклида
• Решето Эратосфена
• Быстрое возведение в степень

Алгоритмы поиска
В разделе изучается бинарный поиск, его разновидности и как его увидеть в задании, а также класс задач по теме "линейный поиск".

• Бинарный поиск
• Тернарный поиск
• Метод двух указателей
• Метод сканирующей прямой

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

• Динамическое программирование
• Восстановление ответа
• Задачи НОП, НВП, НОВП
• Динамическое программирование по подстрокам, поддеревьям, подмножествам, профилю
• Метод Convex Hull Trick

Структуры данных
Раздел направлен на изучение структуры данных, которая отвечает за представление данных и их удобное восприятие.

• Префиксные суммы
• Sqrt-декомпозиция
• Sparse table
• Дерево отрезков
• Массовые операции в дереве отрезков
• Декартово дерево
• Декартово дерево по неявному ключу
• Дерево merge-sort
• Метод сканирующей прямой и дерева отрезков
• Дерево Фенвика
• Система непересекающихся множеств

Алгоритмы на графах
Раздел изучает графы: от обычных обходов графа до сложных алгоритмов, встречающихся в финале ВСОШ по информатике.

• Хранение графов
• DFS, топологическая сортировка, конденсация, поиск мостов и точек сочленения
• BFS
• Алгоритм Дейкстры
• Алгоритм Форда-Беллмана
• Алгоритм Флойда
• Поиск минимального остовного дерева
• Задача LCA
• Поиск паросочетаний

Вычислительная геометрия
Геометрия в информатике совершенно не похожа на стандартную планиметрию. Раздел предполагает работу на координатной плоскости с простейшими объектами (точками, прямыми), а также с окружностями и многоугольниками.

• Структура точки
• Скалярное и векторное произведение
• Площадь многоугольника, задача про точку внутри многоугольника
• Прямые, окружности

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

• Хэширование

Комбинаторные алгоритмы
В разделе рассказывается о комбинаторике, а также о различных типах комбинаторных объектов в информатике, их построении и работе с ними.

• Генерация всех комбинаторных объектов
• Получение объекта по номеру и номера по объекту
• Получение следующего объекта