Блог пользователя qoo2p5

Автор qoo2p5, история, 5 лет назад, По-русски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

Автор qoo2p5, 5 лет назад, По-русски

Привет!

В сентябре я начал преподавать алгоритмы в кружке Tinkoff Generation. Занятия в кружке бесплатные. Осенью к нам пришли 150 школьников, успешно написавших вступительный контест. Мы готовы взять больше мотивированных школьников, поэтому сделали еще и зимний отбор. Приглашаем вас принять в нем участие. :)

Сейчас у нас 3 направления: алгоритмы и структуры данных, машинное и глубокое обучение и олимпиадная математика. В посте я расскажу о кружке по алгоритмам в Москве. Но кружки работают еще в Рязани и Нижнем Новгороде. А с нового года еще в Ижевске и Екатеринбурге. Подробнее.

В Москве мы разбили школьников на 3 курса. Они различаются по уровню. Занятия проходят по субботам с 16:00 по 21:00 в штаб-квартире Тинькофф в БЦ "Водный" на метро Водный стадион. Занятия проводят студенты ФКН ВШЭ и ФИВТ МФТИ, которые в школьные годы были победителями и призерами таких олимпиад как Всероссийская олимпиада по информатике, Открытая олимпиада, Технокубок, ВКОШП. Некоторые из преподавателей продолжают участие в студенческих олимпиадах и являются финалистами ICPC 2019.

3 курс

Преподаватели:

  • Филипп Грибов (grphil)
  • Даниил Николенко (qoo2p5)

Программа группы рассчитана на школьников уровня дипломантов и участников Всероссийской олимпиады, имеющих представление об алгоритмах уровня параллелей A'-A ЛКШ. В первом полугодии изучались такие темы как convex hull trick, divide and conquer, центроидная декомпозиция, small-to-large, heavy-light декомпозиция, лестничная декомпозиция, алгоритм Фараха-Колтона и Бендера, теория Гранди, альфа-бета отсечение, быстрое преобразование Фурье, персистентные структуры данных, двумерные деревья отрезков, корневые декомпозиции, суффиксный автомат, алгоритм Куна и его применения, эйлеровы графы, а также некоторые другие алгоритмы и структуры данных.

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

На неделю даем два тура. Один тематический, который можно решать всю неделю, а после разбора дорешивать, и один дистанционный — виртуальный пятичасовой тур в формате Всероссийской олимпиады.

Если вы владеете вышеописанными алгоритмами и хотите посещать занятия этой группы, пишите мне в Telegram (@qoo2p5) или ВК.

2 курс

Преподаватели:

Второй курс рассчитан на уровень участников и призеров региона, потенциальных участников и призеров всеросса, знакомых с простыми алгоритмами уровня параллелей С-B’ ЛКШ. Занятия длятся 5 часов и проводятся в группах до 15 человек. На занятиях дается необходимый теоретический материал, а также разбираются задачи на пройденную тему. Список тем, изученных в первом полугодии: дерево отрезков, декартово дерево, Z- и префикс- функции, бор, Ахо-Корасик, полиномиальное хеширование, LCA и связанные задачи, минимальный остов, динамическое программирование на примерах задач различной сложности.

Если вы хотите посещать занятия этого курса, прочитайте ниже про отбор в разделе "Отбор на 1 и 2 курсы в Москве".

1 курс

Преподаватели:

  • Андрей Гаркавый (andrewgark)
  • Максим Гришкин (riskingh)
  • Глеб Лобанов (Glebodin)
  • Антон Алешин

Программа курса рассчитана на начинающих школьников уровня призеров муниципального этапа, умеющих решать простые задачи по информатике в тестирующей системе на языке C++ или Питон. В первом полугодии уже изучались такие темы как сортировки, теория чисел, жадный алгоритм, STL, динамическое программирование (включая рюкзак и НВП-НОП), сканирующая прямая, графы, DFS и BFS.

Занятия состоят из лекции по теме и тематического контеста, обычно на informatics.mccme.ru. Часто дается еще один практический контест с олимпиадными задачами. Эти контесты далее можно и нужно дорешивать дома.

Если вы хотите посещать занятия этого курса, прочитайте ниже про отбор в разделе "Отбор на 1 и 2 курсы в Москве".

Отбор на 1 и 2 курсы в Москве

Если вы хотите посещать занятия этих курсов (для 3 курса читайте информацию в соответствующем разделе), пройдите регистрацию и примите участие в отборе на этом сайте. Отбор начнется в 12:00 12 января и продлится неделю. После окончания отборочного тура вам придет письмо с дальнейшей информацией.

Общие вопросы по кружку задавайте в комментариях или пишите на почту [email protected].

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

