Алгоритмические параллели в ЛКШ-2025

В ЛКШ 2025 планируется 10 алгоритмических параллелей.

Темы, которые изучаются в соседних параллелях (и даже через одну) часто пересекаются. Мы ожидаем, что поступающие в определенную параллель школьники ранее слышали 20-50% материала и планируют его закреплять и дополнять знания новым материалом.

Уровень

Параллель

Что надо знать, чтобы поступить

Какие есть ограничения

Основные темы в параллели

начальный

1

любой язык программирования, желательно Python

6-8 класс, недоступно для тех, кто учился в кружках Яндекса или Т-образования в течение года

Сортировка, линейный поиск, бинарный поиск, стеки, очереди, базовые задачи динамического программирования, BFS, DFS, рекурсия

начальный

2

любой язык программирования, желательно Python

работа с массивами, сортировка, поиск

6-8 класс, недоступно для тех, кто учился в кружках Яндекса или Т-образования в течение года

Бинарный поиск, стеки, очереди, динамическое программирование, BFS, DFS, кратчайшие пути, остовные деревья, комбинаторика

базовый

3

Python или С++

бинарный поиск, базовое ДП, хранение графов, DFS, рекурсия

6-8 класс

Графы, применения DFS, кратчайшие пути, динамическое программирование (задача о рюкзаке, задачи на деревьях и отрезках), деревья отрезков, строки, хеширование

базовый

4

С++

базовое ДП, графы, DFS, базовая работа со строками

6-9 класс

Деревья отрезков (стандартное и массовые операции), разреженные таблицы, перебор, динамическое программирование (задачи на деревьях и отрезках, подмножества, маски), строки (хеши, префикс-функция, Z-функция, бор), графы (мосты, точки сочленения, остовы), геометрия

уверенный

5

С++

дерево отрезков, графы (обходы, кратчайшие пути), строки

6-9 класс

Структуры данных (ДО, Фенвик, разреженные таблицы, декартовы деревья), геометрия (базовые операции, многоугольники, выпуклая оболочка, локализация точки), строки (префикс-функция, Z-функция, бор), графы и задачи на деревьях (LCA, LA, продвинутые кратчайшие пути)

уверенный

6

C++

дерево отрезков, графы, основы геометрии, строки

6-10 класс

Декартово дерево, корневая декомпозиция, LCA, LA, КСС, Эйлеров цикл, геометрия (окружности, многоугольники, касательные), паросочетания, строки (алгоритмы поиска, Ахо-Корасик), продвинутые методы в ДП

уверенный

7

С++

структуры данных (дерево отрезков, ДД), графы, геометрия, строки

6-10 класс

Персистентность, алгоритмы на деревьях (LCA, LA, HLD, центроиды), оптимизации ДП, геометрия (работа с выпуклыми многоугольниками, рандомизированные алгоритмы, пересечение полуплоскостей), корневая оптимизация, суффиксный массив, потоки

продвинутый

8

С++

структуры данных, графы, геометрия, строки, деревья

6-10 класс

Персистентность, алгоритмы на деревьях (LCA, LA, HLD, центроиды), оптимизации ДП, геометрия, суффиксные структуры данных (массив, автомат), потоки, стоимостные потоки, быстрое преобразование Фурье

продвинутый

9

С++

структуры данных, графы, оптимизации ДП, геометрия, потоки

6-10 класс

Теория чисел, FFT, продвинутая геометрия, splay-tree, link-cut tree, суффиксные структуры данных, продвинутые оптимизации ДП, матроиды

продвинутый

10

С++

большинство более-менее стандартной теории

6-10 класс

можно приехать несколько раз

Программа адаптируется каждый год, рассматриваются продвинутые алгоритмы и структуры данных, которые обычно не рассказывают в кружках и других параллелях.

lksh@lksh.ru