Олимпиадное программирование для школьников от Яндекса

Описание параллелей

Для кого Уверенное знание C++ Хорошие знания структур данных: дерево отрезков, декартово дерево, дерево фенвика Динамическое программирование: НВП, НОП, динамика на дереве, динамика по подмножествам, простые оптимизации Структуры данных на деревьях: HLD, центроиды, переливание меньшего к большему Графы: DFS, BFS, алгоритм Дейкстры, алгоритмы Прима и Крускала, поиск мостов и точек сочленения, поиск компонент сильной связности, алгоритм Куна Строки: префикс функция, N-функция, бор Теория чисел: деление по модулю, алгоритм Евклида, решето Эратосфена Геометрия: представление вектора, основные векторные операции, поиск пересечения прямых, выпуклая оболочка		Примеры тем Нетривиальные алгоритмы и задачи теории чисел Декомпозиции деревьев: centroid, heavy-light, ladder Задачи на графах: 2-SAT, паросочетания, остовы и их применение в задачах Продвинутые структуры данных: неявные деревья отрезков, двумерные структуры, персистентные структуры, разные — структуры и алгоритмы дня нахождения минимумов Строковые структуры данных: Ахо-Корасик, суффиксный массив, суффиксный автомат Алгоритмы поиска потоков в сетях Продвинутые геометрические алгоритмы: вращающийся scanline, пересечение полуплоскостей, диаграмма Вороного, триангуляция Делоне Splay-деревья, link-cut Алгоритмы поиска минимальных глобальных разрезов Нетривиальные алгоритмы на графах: венгерский алгоритм, алгоритм двух китайцев, дерево доминаторов Матроиды Алгоритмы во внешней памяти
Формат занятий В начале каждого занятия проводится разбор предыдущих туров: тематического и дистанционного. Далее идет лекция или семинар (а иногда и то, и другое). На семинарах учащиеся сдают задачи с листочка преподавателям. Параллельно, с некоторой задержкой, достаточной, чтобы успеть подумать над соответствующими задачами, проводится их разбор.
Преподаватели Филипп Грибов, Александр Некрасов, Алексей Михненко и Антон Степанов

Входные требования Уверенное знание C++, алгоритмы и структуры данных STL Знание структур данных: дерево отрезков, система непересекающихся множеств, разреженные таблицы Динамическое программирование: задачи рюкзака, НВП, НОП. Динамика по подотрезкам, поддеревьям и подмножествам Базовые алгоритмы поиска кратчайших путей на графах Базовые геометрические примитивы: вектора, точки, прямые и окружности. Базовые операции с примитивами Базовые строковые алгоритмы (хэширование, префикс и z функции)		Примеры тем Структуры данных: от дерева отрезков до splay-дерева Оптимизации динамического программирования: convex hull trick, meet-in-the-middle, divide and conquer Декомпозиции деревьев: centroid, heavy-light, ladder Задачи на графах: паросочетания, потоки, dinamic connectivity problem Геометрия: выпуклые оболочки, сумма Минковского Строки: хэши, Ахо-Корасик, суффиксный массив Полезные трюки: STL, битовые оптимизации, стресс-тестирование
Преподаватели Иван Сафонов, Тихон Евтеев, Владимир Новиков и Алексей Васильев

Входные требования Сортировки Базовые знания C++, алгоритмы и структуры данных STL Линейные алгоритмы (например, поиск ближайшего меньшего при помощи стека или минимум в окне) Способы хранения графов и базовые применения DFS (например, нахождение компонент связности, поиск цикла в графе, проверка графа на двудольность) Базовое понимание и умение решать простые задачи на динамическое программирование		Преподаватели Михаил Первеев Денис Видяев Герман Перов
Примеры тем
Графы: BFS, DFS, их применения. Алгоритмы поиска кратчайших путей во взвешенных графах (Форда-Беллмана, Дейкстры, Флойда). Минимальные остовные деревья. Паросочетания, алгоритм Куна. Деревья: алгоритм поиска наименьшего общего предка в дереве. Эйлеров обход. Декомпозиции дерева (heavy-light, centroid). Строки: префикс-, N- функции, бор, автомат Ахо-Корасик, хеширование. Суффиксный массив. Динамическое программирование: одномерное, многомерное, по подмаскам, подграфам, подотрезкам, подмножествам, профилю и изломанному профилю.		Структуры данных: дерево отрезков с массовыми операциями, декартово дерево, sparse table, система непересекающихся множеств. Дерево Фенвика. Геометрия: базовые примитивы, алгоритмы построения выпуклой оболочки, быстрые алгоритмы в вычислительной геометрии (например, построение касательной к выпуклому многоугольнику). И много других тем: теория Шпрага-Гранди, корневая оптимизация, метод разделяй-и-властвуй, решето Эратосфена, задача дискретного логарифмирования, meet-in-the-middle.

Для кого Знание языка программирования (с++) Умение использовать встроенные алгоритмы (сортировки, поиски) Умение решить задачу Кузнечик на динамическое программирование		Примеры тем Важные структуры данных: дерево отрезков, разреженные таблицы, СНМ Динамическое программирования: до динамики по подстрокам, подмножествам и цифрам Алгоритмы на графах: до поиска мостов, точек сочленения, построения минимального остова Простейшие алгоритмы на деревьях: LCA, LA, Эйлеров обход Базовые алгоритмы на строках: префикс-функция, зет-функция, хэши и бор Геометрия: от векторов и прямых до многоугольников и выпуклой оболочки
Преподаватели Мария Жогова, Даниил Шиндов, Михаил Кондрашин и Сергей Панкевич

Для кого Знание синтаксиса какого-либо языка программирования Готовность быстро изучать c++, если вы еще им не владеете Знание математики на уровне 6-7 класса (степень, извлечение корня, понятие функции, желательно базовая планиметрия, понятие о тригонометрических функциях) Опыт в математических олимпиадах будет плюсом		Примеры тем Сортировки: квадратичные, MergeSort, QuickSort Бинарный поиск: обычный и по ответу Теория чисел: алгоритм Евклида, разбиение числа на простые Простейшие структуры данных: vector, set, map, стек, очередь, деко Базовое динамическое программирование: с нуля до задач о рюкзаке, НВП, НОП, подсчет комбинаторных объектов Базовые алгоритмы на графы: хранение, поиск в глубину, ширину, алгоритмы Дейкстры, Флойда, Форда-Беллмана, конденсация графа Простая геометрия: векторы, прямые, окружности
Преподаватели Полина Романченко, Алексей Кулдошин и Алиса Нестеренко