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

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

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

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

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

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

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

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

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

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

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

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

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

У меня остались вопросы. Как связаться с вами?

Пишите в Telegram Татьяне Колинковой: @Tatyana_Kolinkova. Если нет возможности написать в Telegram, используйте электронную почту [email protected].

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

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

Параллель 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.
• Алгоритмы поиска минимальных глобальных разрезов.
• Нетривиальные алгоритмы на графах: венгерский алгоритм, алгоритм двух китайцев, дерево доминаторов.
• Матроиды.
• Алгоритмы во внешней памяти.
• И многое-многое другое...