Tinkoff Generation

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

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

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

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

Параллель X

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

Примеры тем

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

Параллель B

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

Примеры тем

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

Параллель B'

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

Примеры тем

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

Параллель C

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

Примеры тем

Бинарный поиск и его модификации.
Базовые структуры данных: стеки, очереди, деки, двоичная куча. Решение задач.
Работа с STL C++: lower_bound/upper_bound, ordered/unordered set/map, bitset, и методы работы с ними
Линейные алгоритмы: префиксные суммы, два указателя, минимум в плавающем окне.
Графы: методы хранения графов в памяти. Обход в глубину. Поиск кратчайших путей в графе: BFS, алгоритмы Дейкстры, Флойда, Форда-Беллмана.
Динамическое программирование: одномерное, двумерное. Задачи о рюкзаке, НВП, НОП.
Генерация комбинаторных объектов. Поиск порядкового номера объекта (перестановки, сочетания, ПСП)/объекта по номеру.
Сканирующая прямая, жадные подходы в решении задач
Дерево отрезков
Геометрия: векторы, скалярное/векторное произведение, поиск пересечения прямых/отрезков/окружностей, поиск касательных к окружностям, проверка принадлежности точки многоугольнику.