Всем привет!

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

Сейчас открыт отбор в кружок по олимпиадному программированию «Тинькофф Поколение». Один из классных плюсов кружка — он абсолютно бесплатный, но нужно написать вступительный контест, который открыт до 12 сентября включительно. Зарегистрироваться и начать решать можно здесь: algocode.ru.

Ниже мы постараемся подробнее описать как все устроено в кружке. Если у вас останутся вопросы, задать их можно в комментариях к посту или в telegram (внизу есть наши контакты).

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

Про формат занятий

По результатам отборочного контеста мы разделим участников на учебные параллели. У каждой параллели есть своя группа преподавателей, которые будут читать лекции, помогать с решением задач и написанием кода. Их всегда можно будет попросить объяснить непонятную тему, подсказать тест или найти ошибку в программе.

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

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

• с сентября по декабрь — к муниципальному этапу;
• с сентября по январь — к региональному этапу;
• с сентября по март — к заключительному этапу.

Занятия будут проходить по субботам с 16:00 до 21:00 по московскому времени.

В прошлом году из-за пандемии мы проводили очные занятия для школьников из Москвы и онлайн для ребят, которые не могли посещать занятия очно. В этом году планируем продолжить опыт гибридных занятий: очно+online (каждый год во время анонса кружка прилетают вопросы про участие в кружке ребят из других стран. Мы будем рады всем, но нужно понимать, что основной фокус на школьников из России, и во время подготовки к олимпиадам есть своя специфика).

1. Онлайн

Мы проводим занятия для участников из всех регионов. Лекции проводятся в Zoom. Занятия проводят преподаватели, которые также очно преподают в московском кружке и принимают участие в подготовке олимпиад и проведении сборов. Это возможность заниматься на равне со школьниками из крупных городов.

2. Очно

Очные занятия проходят в Штаб-квартире Тинькофф

• Москва: Штаб-квартира Тинькофф,  ст. м. Водный стадион, БЦ «Водный», Головинское шоссе 5А

Если наберется, достаточное количество участников, мы готовы проводить занятия очно в Центре Разработки Тинькофф в Санкт-Петербурге по адресу:

• Санкт-Петербург, ул. Херсонская, дом 12\14, БЦ «Ренессанс Правда»

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

Параллель А

Параллель рассчитана на опытных олимпиадников: участников и дипломантов Всероссийской олимпиады по информатике прошлого года. Научим решать сверхсложные и нетипичные задачи.

Преподаватели: Филипп grphil Грибов и Егор peltorator Горбачев

Примеры тем:

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

Параллель A'

Для опытных олимпиадников — участников финала Всероса по информатике, Открытой олимпиады и других перечневых олимпиад.

Преподаватели: Иван isaf27 Сафонов, Константин KiKoS Амеличев и Дмитрий _overrated_ Умнов.

Примеры тем:

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

Параллель B

Для тех, кто владеет С++ или Java и уверенно проходит на региональный этап Всероса.

Преподаватели: Максим DebNatkh Деб Натх, Артем SoMuchDrama Рябов, Игорь Siberian Маркелов.

Примеры тем:

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

Параллель B'

Для тех, кто на базовом уровне владеет С++, Python или Java и участвовал в муниципальном этапе Всероссийской олимпиады школьников по информатике прошлого года.

Преподаватели: Глеб Glebodin Лобанов, Александр rationalex Гришутин и Андрей forestryks Одинцов.

Примеры тем:

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

Параллель C

Параллель рассчитана на школьников, которые никогда не занимались олимпиадным программированием или неуверенно себя чувствуют в базовых темах и хотят познакомиться с ними поближе. Необходимо знать синтаксис любого языка программирования и уметь решать простейшие задачи по математике и программированию. В эту параллель не зачисляются школьники, которые перешли в 11 класс.

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

Примеры тем:

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

Зарегистрироваться и начать решать можно по ссылке: algocode.ru.

Другие направления

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

Контакты

Если хотите узнать что-то подробнее, можете написать Тане TKolinkova Колинковой в телеграм @Tatyana_Kolinkova или на почту best-talents@tinkoff.ru.