Информация о параллелях в ЛКШ.2021

Уровень Не старше Требуемые темы Ключевые темы к изучению
Начальный 7 класс
  • Знание одного из языков программирования
    • Python
    • C++
    • Java
    • Pascal
    • PascalABC
    • C#
  • Рекурсия
  • Двоичный поиск и быстрые сортировки
  • Динамическое программирование
  • Введение в теорию графов
Базовый 8 класс
  • Рекурсия
  • Двоичный поиск
  • Введение в теорию графов
  • Проверка числа на простоту, поиск делителей, нахождение НОД и другие арифметические алгоритмы
  • Линейные алгоритмы
  • Сортировка событий
  • Динамическое программирование
  • Обходы в ширину и глубину
  • Кратчайшие пути на графах
  • Дерево отрезков
Уверенный 9 класс
  • Базовое динамическое программирование (НОП, НВП, задача о рюкзаке)
  • Кратчайшие пути на графах
  • Обходы в ширину и глубину
  • Дерево отрезков
Рекомендуется владеть языком программирования C++
  • Применения обхода в глубину (мосты, точки сочленения, эйлеров путь)
  • Дерево Фенвика, корневая оптимизация
  • Продвинутые применения дерева отрезков
  • Декартово дерево
  • Динамическое программирование по подмножествам, поддеревьям
  • Базовая геометрия
  • Базовые строковые алгоритмы (хеширование, Z и префикс-функции)
Продвинутый 10 класс
  • Продвинутые применения дерева отрезков
  • Применения обхода в глубину
  • Динамическое программирование, в том числе по подотрезкам
  • Базовая геометрия
  • Хеширование строк
  • Оптимизации динамического программирования
  • Heavy-light декомпозиция, центроидная декомпозиция
  • Продвинутые строковые алгоритмы (алгоритм Ахо-Корасик, суффиксный массив)
  • Персистентные структуры данных
  • Быстрые алгоритмы в геометрии: построение касательной к выпуклому многоугольнику, сумма Минковского.
Эксперт 10 класс
  • Оптимизации динамического программирования
  • Heavy-light декомпозиция, центроидная декомпозиция, задача об LCA
  • Алгоритм Ахо-Корасик
  • Персистентные структуры данных
  • Корневая оптимизация
  • Паросочетания
  • Разделяй и властвуй
  • Суффиксные структуры данных
  • Потоки в графах
  • Быстрое преобразование Фурье
Продвинутые темы, в зависимости от состава группы, например:
  • Splay дерево
  • Дерево доминаторов
  • Сиплекс-метод
  • Теория игр
  • Матроиды
  • Производящие функции

Если вы уже учились в ЛКШ ранее, то для вас также наложены дополнительные ограничения на уровни вступительной. Для каждой параллели определен уровень, начиная с которого вы можете выполнять работу (можно выполнять работу уровнем выше, нельзя выполнять работу уровнем ниже).

Параллель ЛКШ.Зима 2020 или ЛКШ 2019 и раньше Уровень
С’ Базовый
C, C.python, C.cpp, B’ Уверенный
B, A’ Продвинутый
A, A0 Эксперт
lksh@lksh.ru