5 контестов, лекций и разборов подходит для всех дивизионов от А до D
письменные и онлайн разборы доступны консультации тренеров
для команд из 1, 2 и 3 человек оплата картами физлиц или по счету от организаций


ПРОГРАММНЫЙ КОМИТЕТ



Олег *snarknews* Христенко

Главный судья
Главный редактор Snarknews.info
Модератор контестов
Координатор Открытого кубка по программированию



Михаил *Endagorion* Тихомиров

Методист сборов Discover the World 2020,
Тренер команд МФТИ - золотых медалистов ICPC,
Член Scientific Committee
Международной олимпиады школьников
по информатике IOI.


Андрей *andrewzta* Станкевич

Тренер 7 чемпионов мира ICPC
Премия старшего тренера в Пхукет, Таиланд, 2016
Профессор в ИТМО


Филипп *DPR-pavlin* Рухович

Методист сборов Discover the World 2020,
Главный тренер Открытых московских тренировок МФТИ,
Сотренер команды-медалистов ICPC МФТИ,
Финалист ICPC 2014,
Победитель KPI-Open 2013.




ОРГАНИЗАЦИОННЫЙ КОМИТЕТ



Алексей Малеев

Директор по дистанционным программам МФТИ,
Основатель Moscow Workshops


Сергей Даревский

Генеральный директор Русской
школы программирования,
Руководитель технического отдела


Ольга Солодянникова

Руководитель выездных сборов Moscow Workshops
и Русской школы программирования,
Директор одноименной АНО ДО


Мария Мильшина

Руководитель PR-службы Moscow Workshops,
Замдиректора ЦРИТО МФТИ


РАСПИСАНИЕ

(временное, будет обновляться под участников)

ПРОГРАММА ЛЕКЦИЙ


Программа является приблизительной.
Актуальная программа формируется по результатам заполнения тематических анкет зарегистрированными участниками. В дивизионе A/B лекции и разборы будут читаться на английском языке, в дивизионах C и D — на русском.

Дивизион A/B:



  • Потоки - 1: теорема Форда-Фалкерсона, алгоритм Эдмондса-Карпа
  • Потоки - 2: алгоритм Диница, поиск максимального потока минимальной стоимости
  • Суффиксное дерево: алгоритм Укконена
  • Дерево палиндромов: построение за O(n)
  • Суффиксный автомат: построение за O(n)
  • Быстрое преобразование Фурье - 1: быстрое перемножение многочленов и длинных чисел, быстрое извлечение квадратного корня
  • Быстрое преобразование Фурье - 2: быстрое деление многочленов и длинных чисел, быстрое извлечение квадратного корня
  • Быстрое преобразование Фурье - 3: многомерное БПФ и его связь с быстрой сверткой на подмножествах (Fast Subset Convolution).
  • Комбинаторная теория игр - 1: ретроанализ, теория Шпрага-Гранди
  • Комбинаторная теория игр - 2: теория Смита
  • Динамическое программирование: использование матриц
  • Динамическое программирование на подмасках, по профилю
  • Продвинутые оптимизации в динамическом программировании: Convex Hull Trick, оптимизация Кнута, оптимизация "разделяй-и-властвуй"
  • Диаграмма Вороного. Алгоритм Форчуна.
  • Сливаемые кучи


Дивизионы С и D:



  • Остовные деревья: алгоритмы Прима, Краскала. Использование системы непересекающихся множеств
  • Кратчайшие пути во взвешенных графах. Алгоритмы Дейкстры, Флойда, Форда-Беллмана
  • Поиск мостов, точек сочленения, компонент реберной и вершинной двусвязности в неориентированном графе
  • Паросочетания в двудольном графе: алгоритм Куна. Поиск минимального покрытия и максимального независимого множества в двудольном графе
  • Поиск компонент сильной связности: алгоритмы Косарайю, Тарьяна. Задача 2-SAT.
  • Задачи RSQ и RMQ. Задача static RSQ и частичные суммы. Задача static RMQ и разреженная таблица (sparse table). Дерево отрезков. Технология отложенных операций и множественные операции в дереве отрезков
  • Метод сканирующей прямой
  • Sqrt-decomposition. Алгоритм Мо
  • Бор. Алгоритм Ахо-Корасик
  • Суффиксный массив, его построение за O(n log n). Алгоритм Касаи. Применения суффиксного массива.
  • Задача о наименьшем общем предке: методы двоичных подъемов и сведение к RMQ. Технология сливаемых сетов
  • Декартовы деревья по явному ключу и по неявному ключу. Множественные операции, операции разворота на подотрезке
  • Выпуклая оболочка. Алгоритмы Джарвиса, Грэхема, Эндрю.
  • Основы использования STL: поиск НВП за O(n log n), алгоритмы Дейкстры и Прима с кучей или сетом
  • Базовые строки (Префикс-функция, Z-функция, алгоритм Манакера, хэши)
  • Динамическое программирование: восстановление объекта по номеру и номера по объектам (перестановки, сочетания, ПСП и т.п.);
  • Деревья: диаметр дерева, динамическое программирование на поддеревьях

КАК ОПРЕДЕЛИТЬ СВОЙ ДИВИЗИОН — СВОЙ ТЕКУЩИЙ УРОВЕНЬ ЗНАНИЙ