Algorithms Thread Episode 9: Treaps

Good morning everyone!

Episode 9 of AlgorithmsThread comes out shortly after the Div2 round ends. This episode is on Treaps! It covers:

• Fundamentals of Treaps
• Splitting and Merging
• Range reversing

... and more! I also decided to keep up the super-high quality style and made a custom gym set with 5(+2) original problems to make sure you really understand everything that was covered in the lecture. The gym set will be released shortly after the lecture ends, and I hope that the problems will be challenging and fun, even for people who aren't seeing treaps for the first time.

If you have any questions or suggestions, feel free to leave them below. I hope you enjoy the problem statements, and, in the spirit of the upcoming holiday, I'll leave you all with this:

Update: The scoring distribution for this round will be: 1 — 1 — 1 — 1 — (+1) — (+1) — 1

Update2: Solution video is out now and solutions to all problems are available here. Hope you all enjoyed the contest!

Привет, Codeforces!

Рад анонсировать и пригласить вас на Codeforces Round 678 (Div. 2), который пройдет 24.10.2020 17:05 (Московское время). Пару недель назад мы проводили Codeforces Round 675 (Div. 2) на основе задач Andersen Programming Contest 2020. Квалификация, а в этот раз мы хотим предложить вам порешать лучшие 5-6 задач финала.

Обратите, пожалуйста, внимание на необычное время начала раунда. Этот раунд будет рейтинговым для участников, чей рейтинг ниже 2100.

Компания Andersen уже второй год проводит соревнование, которое в первую очередь предназначено для поддержки студентов региональных ВУЗов Беларуси и Украины (с этого года). В этом году в финале соревнования примет участие 60 студентов региональных вузов Беларуси и Украины.

• Авторами раунда являются: Алексей aropan Ропан, Юрий hloya_ygrt Шиляев, Андрей andrew Мищенко, Александр AleXman111 Кривошеев и я.
• Координаторами раунда выступили Николай KAN Калинин и Ильдар 300iq Гайнуллин.
• Тестировали раунд: Борис PuRpLe_FoReVeR Серенков, Егор 244mhq Дубовик, cckk4467 и rafaelgo.
• И, конечно же, спасибо огромное Михаилу MikeMirzayanov Мирзаянову за cоздание платформ polygon и codeforces.

Всем выше перечисленным огромное спасибо за вклад, внесенный в подготовку раунда, а вам удачи на предстоящем соревновании! :)

UPD: Опубликовали разбор. Удачного дорешивания! :)

Поздравляю победителей официального зачета:

1. kuticpcer
2. SevenDawns
3. Clix
4. iamgqr
5. rishant_m

а также победителей неофициального:

1. jiangly
2. dorijanlendvaj
3. vepifanov
4. krijgertje
5. darkkcyan

Спасибо всем за то что приняли участие. Желаю приятного дорешивания!

Всем привет!

Сегодня на Codeforces появилась поддержка трансляций (стримов)! Спасибо Геннадию tourist Короткевичу за отличную идею!

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

Идея состоит в том, чтобы стримеры могли анонсировать свои трансляции на аудиторию Codeforces. Для этого трансляцию нужно добавить на сайт, используя специальный раздел в профиле. Обратите внимание, что при добавлении Twitch-трансляции вам надо указать просто URL вашего канала, а при добавлении YouTube-трансляции — её уникальную короткую ссылку (ссылку на видео youtu.be/…).

Незадолго до старта трансляции в сайдбаре справа появится уведомление о предстоящей трансляции, которое будут видеть все посетители сайта.

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

Например, прямо сейчас в русскоязычном интерфейсе есть анонс лекции Павла pashka Маврина в рамках его занятий в ИТМО по теме "игры на графах".

Мы встроили просмотр трансляций прямо в интерфейс Codeforces. Чат YouTube-трансляции оказалось встроить непросто, пока такой возможности нет. Для трансляций Twitch чат будет виден на Codeforces.

В наших планах еще немного улучшить эту функциональность. Как вы думаете, какие улучшения были бы полезны? Действительно ли термин "Трансляция" на русском подходящий? Или следует использовать "Стрим"?

Привет! В Oct/20/2020 17:35 (Moscow time) начнётся Codeforces Round 677 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.

Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение.

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

• принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
• не иметь в рейтинге точку 1900 или выше.

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

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Дарье nooinenoojno Степановой, Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда. Также спасибо Артему Rox Плоткину и Дмитрию _overrated_ Умнову за обсуждение идей и тестирование раунда!

Удачи!

UPD: Спасибо infinitepro, nuipojaluista, MrReDoX и Peinot за тестирование раунда и отзывы о задачах!

UPD2: Разбор опубликован!

Hi Codeforces!

stefdasca, koala_bear00 and I are very excited to announce our first contest Codeforces Round #676, which will take place 18.10.2020 12:05 (Московское время). The round will be rated for participants with rating up to 2099.

The tasks were written by me with help from stefdasca and koala_bear00 and you have to help some of the authors' favorite musical artists to solve the problems they're faced with.

We hope we compiled a very interesting contest with memorable tasks :)

