Параллель A
Для кого? Параллель рассчитана на опытных олимпиадников: участников и дипломантов Всероссийской олимпиады по информатике. Необходимо отлично разбираться в алгоритмах и структурах данных уровня параллелей B-A' ЛКШ.
Формат занятий. В начале каждого занятия проводится разбор предыдущих туров: тематического и дистанционного. Далее идет лекция или семинар (а иногда и то, и другое). На семинарах учащиеся сдают задачи с листочка преподавателям. Параллельно, с некоторой задержкой, достаточной, чтобы успеть подумать над соответствующими задачами, проводится их разбор.
Преподаватели: Филипп Грибов, Егор Горбачев и Даниил Николенко
Примеры тем:
- Нетривиальные алгоритмы и задачи теории чисел.
- Декомпозиции деревьев: centroid, heavy-light, ladder.
- Задачи на графах: 2-SAT, паросочетания, остовы и их применение в задачах.
- Продвинутые структуры данных: неявные деревья отрезков, двумерные структуры, персистентные структуры, разные — структуры и алгоритмы дня нахождения минимумов.
- Строковые структуры данных: Ахо-Корасик, суффиксный массив, суффиксный автомат.
- Алгоритмы поиска потоков в сетях.
- Продвинутые геометрические алгоритмы: вращающийся scanline, пересечение полуплоскостей, диаграмма Вороного, триангуляция Делоне.
- Splay-деревья, link-cut.
- Алгоритмы поиска минимальных глобальных разрезов.
- Нетривиальные алгоритмы на графах: венгерский алгоритм, алгоритм двух китайцев, дерево доминаторов.
- Матроиды.
- Алгоритмы во внешней памяти.
- И многое-многое другое...
Параллель A'
Для кого? Параллель рассчитана на призеров регионального этапа Всероссийской олимпиады по информатике. Необходимо разбираться в алгоритмах и структурах данных уровня параллелей B'-B ЛКШ, а также быть готовым решать много задач и развиваться до уровня дипломантов Всероссийской олимпиады по информатике.
Преподаватели: Иван Сафонов, Константин Амеличев и Дмитрий Умнов
Примеры тем:
- Структуры данных: от дерева отрезков до splay-дерева.
- Оптимизации динамического программирования: convex hull trick, meet-in-the-middle, divide and conquer
- Декомпозиции деревьев: centroid, heavy-light, ladder.
- Задачи на графах: паросочетания, потоки, dinamic connectivity problem.
- Геометрия: выпуклые оболочки, сумма Минковского.
- Строки: хэши, Ахо-Корасик, суффиксный массив.
- Полезные трюки: STL, битовые оптимизации, стресс-тестирование.
Параллель B
Для кого? Параллель рассчитана на участников регионального и победителей-призёров муниципального этапов Всероссийской олимпиады. Необходимо комфортно владеть языком программирования (рекомендуется C++) а также разбираться в алгоритмах и структурах данных уровня параллелей C-C' ЛКШ или другой аналогичной школы.
Преподаватели: Максим Деб Натх, Артем Рябов и Игорь Маркелов
Примеры тем:
- Графы: BFS, DFS, их применения. Алгоритмы поиска кратчайших путей во взвешенных графах (Форда-Беллмана, Дейкстры, Флойда). Минимальные остовные деревья. Паросочетания, алгоритм Куна.
- Деревья: алгоритм поиска наименьшего общего предка в дереве. Эйлеров обход. Декомпозиции дерева (heavy-light, centroid)
- Строки: префикс-, Z- функции, бор, автомат Ахо-Корасик, хеширование. Суффиксный массив.
- Динамическое программирование: одномерное, многомерное, по подмаскам, подграфам, подотрезкам, подмножествам, профилю и изломанному профилю.
- Структуры данных: дерево отрезков с массовыми операциями, декартово дерево, sparse table, система непересекающихся множеств. Дерево Фенвика.
- Геометрия: базовые примитивы, алгоритмы построения выпуклой оболочки, быстрые алгоритмы в вычислительной геометрии (например, построение касательной к выпуклому многоугольнику).
- И много других тем: теория Шпрага-Гранди, корневая оптимизация, метод разделяй-и-властвуй, решето Эратосфена, задача дискретного логарифмирования, meet-in-the-middle.
Параллель B'
Для кого? Параллель рассчитана на участников муниципального этапа Всероссийской олимпиады, то есть тех, кто уже начал знакомство с олимпиадным программированием и уверенно себя чувствует в базовых темах параллели C' ЛКШ. Необходимо знать синтаксис языка программирования и иметь опыт решения олимпиадных задач по программированию.
Преподаватели: Глеб Лобанов, Александр Гришутин и Андрей Одинцов.
Примеры тем:
- C++ с нуля.
- Важные структуры данных: дерево отрезков, разреженные таблицы, СНМ.
- Динамическое программирования: до динамики по подстрокам, подмножествам и цифрам.
- Алгоритмы на графах: до поиска мостов, точек сочленения, построения минимального остова.
- Простейшие алгоритмы на деревьях: LCA, LA, эйлеров обход.
- Базовые алгоритмы на строках: префикс-функция, зет-функция, хэши и бор.
- Геометрия: от векторов и прямых до многоугольников и выпуклой оболочки.
Параллель C
Для кого? Параллель рассчитана на школьников, которые никогда не занимались олимпиадным программированием или неуверенно себя чувствуют в базовых темах уровня параллели C' ЛКШ, и хотят познакомиться с ними поближе. Необходимо знать синтаксис одного из языков программирования и уметь решать простейшие задачи по математике и программированию.
Преподаватели: Егор Гутров и Полина Романченко.
Примеры тем:
- C++ с нуля.
- Сортировки: квадратичные, MergeSort, QuickSort.
- Бинарный поиск: обычный и по ответу.
- Теория чисел: алгоритм Евклида, разбиение числа на простые.
- Простейшие структуры данных: vector, set, map, стек, очередь, дек.
- Базовое динамическое программирование: с нуля до задач о рюкзаке, НВП, НОП, подсчет комбинаторных объектов.
- Базовые алгоритмы на графы: хранение, поиск в глубину, ширину, алгоритмы Дейкстры, Флойда, Форда-Беллмана, конденсация графа.
- Простая геометрия: векторы, прямые, окружности.