Hello Codeforces,

Manthan, Codefest'18 will take place on Sep/02/2018 17:35 (Moscow time) with a duration of 2 hours (tentative). The round is rated for both Div1 and Div2 participants and will consist of 8 problems.

The Department of Computer Science and Engineering, IIT (BHU) is conducting Codefest from 31st August-2nd September. Manthan (मंथन in Hindi, meaning Brainstorming), the algorithmic programming contest under the banner of Codefest, is being held as a special Codeforces round. The round follows regular Codeforces rules.

The round has been prepared by hitman623, karansiwach360, GT_18, Ezio07, Enigma27, csgocsgo and me (dhirajfx3). Special thanks to TooDumbToWin and DeshiBasara for their contribution in the preparation of the round.

We express our heartiest thanks to KAN, vintage_Vlad_Makeev, 300iq, isaf27 and cdkrot for their help in preparing the contest and MikeMirzayanov for the awesome Codeforces and Polygon platforms!

Prizes

Overall 1st place: INR 25000, Overall 2nd place: INR 18000, Overall 3rd place: INR 12000

1st place in India: INR 10,000

1st place in IIT(BHU) Varanasi: INR 4,000 1st place in freshman/sophomore year, IIT(BHU) Varanasi: INR 1,000

About Codefest: Codefest is the annual coding festival of the Department of Computer Science and Engineering, IIT (BHU) Varanasi, which is held online and is open to participation by all! Register on the Codefest website now! Total prizes worth ₹500,000/- up for grabs with events covering domains from Math, Machine Learning, Natural Language Processing and Capture The Flag style competitions. Go to the Codefest website to find out more!

As usual, the scoring distribution will be announced just before the round.

UPD1: Scoring 500-750-1000-1500-2250-3000-3500-4000

UPD2: Following are the winners of the contest

1. tourist

2. DearMargaret

3. LHiC

Best in India

amit_swami

Good luck and have fun!

UPD3: Link to editorial

Hello, codeforces!

It's time to continue the series of Polish tasks. I've decided to write about my own task one more time. Its name is "cook" (you can submit here). The task isn't very hard, but it uses cute (in my opinion) trick. The statement goes as follows:

There is a cook in a restaurant. He has n (1 ≤ n ≤ 10⁶) orders which he must fill. Every order is a piece of paper, and all orders are speared on a spindle (sharp stick with pierced pieces of paper) in a fixed order which cannot be changed. Normal cook would just take orders one by one from the top of the spindle and fill them in this order, but the cook in this task has supernatural cooking powers and can combine orders to fill them faster. In particular, if at some moment there are k out of n orders still on the spindle, he can choose one of three options:

 —  He can take the topmost piece of paper and fill this order in time one(k).

 —  If k > 1, he can take two topmost pieces of paper and fill both orders in total time two(k).

 —  If k > 1, he can take topmost pieces of paper and fill these orders in total time half(k).

This task is interactive, so you should communicate with the library and ask it for values of one, two and half. You can ask as many times as you want and assume that the library works in negligible time, so your only limit is the time limit. Please, note, that when k = 2 functions one and half both fills only one order, but they might take different amounts of time. This same applies to other similar situations.

Also, the cook has an energy level, initially equal to e (0 ≤ e ≤ 10⁶). He likes preparing food without any tricks, so whenever he uses the first option his energy increases by one. However, his half combo tires him very much, thus each time when he chooses the third option his energy decreases by one. Cook's energy cannot drop below zero at any time. Of course, we are asked about the minimum amount of time in which cook can finish all orders. Final energy level doesn't matter.

Last thing: memory limit is unusual because it's equal to 8MB.

Привет, Codeforces!

В 27.08.2018 19:35 (Московское время) состоится AIM Tech Codeforces Round 5.

Раунд подготовили сотрудники компании AIM Tech: Kostroma, riadwaw, Edvard, yarrr, zemen, Errichto, malcolm, gchebanov, VadymKa и zeliboba.

Раунд пройдет во время Петрозаводских сборов, спонсором которых является наша компания.

Благодарим Михаила Мирзаянова (MikeMirzayanov) за замечательные платформы Polygon и Codeforces, и координатора задач Codeforces Николая Калинина (KAN) за помощь в подготовке раунда. Огромное спасибо Golovanov399, Arterm, winger за ценные замечания и прорешивание раунда!

