Привет! Скоро начнется новый учебный год, а вместе с ним и разные олимпиадные кружки. Я хочу рассказать об одном из них, Tinkoff Generation, а если еще точнее — о курсе алгоритмов в Москве, преподавателем которого являюсь. О других направлениях и городах можете прочитать здесь.

Мы открылись в прошлом году, получили много фидбека и за лето провели работу по улучшению, так что надеемся, что в этом году кружок будет еще интереснее и полезнее.

Какой уровень занятий?

В этом году у нас будет пять параллелей: C, B', B, A' и A. Параллели примерно соответствуют соответствующим параллелям в ЛКШ по начальному уровню учащихся, но в среднем программа сложнее, потому что занятий за год сильно больше, чем за одну смену в ЛКШ, практики тоже сильно больше, потому что на решение задачек по теме есть целая неделя. Подробное описание параллелей есть ниже.

Где и когда проходят занятия?

Занятия проходят по субботам с 16:00 по 21:00 в офисе Тинькофф, который расположен в БЦ «Водный» (несколько минут пешком от м. Водный Стадион). В середине занятий есть перерыв на еду.

Как проходят занятия?

Что конкретно происходит во время занятий зависит от параллели, но можно выделить следующие основные виды деятельности: разбор, лекция/семинар и практика. После каждого занятия на неделю дается тематический контест.

Дистанционные туры

Мы с Филиппом (grphil) в прошлом году решили попробовать в своей группе A давать на неделю кроме тематического тура еще и дистанционный — так мы называем виртуальный контест с задачами, взятыми с настоящих олимпиад, в основном других стран, чтобы их до этого никто не видел. Эта идея оказалась очень успешной, и теперь мы будем делать дистанционные туры для всех параллелей: туры уровня заключительного, регионального и муниципального этапов Всероссийской олимпиады. Более того, в этом году дистанционные туры будут доступны для всех желающих, независимо от того, посещаете ли вы наши кружки. Ссылка на анкету для регистрации можете найти здесь.

Кто ведет занятия?

Все преподаватели — опытные олимпиадники, которые в школе становились призерами и победителями самых разных олимпиад по информатике: Всероссийской олимпиады, ВКОШП и многих других. Есть и те, кто до сих пор участвует в олимпиадах, но уже студенческих, среди них есть медалисты Чемпионата мира по программированию.

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

Параллель C

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

Преподаватели: Егор Гутров (w8_m8) и Полина Романченко (Romanchenko).

Примеры тем:

• C++ с нуля.
• Сортировки: квадратичные, MergeSort, QuickSort.
• Бинарный поиск: обычный и по ответу.
• Теория чисел: алгоритм Евклида, разбиение числа на простые.
• Простейшие структуры данных: vector, set, map, стек, очередь, дек.
• Базовое динамическое программирование: с нуля до задач о рюкзаке, НВП, НОП, подсчет комбинаторных объектов.
• Базовые алгоритмы на графы: хранение, поиск в глубину, ширину, алгоритмы Дейкстры, Флойда, Форда-Беллмана, конденсация графа.
• Простая геометрия: векторы, прямые, окружности.

Параллель B'

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

Преподаватели: Глеб Лобанов (Glebodin).

Примеры тем:

• C++ с нуля.
• Важные структуры данных: дерево отрезков, разреженные таблицы, СНМ.
• Динамическое программирования: до динамики по подстрокам, подмножествам и цифрам.
• Алгоритмы на графах: до поиска мостов, точек сочленения, построения минимального остова.
• Простейшие алгоритмы на деревьях: LCA, LA, эйлеров обход.
• Базовые алгоритмы на строках: префикс-функция, зет-функция, хэши и бор.
• Геометрия: от векторов и прямых до многоугольников и выпуклой оболочки.

Параллель B

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

Преподаватели: Максим Деб Натх (DebNatkh), Артем Рябов (SoMuchDrama), Сергей Слотин (sslotin) и Андрей Чулков (achulkov2).

Примеры тем:

• Графы: BFS, DFS, их применения. Алгоритмы поиска кратчайших путей во взвешенных графах (Форда-Беллмана, Дейкстры, Флойда). Минимальные остовные деревья. Паросочетания, алгоритм Куна.
• Деревья: алгоритм поиска наименьшего общего предка в дереве. Эйлеров обход. Декомпозиции дерева (heavy-light, centroid)
• Строки: префикс-, Z- функции, бор, автомат Ахо-КОрасик, хеширование. Суффиксный массив.
• Динамическое программирование: одномерное, многомерное, по подмаскам, подграфам, подотрезкам, подмножествам, профилю и изломанному профилю.
• Структуры данных: дерево отрезков с массовыми операциями, декартово дерево, sparse table, система непересекающихся множеств. Дерево Фенвика.
• Геометрия: базовые примитивы, алгоритмы построения выпуклой оболочки, быстрые алгоритмы в вычислительной геометрии (например, построение касательной к выпуклому многоугольнику).
• И много других тем: теория Шпрага-Гранди, корневая оптимизация, метод разделяй-и-властвуй, решето Эратосфена, задача дискретного логарифмирования, meet-in-the-middle".

Параллель A'

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

Формат занятий. В начале каждого занятия проводится разбор предыдущих туров: тематического и дистанционного. Далее идет лекция или семинар (а иногда и то, и другое). На семинарах учащиеся сдают задачи с листочка преподавателям. Параллельно, с некоторой задержкой, достаточной, чтобы успеть подумать над соответствующими задачами, проводится их разбор.

Преподаватели: Иван Сафонов (isaf27) и Константин Амеличев (KiKoS).

Примеры тем:

• Структуры данных: от дерева отрезков до splay-дерева.
• Оптимизации динамического программирования: convex hull trick, meet-in-the-middle, divide and conquer
• Декомпозиции деревьев: centroid, heavy-light, ladder.
• Задачи на графах: паросочетания, потоки, dinamic connectivity problem.
• Геометрия: выпуклые оболочки, сумма Минковского.
• Строки: хэши, Ахо-Корасик, суффиксный массив.
• Полезные трюки: STL, битовые оптимизации, стресс-тестирование.

Параллель A

Для кого? Параллель рассчитана на опытных олимпиадников: участников и дипломантов Всероссийской олимпиады по информатике. Необходимо отлично разбираться в алгоритмах и структурах данных уровня параллелей B-A' ЛКШ.

Формат занятий. В начале каждого занятия проводится разбор предыдущих туров: тематического и дистанционного. Далее идет лекция или семинар (а иногда и то, и другое). На семинарах учащиеся сдают задачи с листочка преподавателям. Параллельно, с некоторой задержкой, достаточной, чтобы успеть подумать над соответствующими задачами, проводится их разбор.

Преподаватели: Филипп Грибов (grphil) и я, Даниил Николенко (qoo2p5).

Примеры тем:

• Нетривиальные алгоритмы и задачи теории чисел.
• Декомпозиции деревьев: centroid, heavy-light, ladder.
• Задачи на графах: 2-SAT, паросочетания, остовы и их применение в задачах.
• Продвинутые структуры данных: неявные деревья отрезков, двумерные структуры, персистентные структуры, разные структуры и алгоритмы дня нахождения минимумов.
• Строковые структуры данных: Ахо-Корасик, суффиксный массив, суффиксный автомат.
• Алгоритмы поиска потоков в сетях.
• Продвинутые геометрические алгоритмы: вращающийся scanline, пересечение полуплоскостей, диаграмма Вороного, триангуляция Делоне.
• Splay-деревья, link-cut.
• Алгоритмы поиска минимальных глобальных разрезов.
• Нетривиальные алгоритмы на графах: венгерский алгоритм, алгоритм двух китайцев, дерево доминаторов.
• Матроиды.
• Алгоритмы во внешней памяти.
• И многое-многое другое...

Как попасть на кружок?

Нужно написать отбор. Зарегистрироваться на него можно здесь. Так как параллелей стало больше, отбор должны написать даже те, кто ходил к нам прошлом году и отлично сдал зачет. Дипломанты различных олимпиад также должны писать отбор: мы хотим, чтобы вы попали в параллель, которая будет действительно соответствовать вашему уровню.