qoo2p5's blog

By qoo2p5, history, 2 months ago, In Russian,

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

Курс алгоритмов проводится еще и в Санкт-Петербурге, Новосибирске, Рязани, Нижнем Новогороде, Екатеринбурге и Ижевске. О других направлениях и городах можете прочитать здесь. Подробности можете спрашивать у Татьяны Колинковой, контакты которой даны ниже.

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

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

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

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

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

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

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

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

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

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

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

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

Если вы в течение суток не получили никаких ответных писем, проверьте папку со спамом, если и это не помогло — пишите нам.

Как с нами связаться?

Пишите в Telegram Татьяне Колинковой: @Tatyana_Kolinkova. Если нет возможности написать в Telegram, используйте электронную почту best-talents@tinkoff.ru.

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

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

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

Read more »

 
 
 
 
  • Vote: I like it
  • +27
  • Vote: I do not like it

By qoo2p5, 9 months ago, In Russian,

Привет!

В сентябре я начал преподавать алгоритмы в кружке 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 января и продлится неделю. После окончания отборочного тура вам придет письмо с дальнейшей информацией.

Общие вопросы по кружку задавайте в комментариях или пишите на почту best-talents@tinkoff.ru.

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

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

Read more »

 
 
 
 
  • Vote: I like it
  • +106
  • Vote: I do not like it

By qoo2p5, 18 months ago, translation, In English,

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!

Read more »

 
 
 
 
  • Vote: I like it
  • +83
  • Vote: I do not like it

By qoo2p5, 22 months ago, In English,

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!

Read more »

 
 
 
 
  • Vote: I like it
  • +67
  • Vote: I do not like it

By qoo2p5, history, 22 months ago, In Russian,

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

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

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

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

Read more »

 
 
 
 
  • Vote: I like it
  • +29
  • Vote: I do not like it

By qoo2p5, history, 2 years ago, translation, In English,
Problem A. Key races
Problem B. The number on the board
Problem C. Star sky
Problem D. Palindromic characteristics
Problem E. The penguin's game
Problem F. Roads in the Kingdom

Read more »

 
 
 
 
  • Vote: I like it
  • +120
  • Vote: I do not like it

By qoo2p5, 2 years ago, translation, In English,

Hi!

On Monday, July 31, 2017, at 14:35 UTC rated Codeforces Round #427 for participants from the second division will take place. As always, participants from the first division can take part out of competition.

The problems for this round were prepared by me. Many thanks to Alexey Ilyukhov (Livace) for help in preparations of the round and testing the problems, AmirReza PoorAkhavan (Arpa) for proofreading the statements and testing the problems, Gaev Alexandr (krock21) for testing the problems, Nikolay Kalinin (KAN) for the round coordination and, of course, Mike Mirzayanov (MikeMirzayanov) for great Codeforces and Polygon platforms.

The round will last for 2 hours, and you will be given 6 problems. I recommend you to read the statements of all problems. I hope everyone will find an interesting problem!

Scoring will be announced before the round.

Scoring: 500 — 750 — 1250 — 1500 — 2250 — 2250.

UPD.

Thanks for participating!

The editorial is here.

Congratulations to the winners!

Div2:

  1. ywwyww

  2. nick452

  3. JustAnAverageCoder123

  4. cxt

  5. wa1tz7I9

Div1:

  1. dotorya

  2. rajat1603

  3. anta

  4. Kaban-5

  5. HellKitsune

Read more »

 
 
 
 
  • Vote: I like it
  • +347
  • Vote: I do not like it

By qoo2p5, 2 years ago, In Russian,

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

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

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

Read more »

 
 
 
 
  • Vote: I like it
  • +27
  • Vote: I do not like it

By qoo2p5, 2 years ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it
  • +72
  • Vote: I do not like it