Наша компания занимается алгоритмической торговлей на бирже, ключевыми понятиями для нас являются low latency и high frequency trading. Перед ребятами в нашей компании стоят разнообразные задачи: написание стратегий для торговли, оптимизация торговых систем для достижения минимально возможной скорости реакции на биржевые события, сохранение и обработка больших объемов исторических данных. Умение писать эффективный C++ код, алгоритмическое мышление и математическая интуиция очень полезны в нашей работе, поэтому большая часть наших сотрудников — олимпиадники по программированию и математике. У нас работает несколько финалистов ACM ICPC, три золотых медалиста и чемпион мира (и золотой медалист). В свободное от работы время мы участвуем в разных соревнованиях по программированию и не только, испытываем себя на прочность в походах и покоряем горные вершины.

Узнать о нас больше можно на сайте aimtech.com, в facebook и instagram. Можно отправить нам резюме через эту форму, даже если вы не участвуете в раунде.

Участникам совмещенного раунда будет предложено 8 задач и 2:15 на их решение.

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

Призы с 502 раунда в память о Leopoldo Taravilse будут разыграны в этом раунде.

Топ-25 получат 100$ каждый, 26-71 места получат по 50$ каждый.

Разбалловка 500-750-1250-2000-2500-3250-3250-3500

Всем удачи и высокого рейтинга!

Спасибо за участие, поздравляем победителей!

1. LHiC
2. jqdai0815
3. bmerry
4. Um_nik
5. Egor
6. Benq
7. tqyaaaaang
8. DearMargaret
9. Marcin_smu
10. Swistakk

Разбор

Краткий разбор от bmerry

Информация о получении призов и будет опубликованы позднее.

<copy-pasted-part>

Привет! В 24.08.2018 17:50 (Московское время) начнётся Codeforces Round 506 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Наверное, участникам из первого дивизиона они будут совсем не интересны, а для 1600-1899 покажутся простыми. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

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

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

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

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

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

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

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

Удачи!

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

</copy-pasted-part>

UPD1:

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

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

Всего было сделано 1217 успешных взломов и 926 неудачных взломов!

И. наконец, люди, отправившие первое полное решение по задаче:

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

NOTE : Knowledge of Binary Indexed Trees is a prerequisite.

Problem Statement

Assume we need to solve the following problem. We have an array, A of length N with only non-negative values. We want to perform the following operations on this array:

1. Update value at a given position

2. Compute prefix sum of A upto i, i ≤ N

3. Search for a prefix sum (something like a lower_bound in the prefix sums array of A)

С 6 по 13 ноября 2018 года студенты, нацеленные на победу в ICPC и региональных соревнованиях по спортивному программированию, приглашаются на сборы в МФТИ (г. Долгопрудный). Международный семинар по программированию в рамках мирового первенства будет проходить на английском языке, поэтому участвовать могут команды со всего мира.

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

Дивизион А – для опытных команд с серьезным уровнем подготовки, которые претендуют на выход в финал

Дивизион В – для участников, которые готовятся к участию в региональных соревнованиях.

Основным модератором контестов выступит Олег Христенко, координатор Открытого кубка им. Е.В. Панкратьева и главный редактор Snarknews. Учебную программу координируют Михаил Тихомиров и Глеб Евстропов.

Для тех, кто оплачивает участие заранее, действуют скидки. Граждане из стран Евразийского Экономического Союза (ЕАЭС) могут совершать платежи в рублях, а резиденты других стран — в американских долларах. В стоимость участия входит учебная программа, питание и проживание в кампусе МФТИ, а также программа досуга.

Стоимость (на 1 человека) до 21 сентября — 26.000 рублей (для резидентов ЕАЭС), $630 USD. Две команды могут получить возможность бесплатного участия — об этом подробнее на сайте.

Регистрируйтесь на Международный семинар по программированию и побеждайте!

Ждем вас и желаем удачи!

Hello, codeforces!

This time I've decided to choose a task from my own contest which took place last April and was known as the Grand Prix of Poland. If you want to write this contest virtually in the future, then consider not reading this blog. If you've participated in this contest and maybe even solved this task, then anyway I recommend reading it, cause this task has many very different solutions, each of them being very interesting (in my opinion). It's also a reason why this blog is longer than previous ones.

