Информация об уровнях в ЛКШ.2022
| Уровень |
Не старше |
Требуемые темы |
Ключевые темы к изучению |
| Начальный |
7 класс |
- Знание одного из языков программирования
- Python
- C++
- Java
- Pascal
- PascalABC
- C#
|
- Рекурсия
- Двоичный поиск и быстрые сортировки
- Динамическое программирование
- Введение в теорию графов
|
| Базовый |
8 класс |
- Рекурсия
- Двоичный поиск
- Введение в теорию графов
- Проверка числа на простоту, поиск делителей, нахождение НОД и другие арифметические алгоритмы
|
- Линейные алгоритмы
- Сортировка событий
- Динамическое программирование
- Обходы в ширину и глубину
- Кратчайшие пути на графах
- Дерево отрезков
|
|
Уверенный
|
9 класс
|
- Базовое динамическое программирование (НОП, НВП, задача о рюкзаке)
- Кратчайшие пути на графах
- Обходы в ширину и глубину
- Дерево отрезков
Рекомендуется владеть языком программирования C++
|
- Применения обхода в глубину (мосты, точки сочленения, эйлеров путь)
- Дерево Фенвика, корневая оптимизация
- Продвинутые применения дерева отрезков
- Декартово дерево
- Динамическое программирование по подмножествам, поддеревьям
- Базовая геометрия
- Базовые строковые алгоритмы (хеширование, Z и префикс-функции)
|
|
Продвинутый
|
10 класс
|
- Продвинутые применения дерева отрезков
- Применения обхода в глубину
- Динамическое программирование, в том числе по подотрезкам
- Базовая геометрия
- Хеширование строк
|
- Оптимизации динамического программирования
- Heavy-light декомпозиция, центроидная декомпозиция
- Продвинутые строковые алгоритмы (алгоритм Ахо-Корасик, суффиксный массив)
- Персистентные структуры данных
- Быстрые алгоритмы в геометрии: построение касательной к выпуклому многоугольнику, сумма Минковского.
|
|
Эксперт
|
10 класс
|
- Оптимизации динамического программирования
- Heavy-light декомпозиция, центроидная декомпозиция, задача об LCA
- Алгоритм Ахо-Корасик
- Персистентные структуры данных
- Корневая оптимизация
- Паросочетания
- Разделяй и властвуй
|
- Суффиксные структуры данных
- Потоки в графах
- Быстрое преобразование Фурье
Продвинутые темы, в зависимости от состава группы, например:
- Splay дерево
- Дерево доминаторов
- Сиплекс-метод
- Теория игр
- Матроиды
- Производящие функции
|
Если вы уже учились в ЛКШ ранее, то для вас также наложены дополнительные ограничения на уровни вступительной. Для каждой параллели определен уровень, начиная с которого вы можете выполнять работу (можно выполнять работу уровнем выше, нельзя выполнять работу уровнем ниже).
| Параллель ЛКШ.Зима 2020 или ЛКШ 2019 и раньше |
Параллель ЛКШ 2021 |
Уровень |
| С’ |
1 |
Базовый |
| C, C.python, C.cpp, B’ |
2,3,4 |
Уверенный |
| B, A’ |
5,6,7 |
Продвинутый |
| A, A0 |
8,9,10 |
Эксперт |