Tinkoff Generation

Описание параллелей

Формат занятий

Параллель X
Занятия параллели преимущественно практические. Бо́льшая их часть будет представлять собой пятичасовой контест в формате РОИ и ICPC, который потребуется решать. Внутри параллели участников разобьют на три поддивизиона, между которыми будет возможно движение по результатам контестов. Для получения зачета по результатам обучения необходимо дорешивание контестов, которые окажутся разобраны через некоторое время. Помимо этого на занятиях планируются лекции на сложные алгоритмические высокого уровня.

Параллели B, B', C
В начале занятия проводится лекция по алгоритмической теме, затем на оставшееся время дается тематический контест. Раз в три-четыре занятия проводится разбор, после которого у участников остается неделя на окончательное дорешивание. По его итогам выставляется оценка за блок.

Параллель X

Для кого?
Параллель рассчитана на опытных олимпиадников уровня участников, призеров и победителей ВсОШ по информатике. Необходимо отлично разбираться в алгоритмах и структурах данных параллелей B, B', C нашего кружка.

Примеры тем

Поиск потоков в сетях: метод Форда-Фалкерсона, алгоритмы Эдмондса-Карпа, Диница, поиск максимальных потоков минимальной стоимости.
Быстрое преобразование Фурье его друзья: умножение и деление многочленов и длинных чисел, свертка Уолша-Адамара, ...
Продвинутые строковые структуры данных: суффиксное дерево, суффиксный автомат.
Сливаемые кучи: левацкая, косая, Фибоначчи.
Splay-дерево, link-cut tree.
Нетривиальные алгоритмы на графах: венгерский алгоритм, алгоритм двух китайцев, дерево доминаторов, ...

Параллель B

Для кого?
Параллель рассчитана на учеников уровня участников, призеров и победителей регионального этапа ВсОШ. Необходимо комфортно владеть языком программирования (рекомендуется C++), а также разбираться в алгоритмах и структурах данных параллели С нашего кружка. Параллель является продолжением параллели С.

Примеры тем

Поиск минимальных остовных деревьев, система непересекающихся множеств.
DFS: поиск компонент сильной связности, вершинной и реберной двусвязностей, нахождение мостов и точек сочленения, поиск паросочетаний.
Структуры данных: дерево отрезков с отложенными операциями, декартовы деревья по явному и неявному ключам, heavy-light decomposition, centroid decomposition, дерево Фенвика, персистентные структуры данных.
SQRT-декомпозиция: на массивах и запросах, алгоритм Мо и его модификации.
Динамическое программирование: НВП за O(n log n), метод Хиршберга, ДП на подмножествах/профилю.
Оптимизации ДП: convex hull trick, оптимизации Кнута, “разделяй-и-властвуй”, lambda-оптимизация.
Геометрия: выпуклые оболочки, поиск касательных к многоугольникам, сумма Минковского, метод сканирующей прямой.
Строки: алгоритм Ахо-Корасик, суффиксный массив.

Параллель B'

Для кого?
Параллель является средним между параллелями C и B и предназначена для тех, кто уже имеет некоторые знания в области алгоритмам и опыт решения олимпиадных задач, но еще не дотягивает до уровня параллели B (уровень участников, призеров и победителей муниципального этапа ВсОШ). Необходимо знать синтаксис языка программирования (рекомендуется С++) и владеть базовыми темами параллели С.

Примеры тем

Деревья: поиск диаметра, центра и центроида, LCA.
Структуры данных: префиксные суммы/разности, разреженные таблицы, деревья отрезков, технология отложенных операций, основы SQRT-декомпозиции, дерево Фенвика.
Строки: префикс-функция, z-функция, строковые хэши, бор, алгоритм Ахо-Корасик.
DFS: топологическая сортировка, поиск эйлерова пути/цикла, поиск компонент сильной связности, мостов, точек сочленения, компонент вершинной и реберной двусвязности.
Работа с STL: sort, unique, lower_bound/upper_bound, set/map и методы работы с ними и т.п.
Геометрия: векторы, скалярное/векторное произведение, поиск пересечения прямых/отрезков/окружностей, поиск касательных к окружностям, проверка принадлежности точки многоугольнику, выпуклые оболочки, касательные к многоугольникам, метод сканирующей прямой.
Динамическое программирование: на подотрезках, на поддеревьях, по подмножествам/профилю, поиск порядкового номера объекта (перестановки, сочетания, ПСП)/объекта по номеру, поиск НВП за O(n log n).

Параллель C

Для кого?
Параллель рассчитана на школьников, которые никогда/почти никогда не занимались олимпиадным программированием или неуверенно себя чувствуют в базовых темах спортивного программирования (см. примерную программу ниже), и хотят познакомиться с ними поближе. Необходимо знать синтаксис одного из языков программирования (лучше всего С++, ибо “разговаривать” преподаватели будут именно на этом языке) и уметь решать простейшие задачи по математике и программированию.

Примеры тем

Бинарный поиск и его модификации.
Базовые структуры данных: стеки, очереди, деки, двоичная куча. Решение задач.
Сортировки: выбором, вставками, пузырьком, слиянием, кучей, быстрая. Поиск К-ой порядковой статистики.
Графы: методы хранения графов в памяти. Поиск кратчайших путей в графе: BFS, 0-1-BFS, [A-2A]-BFS, алгоритмы Дейкстры, Флойда, Форда-Беллмана.
Введение в динамическое программирование: одномерное, двумерное. Задачи о рюкзаке, НВП, НОП.
Деревья: Деревья: поиск диаметра, центра и центроида, LCA.
Динамическое программирование на деревьях.
Поиск порядкового номера объекта (перестановки, сочетания, ПСП)/объекта по номеру.
Геометрия: векторы, скалярное/векторное произведение, поиск пересечения прямых/отрезков/окружностей, поиск касательных к окружностям, проверка принадлежности точки многоугольнику.
Строки: префикс-функция, z-функция, строковые хэши.