Special thanks to:

• antontrygubO_o for coordinating our round and pushing us to come up with more and more interesting tasks.

• dorijanlendvaj, kclee2172, Devil, thenymphsofdelphi, atharv, Stelutzu, RetiredPlayer, shashwatchan, stack_overflows, AmShZ, Osama_Alkhodairy, raresdanut, katsurap_, A_N_D_Y, Usu and kpw29 for testing the round and providing useful feedback.

• MikeMirzayanov for awesome Codeforces and Polygon platforms. Thanks!

You will be given 2 hours to solve 5 problems, good luck everyone and have fun!

UPD 1: After the round you can watch videos explaining the solutions to the tasks on stefdasca's Youtube channel.

UPD 2: The round was rescheduled, because of intersection with other scheduled contests.

UPD 3: The scoring distribution is standard 500 — 1000 — 1500 — 2000 — 2500.

UPD 4: The editorial was posted and you can check stefdasca's video solutions aswell.

UPD 5: The round is finished, we are glad everything went smooth and hope you enjoyed our tasks!

Div1 winners (unofficial):

1. I_love_Tanya_Romanova
2. LJC00118
3. 244mhq
4. LayCurse
5. uwi

Div2 winners:

1. RGB_ICPC2
2. _ztyqwq
3. AnakMbah1937
4. SakuraiMomoka
5. rin204

Congratulations to those above and to everyone for participating!

Привет, Codeforces!

Присоединяйтесь к объединенному Div1 и Div2 раунду Codeforces Raif Round 1 (Div. 1 + Div. 2), который будет проходить при поддержке Райффайзенбанка и начнётся в 17.10.2020 16:05 (Московское время). Он будет рейтинговым и открытым для обоих дивизионов. Обратите внимание на нестандартное время начала раунда.

Все задачи были придуманы и подготовлены bensonlzl, oolimry, errorgorn, dvdg6566, shenxy13.

Спасибо:

• isaf27 и KAN за коодинацию раунда и помощь в подготовке

• zhangguangxuan99 за то, что он лучший IOI тренер <3

• Армии наших тестеров: Ari, KAN, Monogon, prabowo, SYY, shashwatchan, TeaTime, Tlatoani, -rs-, agul, cstuart, dantoh, jhkoh, kai824, kymmykym, lperovskaya, mango_lassi, morzer, Retired_cherry, socho, zhangguangxuan99, zscoder за их советы и замечания.

• MikeMirzayanov за замечательные системы Codeforces и Polygon.

Вам будет дано 8 задач, одна из которых будет разделена на простую и сложную версии, и 150 минут на их решение.

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

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

Спасибо компании Райффайзенбанк за подарки участникам:

Призы для победителей:

• 1-3 место = Беспроводная колонка

• 4-10 место = Поясная Сумка

• 11-20 место = Power bank

Случайные 50 участников, не вошедшие в топ-20, но решившие хотя бы одну задачу, получат:

• Термокружки

• Футболки от Райффайзенбанка

Несколько слов от команды алготрейдинга Райффайзенбанка:

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

Вы сможете:

• поработать с задачами в таких областях как JIT-компиляция, устройство современных CPU;

• поучаствовать в разработке высоконагруженных распределённых систем;

• оптимизировать скорость исполнения кода и архитектуру платформы;

• реализовывать низкоуровневые структуры данных и алгоритмы.

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

UPD: Разбалловка: 500 — 1000 — 1000 — 1500 — 1750 — 1750 — (2250+750) — 4000

UPD: Разбор!

Всем привет!

18 октября 2020 года в 11:00 состоится первая командная интернет-олимпиада для школьников. Приглашаем вас принять в ней участие!

Продолжительность олимпиады — 5 часов. Не забудьте зарегистрироваться на цикл командных интернет-олимпиад в этом сезоне перед началом олимпиады. Обратите внимание, что для участия в командных олимпиадах, нужно зарегистрировать команду (по ссылке "Новая команда"). Команда может содержать от 1 до 3 человек. Дополнительную информацию, а также расписание всех предстоящих командных интернет-олимпиад можно посмотреть на страничке интернет-олимпиад.

Условия появятся на сайте в момент начала олимпиады. Тестирующая система находится по адресу pcms.itmo.ru.

Олимпиаду для вас подготовили Николай Будин (budalnik), Михаил Иванов (orz), Михаил Анопренко (manoprenko), Даниил Орешников (doreshnikov), Дмитрий Гнатюк (ima_ima_go), Ильдар Загретдинов (SemBarner22).

Для связи с жюри можно использовать адрес электронной почты [email protected].

Удачи!

Привет, Codeforces!

В Oct/11/2020 12:05 (Moscow time) состоится Educational Codeforces Round 96 (Rated for Div. 2). Обратите внимание на необычное время старта раунда.

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев и Александр fcspartakm Фролов. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Удачи в раунде! Успешных решений!

UPD: Разбор можно найти здесь.

Поздравляем победителей:

Поздравляем лучших взломщиков:

Суммарно было сделано 858 успешных взломов и 2258 неудачных!