При проблемах с регистрацией попробуйте проверить папку "Спам", а если это не помогло, пишите мне в Telegram (@qoo2p5) или ВК.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +106
  • Проголосовать: не нравится

Автор qoo2p5, 6 лет назад, По-русски

Hello Codeforces Community!

I invite you all to join HackerRank's 101 Hack 54 on May 2, 2018, at 15:00 UTC.

There will be five problems in the round and three hours for you to solve them. The contest will be rated and the top ten contestants will receive HackerRank T-shirts!

Top 100 coders will get contacted by HackerRank for a job opportunity. (India only)

The problems are prepared by me. Thanks to kevinsogo, who tested and helped in setting up this contest.

I hope you’ll enjoy the problems and find them interesting.

Good luck and happy coding!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +83
  • Проголосовать: не нравится

Автор qoo2p5, 6 лет назад, По-английски

Hello Codeforces Community!

Happy New Year to all!

I invite you all to join HackerRank's HourRank 25 on January 2, 2018, at 20:30 IST.

There will be three tasks in the round and one hour for you to solve them. The contest will be rated and the top ten contestants will receive HackerRank T-shirts!

The problems are prepared by me and tested by niyaznigmatul. Thanks to kevinsogo for help in setting up this contest.

I hope you’ll enjoy the problems.

Good luck and Happy Coding!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +67
  • Проголосовать: не нравится

Автор qoo2p5, история, 6 лет назад, По-русски

За последние несколько дней Polygon перестал нормально работать. :(

Изменяю валидатор/генератор  –  ничего не меняется, запускаются старые бинарники. Main correct solution получает Rejected, хотя другие решения получают на этих тестах нормальные вердикты.

В общем, как будто перестало работать обновление генераторов, валидаторов, скриптов генерации тестов и всего остального тоже.

Кажется, эта проблема не только у меня.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +29
  • Проголосовать: не нравится

Автор qoo2p5, история, 7 лет назад, По-русски
Задача A. Кнопочные гонки
Задача B. Число на доске
Задача C. Звёздное небо
Задача D. Палиндромная характеристика
Задача E. Игра пингвина
Задача F. Дороги в королевстве

Полный текст и комментарии »

Разбор задач Codeforces Round 427 (Div. 2)
  • Проголосовать: нравится
  • +120
  • Проголосовать: не нравится

Автор qoo2p5, 7 лет назад, По-русски

Всем привет!

31 июля 2017 в 17:35 (по московскому времени) состоится рейтинговый Codeforces Round #427 для участников из второго дивизиона. Как всегда, участники из первого дивизиона смогут принять участие вне конкурса.

Задачи для этого раунда были подготовлены мною. Большое спасибо Алексею Илюхову (Livace) за помощь в подготовке раунда и прорешивание задач, AmirReza PoorAkhavan (Arpa) за вычитывание условий и прорешивание задач, Александру Гаеву (krock21) за прорешивание задач, Николаю Калинину (KAN) за координацию раунда и, конечно, Михаилу Мирзаянову (MikeMirzayanov) за замечательные платформы Codeforces и Polygon.

Раунд будет длиться 2 часа, и вам будет предложено 6 задач. Рекомендую прочитать условия всех задач. Надеюсь, каждый найдёт интересную для себя задачу!

Разбалловка будет объявлена перед началом раунда.

Разбалловка: 500 — 750 — 1250 — 1500 — 2250 — 2250.

UPD.

Cпасибо за участие в раунде!

Разбор здесь.

Поздравления победителям!

Div2:

  1. ywwyww

  2. nick452

  3. JustAnAverageCoder123

  4. cxt

  5. wa1tz7I9

Div1:

  1. dotorya

  2. rajat1603

  3. anta

  4. Kaban-5

  5. HellKitsune

Полный текст и комментарии »

  • Проголосовать: нравится
  • +347
  • Проголосовать: не нравится

Автор qoo2p5, 7 лет назад, По-русски

Здравствуйте!

Допустим, есть множество из n элементов a1, ..., an, на котором введено отношение частичного порядка  < , притом у нас есть оракул, который позволяет узнать: верно ли, что ai < aj. Необходимо отсортировать данные элементы, то есть найти такую перестановку b1, ..., bn, что не найдётся i < j таких, что bj < bi.

Хочется минимизировать количество обращений к оракулу. Понятно, что можно сделать O(n2) обращений, используя топологическую сортировку. Но можно ли делать это быстрее? Если нет, то интересно узнать доказательство этого.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

Автор qoo2p5, 7 лет назад, По-английски

I want to ask people who has already prepared Codeforces contests: how long had you been waiting for a response?

I have no response for more than 6 weeks... It's really disappointing.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +72
  • Проголосовать: не нравится