I'll write about task C "cutting tree" (not uploaded to the ejudge yet :/). The statement goes as follows:

You are given a tree with n vertices (1 ≤ n ≤ 2·10⁵). The task is to calculate f(k) for each integer k from the range [1, n] where f(k) is defined as the maximum number of connected components of size k which we can "cut off" from the tree. A connected component of size k is a set of k vertices such that it's possible to traverse in the tree between any pair of these vertices using only vertices from this set. Chosen components are not allowed to intersect, so each vertex must belong to at most one component.

#IjustWantContribution

It seems there isn't any blog about Berlekamp-Massey Algorithm around here, so I decided to go on a try. :P

Acknowledgement: Hats off to matthew99 for introducing this algorithm.

What is 'linear recurrence'?

Assuming there is a (probably infinity) sequence a₀, a₁...a_n - 1, we call this sequence satisfies a linear recurrence relation p₁, p₂...p_m, iff . (Obviously, if m ≥ n any p can do :P)

How to calculate k-th term of a linear recurrence?

For a polynomial , we define .

Obviously G satisfies G(f) ± G(g) = G(f ± g).

Because , if we let , then G(f) = 0. Also G(fx), G(fx²)... = 0. So G(fg) = 0 (g is any polynomial).

What we want is G(x^k). Because G(f⌊ x^k / f⌋) = 0, then .

Привет.

В 19.08.2018 16:35 (Московское время), состоится общий рейтинговый раунд Codeforces Round #505. Этот раунд идет в паре с раундом #504.

Часть задач взята с Финала VK Cup 2018 (ashmelev, Errichto, Lewin), часть придумана мной. Спасибо моим товарищам — Диме (cdkrot), который, кстати, является координатором этого раунда, Коле (KAN), который позвал меня его проводить, а также Грише (vintage_Vlad_Makeev) и Ильдару (300iq) за то, что они просто клевые.

Также спасибо Майку MikeMirzayanov за множественные баг-фиксы и замечательный Codeforces!

Задач будет семь со следующей разбалловкой:
500 — 1000 — 1500 — 1750 — 2250 — 2750 — 3500

UPD. Систесты окончены. Разбор

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

1. Swistakk
2. DearMargaret
3. Kostroma
4. Benq
5. AwD
6. xumingkuan
7. webmaster
8. TLE
9. Egor
10. kriii

Так же, как и в прошлом раунде, по инициативе компании ВКонтакте будут разыграны очки GP30.

Участники сортируются по очкам за оба тура (если участник не участвовал в одном из туров, очки, набранные за него, полагаются равными нулю); при равенстве очков как тай-брейк используется максимальное за оба тура время, прошедшее от начала тура до последней посылки, прошедшей претесты.

Напоминаю, что лучшие 10 по сумме очков GP30 получат фирменного плюшевого персика.

Надеюсь, что вам понравится. Удачи!

Привет, Codeforces!

В такой замечательный день недели, как Aug/18/2018 17:35 (Moscow time) состоится Educational Codeforces Round 49.

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

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

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

Задачи вместе со мной придумывали и готовили Владимир vovuh Петров, Адилбек adedalic Далабаев, Иван BledDest Андросов и Михаил MikeMirzayanov Мирзаянов.

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

А вот сообщение от наших друзей из Harbour.Space:

Hi Codeforces!

Our Hello Barcelona Programming Bootcamp will be kicking off next month from Sept 26 — Oct 4, and we’d love to see you there!

The boot camp will once again feature the all-time greats Mike MikeMirzayanov Mirzayanov, Andrey andrewzta Stankevich, Michael Endagorion Tikhomirov, Gleb GlebsHP Evstropov, Artem VArtem Vasilyev, Ivan ifsmirnov Smirnov and other world renowned Russian coaches to train the participants.

You will be competing and learning side by side with some of the greatest teams in the world, while learning from the best coaches the ICPC has to offer.

Be sure to register before September 1st so everyone has time to get visas if needed, and of course for the Early Bird Discount of 5% or the Loyalty Discount* of 20% off registration for the boot camp!

*The loyalty discount is offered to universities and individual participants that took part in Hello Barcelona Bootcamps and Moscow Workshops ICPC.

Learn more about Barcelona ICPC Bootcamp

You can ask any questions by email: [email protected]

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

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

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

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