И, наконец, участники, получившие вердикт "Полное решение" первыми:

Hi!

On Oct/10/2020 17:50 (Moscow time) we will host Codeforces Global Round 11.

This is the fifth round of the 2020 series of Codeforces Global Rounds. The rounds are open and rated for everybody.

The prizes for this round are as follows:

• 30 best participants get a t-shirt.
• 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2020:

• In each round top-100 participants get points according to the table.
• The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
• The best 20 participants over all series get sweatshirts and place certificates.

Thanks to XTX, which in 2020 supported the global rounds initiative!

Problems for this round are set by me. Thanks a lot to the coordinator antontrygubO_o, to the testers dacin21, Giada, H4ckOm, DimmyT, Retired_cherry, oolimry, nkamzabek, Prakash11, Tlatoani, coderz189, nvmdava, stack_overflows, dorijanlendvaj, and to MikeMirzayanov for the Codeforces and Polygon platforms.

The round will have 8 problems and will last 180 minutes.

The (unusual) scoring distribution is: 500-750-1000-1000-1500-2250-2250-4500.

I hope you will have fun solving the problems!

UPD: The round is postponed by 15 minutes because just before the round there will be a 10-minutes-long unrated testing round. Considering the recent Codeforces downtime, this is a measure to make sure that there will not be technical issues during the real round.

UPD2: There were no technical issues during the testing round, hence the real round will happen. Good luck and see you in the scoreboard!

UPD3: I hope you liked the problems, here is the editorial.

UPD4: Congratulations to the winners!

1. Benq
2. yosupo
3. ksun48
4. Um_nik
5. ecnerwala
6. sunset
7. maroonrk
8. zscoder
9. SirShokoladina
10. gamegame

UPD5: And congratulation to Petr who upsolved H before the editorial was posted! You made me happy!

Hello, Codeforces!

Hope you're all safe and well.

Microsoft Development Center Serbia is thrilled to announce the finals of the 13th edition of Bubble Cup competition! Bubble Cup is an international, ACM-style team contest aimed at university and high school students.

Contest will take place on Sunday, 4th of October at 11AM CEST, virtually. Live results will be available on the official Bubble Cup website (results will be frozen during the last 45 minutes of the competition). Winners will be announced at the closing ceremony. You can find more info on the BubbleCup website.

Just like the previous editions, this final will be followed by an online mirror competition on Codeforces. Mirror will take place on Monday, 5th of October at 15:05 CEST. Contest will last for 3 hours and ACM ICPC rules will be applied. It will be a competition for teams of 1-3 members. There will be at least eight problems.

Just like last year, the finals are divided in two "divisions", called Premier League and Rising Stars. The two contests will have most of their problems in common, but the Rising Stars competition will feature some easier tasks targeted at high school contestants.

Both of the contests will be mirrored here on Codeforces, with Premier League mapping to the Div1 contest and Rising Stars mapping to the Div2 contest. The mirror will use native Codeforces ACM-ICPC team contest rules.

We kindly ask participants of the virtual finals to hold off discussing problems publicly until the mirror is over.

Contest was mainly prepared by employees of MDCS with help from our alumni member Lazar Milenković (milenkoviclazar). We give our thanks to Nikolay Kalinin (KAN) for the round coordination, Mike Mirzayanov (MikeMirzayanov) and the team behind Codeforces and Polygon platforms. Special thanks goes to Alexandr Lyashko (knightL) for helping out with problem testing.

The contest will be unrated. The reason for this is because rules of this contest are not common for Codeforces.

Editorial will be available in the booklets section on the Bubble Cup website sometime after the online mirror ends.

You can find problems from previous finals on our Codeforces online mirror competitions:

Bubble Cup 8 — Finals [Online Mirror]

Bubble Cup 9 — Finals [Online Mirror]

Bubble Cup X — Finals [Online Mirror]

Bubble Cup 11 — Finals [Online Mirror, Div. 1]

Bubble Cup 11 — Finals [Online Mirror, Div. 2]

Bubble Cup 12 — Finals [Online Mirror, Div. 1]

Bubble Cup 12 — Finals [Online Mirror, Div. 2]

We wish you best of luck in competition!

Update #1: Given the current situation we want everyone to be safe and enjoy the Bubble Cup finals from their home and that's why team members will be allowed to work on different machines.

Update #2: Congratulations to the winners!

Div1:

1. Omatase-Trinity: hos.lyric, maroonrk, yosupo
2. Almost Retired Dandelion: Merkurev, Um_nik
3. times187: Cyanic, ix35, s_r_f
4. tourist
5. Itst两小时阿克离场: newbiegcz, Itst, pupiI

Div2:

1. 2-sad walk: Dart-Xeyter, tem_shett, sevlll777
2. TeamSeven: liit_mixer, sachin208, jnarutoj
3. Fast but not Furious: amirmohammad-nezami, armin.atarod, ymmparsa
4. （￣ー￣）: noneTP
5. heh: Eyed, penguinhacker, el_heffeh

Preliminarily version of the editorial can be found here. Full version of the booklet will be published at a later time.