| Параллель |
Для кого |
Примеры изучаемых тем
|
| А |
Параллель рассчитана на опытных олимпиадников: участников и дипломантов Всероссийской олимпиады по информатике. Необходимо отлично разбираться в алгоритмах и структурах данных уровня параллелей B-A' ЛКШ.
|
- Нетривиальные алгоритмы и задачи теории чисел.
- Декомпозиции деревьев: centroid, heavy-light, ladder.
- Задачи на графах: 2-SAT, паросочетания, остовы и их применение в задачах.
- Продвинутые структуры данных: неявные деревья отрезков, двумерные структуры, персистентные структуры, разные структуры и алгоритмы дня нахождения минимумов.
- Строковые структуры данных: Ахо-Корасик, суффиксный массив, суффиксный автомат.
- Алгоритмы поиска потоков в сетях.
- Продвинутые геометрические алгоритмы: вращающийся scanline, пересечение полуплоскостей, диаграмма Вороного, триангуляция Делоне.
- Splay-деревья, link-cut.
- Алгоритмы поиска минимальных глобальных разрезов.
- Нетривиальные алгоритмы на графах: венгерский алгоритм, алгоритм двух китайцев, дерево доминаторов.
- Матроиды.
- Алгоритмы во внешней памяти.
- И многое-многое другое...
|
| A'
|
Параллель рассчитана на призеров регионального этапа Всероссийской олимпиады по информатике. Необходимо разбираться в алгоритмах и структурах данных уровня параллелей B'-B ЛКШ, а также быть готовым решать много задач и развиваться до уровня дипломантов Всероссийской олимпиады по информатике.
|
- Все важнейшие структуры данных: дерево отрезков, декартово дерево, разреженные таблицы
- Базовые а также продвинутые алгоритмы на строках: от префикс-функции до автомата Ахо-Корасик
- Базовые и не очень алгоритмы вычислительной геометрии
- LCA, LA, эйлеров обход, декомпозиции дерева
- Динамическое программирование
- Классические алгоритмы на графах: от применений DFS до алгоритма Куна и минимальных остовных деревьев"
|
| B
|
Параллель рассчитана на участников регионального и победителей-призёров муниципального этапов Всероссойской олимпиады. Необходимо комфортно владеть языком программирования (рекомендуется -- C++) а также разбираться в алгоритмах и структурах данных уровня параллелей C-C' ЛКШ или другой аналогичной школы.
|
- Все важнейшие структуры данных: дерево отрезков, декартово дерево, разреженные таблицы
- Базовые а также продвинутые алгоритмы на строках: от префикс-функции до автомата Ахо-Корасик
- Базовые и не очень алгоритмы вычислительной геометрии
- LCA, LA, эйлеров обход, декомпозиции дерева
- Динамическое программирование
- Классические алгоритмы на графах: от применений DFS до алгоритма Куна и минимальных остовных деревьев"
|
| B'
|
Параллель рассчитана на участников муниципального этапа Всероссийской олимпиады, то есть тех, кто уже начал знакомство с олимпиадным программированием и уверенно себя чувствует в базовых темах параллели C' ЛКШ. Необходимо знать синтаксис языка программирования и иметь опыт решения олимпиадных задач по программированию.
|
- C++ с нуля
- Важные структуры данных: дерево отрезков, разреженные таблицы, СНМ
- Динамическое программирования: до динамики по подстрокам, подмножествам и цифрам
- Алгоритмы на графах: до поиска мостов, точек сочленения, построения минимального остова
- Простейшие алгоритмы на деревьях: LCA, LA, эйлеров
- Базовые алгоритмы на строках: префикс-функция, зет-функция, хэши и бор
- Геометрия: от векторов и прямых до многоугольников и выпуклой оболочки"
|
| С
|
Параллель рассчитана на школьников, которые никогда не занимались олимпиадным программированием или неуверенно себя чувствуют в базовых темах уровня параллели C' ЛКШ, и хотят познакомиться с ними поближе. Необходимо знать синтаксис одного из языков программирования и уметь решать простейшие задачи по математике и программированию.
|
- C++ с нуля
- Сортировки: квадратичные, MergeSort, QuickSort
- Бинарный поиск: обычный и по ответу
- Теория чисел: алгоритм Евклида, разбиение числа на простые
- Простейшие структуры данных: vector, set, map, стек, очередь, дек
- Базовое динамическое программирование: с нуля до задач о рюкзаке, НВП, НОП, подсчет комбинаторных объектов
- Базовые алгоритмы на графы: хранение, поиск в глубину, ширину, алгоритмы Дейкстры, Флойда, Форда-Беллмана, конденсация графа
- Простая геометрия: векторы, прямые, окружности"
|