Всем привет!

Мы рады сообщить вам о том, что с 7 по 16 ноября 2017 года пройдут тренировочные сборы Moscow International Workshop ACM ICPC. Это отличная возможность для ребят, которые не только хотят серьезно подготовиться к следующему сезону ACM ICPC 2017/18, но также попутешествовать и пообщаться с талантливыми программистами со всего мира. Весной в Долгопрудный приехали 28 иностранных команд, и мы надеемся побить этот рекорд осенью! :)

Сборы проводятся в Долгопрудном на базе кампуса МФТИ при поддержке Университета ИТМО, СПбГУ и МГУ.

Программу готовят Михаил Тихомиров Endagorion, Глеб Евстропов GlebsHP и, конечно же, наш бессменный Олег Snark Христенко, главный редактор Snarknews и сооснователь Open Cup.

У нас есть хорошая новость для тех, кто не может надолго пропускать учебные занятия в университете: можно выбрать сокращенную программу с 9 по 16 ноября. А еще мы готовим пару нововведении, но о них сообщим чуть позже.

Подробнее о сборах и о стоимости участия можно прочитать здесь! Имейте в виду, что регистрация обязательна, и анкету нужно заполнить до 1-го ноября!

На сегодняшний день у вас есть месяц для того, чтобы попасть на сборы по сниженной стоимости: оплата до 16 сентября составит 27.000 рублей для граждан стран Евразийского Экономического Союза (ЕАЭС) и $550 для остальных участников. Эта цена включает в себя учебную программу, проживание и питание в кампусе МФТИ, а также спорт и развлечения.

Самые трудолюбивые команды могут написать свой контест и принять участие в сборах бесплатно!

А пока вы думаете, ехать или нет, вы можете посмотреть фотографии или видео с весенних сборов в Долгопрудном:

• Мы ВК:https://vk.com/acmmipt
• Мы ФБ:https://www.facebook.com/MoscowACM/
• Мы в Instagram: https://www.instagram.com/acmmipt/

Всем привет!

Приглашаю вас принять участие в Codeforces Round #429, который начнётся 18 августа в 18:05 по московскому времени.

Задачи для вас готовили Фёдор Mediocrity Коробейников, и Владислав totsamyzed Мосько. Большое спасибо Алексею netman Вистяжу за помощь в подготовке раунда, Александру AlexFetisov Фетисову и Владиславу winger Исенбаеву за тестирование задач, Михаилу MikeMirzayanov Мирзаянову за системы Codeforces и Polygon.

Участникам обоих дивизионов будет предложено по пять задач и 2 часа на их решение. Разбалловка будет объявлена ближе к началу раунда.

Надеемся, раунд вам понравится! Всем удачи!

UPD: Разбалловка: 500 — 1000 — 1500 — 2000 — 2500. Обратите внимание, что количество задач изменилось с 6 до 5.. А также большое спасибо Алексею Um_nik Данилюку за тестирование задач.

UPD: Раунд завершён. Просим прощения за все произошедшие неудобства. Поздравляем победителей:

Div1:

1. anta

2. LHiC

3. Radewoosh

4. dreamoon_love_AA

5. ikatanic

Div2:

1. emengdeath2020

2. Svlad_Cjelli

3. denis2111

4. Ehsan22

5. zjt_ioi_2019_ak

UPD: Разбор

I always was dreaming that one day competitive programming will become a real sport, not just activity for a small group of participants. Why? Because I don't really like working and my tries to do some science were totally unsuccessful. It would be cool to live just by doing what you like. Very childish, I know.

But this blog is not about if competitive programming is important or are there any ways to make it interesting to watch to wider audience. I am just trying to understand, is it currently moving toward real sport or away from it? And I get some mixed signals about that:

Bad signals:

• Big onsites (like GCJ or TCO) seem to cut the number of participants and the amount of prizes.

• Some onsite-finals are turning to online-finals. For example, several years ago we had Russian Code Cup onsite in Russia, currently RCC Finals is online.

• Some big companies are turning away from sport programming (IBM is stopping sponsorship of ACM ICPC).

Good signals:

• Some new finals were created during last years. For example, VK Cup in Russia, SnackDown in India or Code Festival in Japan (for students).

• Some small firms are holding rounds and even created their own little onsite finals.

• Sports programming (not in the financial part) seems to thrive. For instance, there are new platforms for training that were created just in the last year: like atcoder (for international participants) or csacademy.

So, what future will you predict for a competitive programming? Will it become a real sport? Or will it forever be just for fun and for students to get to the interview in a big company?

This article will be presenting a rather classical problem that can be solved using deques, along with an extension that allows you to solve the problem in its more general multi-dimensional case. I have decided to write this article after this discussion on 2D range-minimum query.

The article will be mainly based on this following problem:

You are given an array of numbers A[] of size n and a number k ≤ n. Find the minimum value for each continuous subarray of size k.

We will be now focusing on the linear-time solution to this problem.

Solution:

Consider sweeping from left to right through the array. At every moment we keep a list of "candidates" for minimum values throughout the process. That means that at each moment, you have to add one element to the list and (potentially) remove one element from the list.

The key observation is that, during the sweep line process, we find two values A[i] and A[j] which have i < j and A[i] ≥ A[j], then we can safely discard A[i]. That is because, intuitively, A[j] will continue to "live" in our sweep line more than A[i], and we will never prefer A[i] instead of A[j].

We should now consider pruning all the "useless" values ("useless" as in the statement above). It is easy to see now that doing this will lead to a strictly increasing list of candidates (why?). In this case, the minimum will always be the first element (O(1) query).

In order to insert an element to the back of the pruned candidate list, we will do a stack-like approach of removing all elements that are greater than it, and to erase on element, we just pop the front of the list (if it is not already removed).

This is a well-known approach for finding minima over fixed-size continuous subarrays. I will now present an extensions that allows you to do the same trick in matrices and even multi-dimensional arrays.

The multi-dimensional extension

Problem (2D):

You are given an matrix of numbers A[][] of size n × m and two numbers k ≤ n, l ≤ m. Find the minimum value for each continuous submatrix of size k × l.

Solution:

Consider the matrix as a list of rows. For each row vector of A, use the 1D algorithm to compute the minimum value over all l-length subarrays, and store them in ColMin[][] (obviously, ColMin[][] is now a n × (m - l + 1)-sized matrix).

Now, consider the new matrix as a list of columns. For each column vector of ColMin, use the algorithm to compute the minimum value over all k-length subarrays, and store them in Ans[][] (of size (n - k + 1) × (m - l + 1)).

The Ans[][] is the solution to our problem.

The following picture shows the intutition behind how it works for computing Ans[1][1] for n = 5, m = 7, k = 3, l = 4

The pseudocode is as follows:

def solve_2d(M, k, l):
  column_minima = {} # empty list
  for each row in M.rows:
    # We suppose we have the algorithm that solves
    # the 1D problem
    min_row = solve_1d(row, l)
    column_minima.append_row(min_row)
  
  ans = {}
  for each col in column_minima.cols:
    min_col = solve_1d(col, k)
    ans.append_col(min_col)
  
  return ans

Note that the pseudocode is (deliberately) hiding some extra complexity of extracting rows / columns and adapting the 1D algorithm to the 2D problem, in order to make the understanding of the solution clearer.

The total complexity of the algorithm can be easily deduced to be O(n * m)

Multi-dimensional case analysis

The solution can be extended to an arbitrary order of dimensions. For a d-dimensional matrix of size s₁, s₂, ..., s_d, the time-complexity of the problem is O(d * s₁ * ... * s_d), and the memory complexity is O(s₁ * ... * s_d). This is much better than other algorithms that do the same thing on non-fixed size submatrices (e.g. multi-dimensional RMQ has O(s₁ * ... * s_d * log(s₁) * ... * log(s_d)) time and memory complexity).

Finding the best k minima

The deque approach itself is limited in the sense that it allows you to find only the minimum value over the ranges. But what happens if you want to calculate more that one minimum? We will discuss an approach that I used during a national ACM-style contest where we were able to calculate the best 2 minima, and then argue that you can extend to an arbitrary number of minimum values.

In order to store the lowest 2 values, we will do the following:

Keep 2 deques, namely D1 and D2. Do a similar algorithm of "stack-like popping" on D1 when you add a new element, but instead of discarding elements from D1 when popping, transfer them down to D2 and "stack-like pop" it.

It is easy to see why the lowest 2 elements will always be in one of the two deques. Moreover, there are only 2 cases for the lowest two elements: they are either the first two elements of D1, or the first elements of D1 and D2 subsequently. Checking the case should be an easy thing to do.

The extension to an arbitrary number of minima is, however, not so great, in the sense that the complexity of this approach becomes O(n * k²) for a n-sized array, currently bottlenecked by the number of elements you have to consider in order to find the first k minima. [Maybe you can come up with a cleverer way of doing that?]

Useful links

This is the problem I referred to above: http://www.infoarena.ro/problema/smax. I recommend trying to think it through and implementing it, and translating the statement via Google Translate or equivalent.

Hi everybody!

On Saturday, August 12, 2017, at 14:35 UTC Codeforces Round #428 will be held. As usual, Div.1 participants can join out of competition.

The problems are prepared by me(Sadegh Mahdavi) and NikaraBika(Majid GarooC). Great thanks to Arpa(AmirReza PoorAkhavan) and Livace(Alexey Ilyukhov) for testing the round, KAN(Nikolay Kalinin) for helping us preparing the round and MikeMirzayanov(Mike Mirzayanov) for the Codeforces and Polygon systems.

There will be 5 problems and 2 hours to solve. The scoring will be published later.

The main characters of this round are chosen from the game of thrones series :D

UPD : The scoring is : 500 — 1000 — 1500 — 2000 — 2500

UPD: The judges solutions for problem B incorrectly handled some case, so we are going to rejudge some of the hacks. The pretests are not affected, so the contest is going to be rated.

UPD : The round is finished. Congratulations to winners:

Div 2:

1.mama_budra

2.fatego

3.regmsif

4.Lyra

5.Illyasviel

Div 1:

1.dotorya

2.kmjp

3.I_love_Tanya_Romanova

4.Benq

5.Claris

UPD Editorial

On Sunday, August 6th, 22:00 IST, we will hold the 2nd elimination for IndiaHacks (some more details here). The top 900 individuals who qualified through previous rounds will have the opportunity to participate in this round. The top 25 global participants and top 25 Indian participants will advance to the final round. The link to the contest is here.

After the official round is over, the next morning, on Monday, August 7th, 11:35 IST, we'll hold an unofficial unrated mirror here on Codeforces. This mirror will have ICPC rules. For participants of the official round, please hold off on discussing the problems publicly until after this mirror is over.

I was the author of the problems in this set, and I hope you will enjoy the problems. I would like to thank zemen for testing the set, Arpa for writing editorials, r3gz3n for his help on the HackerEarth side, KAN for helping us set up the mirror contest, and of course MikeMirzayanov for the great Polygon/Codeforces platform.

The round will consist of 6 problems and you will have 3 hours to complete them. Please note that the problems will be randomly arranged in both rounds, since I couldn't figure out how to sort them by difficulty. Be sure to read all the problems.

UPD1: Updated time of official round and posted link to contest.

UPD2: We should have updated the leaderboard to accept solutions that followed the first version of the first problem. We have also increased the number of finalists to 60 total (30 global + 30 indian) based on this new leaderboard.

UPD3: Here is the list of qualifiers. Congratulations to everyone.

Привет, Codeforces!

3 августа в 18:05 по Москве начнётся Educational Codeforces Round 26.

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

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

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

Задачи вместе со мной придумывали и готовили Иван BledDest Андросов, Алексей Perforator Рипинен и Михаил MikeMirzayanov Мирзаянов.

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

Не упустите возможность попасть в список победителей финала ACM-ICPC, зарезервируйте себе место во втором Hello Barcelona Programming Bootcamp (в сотрудничестве с Moscow Workshops ACM-ICPC)!

Посмотрите на статистику достижений участников этих сборов на прошедшем финале — World Finals 2017 Results.

8 из 12 призёров финала 2017 года принимали участие в Moscow Workshops ACM-ICPC!

Вспомните, как проходили первые сборы "Hello Barcelona ACM-ICPC Bootcamp (в сотрудничестве с Moscow Workshops ACM-ICPC)". Студенты и тренеры со всего мира собрались там, чтобы учиться у ведущих программистов мира и работать с ними, наслаждаться солнцем Барселоны и стать частью дружного сообщества программистов. Harbour.Space University снова рады приветствовать всех на сборах, на этот раз в красивой и высокотехнологичной постройке Media-TIC.

UPD: Разбор доступен по ссылке

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

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

Было сделано 1361 успешных и 513 неудачных взломов.

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

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

Совсем текущее состояние: У Саши 63 место, у Егора 38 место, у Денис 27 место и у Вовы 19 место. Итого, три серебра и одно золото, причём, у Дениса самое первое серебро, что, конечно, очень обидно, но всё равно очень классно. Есть куда расти в следующем году!

Текущее состояние на момент конца тура: Тур длился 5:30, последние 25 минут табличка не обновлялась. За это время Саша успела улучшить результат по последней задаче до 50, чем, скорее всего, гарантировала себе серебро! Основная интрига для нас заключается в том, много ли участников оказались выше Дениса в итоге, или нет: до падения таблицы результатов Денис был на 24 месте, а золотых медалей, если мы ничего не путаем, 26.

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

05:21: Тур продлён на 30 минут (минимум). По неподтверждённой информации, у них возникли серьёзные проблемы с тестирующей системой. Таблица не обновляется.

05:05: Саша и Денис все ближе к границам, волнуемся. К тому же нет гарантии, что текущая таблица правильная.

05:02: Сообщают, что контест продлен, неизвестно, на сколько именно.

04:51: Саша успевает набрать 13 по simurgh и теперь более уверенно попадает в серебро.

04:49: В последние минут Егор пихает books, Денис что-то шлет по simurgh.

04:46: САША!!! Смогла 90 по prize! Граница серебра, но какой все же камбэк!

04:33: yutaka1999 300. voidmax добил books на 50, точно золото. Denisson опасно болтается на границе.

03:54: К нам вернулся интернет. voidmax тоже смог сдать simurgh на 51.

03:30: Тем временем, у xumingkuan 70 по simurgkh, это первый участник, кто справился с полным графом.

03:15: Egor.Lifar и Denisson продолжают слать books, demon1999 послала simurgh на 0.

03:10: наш прогноз на границы медалей: золото 350, серебро 250, бронза 170.

03:03: Denisson привез 50 по books! С хорошей вероятностью наше первое золото. Egor.Lifar преодолел ноль по этой же задаче.

02:52: voidmax все же смог набрать 12 по books.

02:49: Egor.Lifar пытается улучшить свои 51 по simurgh, voidmax пытается получить больше нуля по books (upd: Egor.Lifar тоже посылал books, и тоже на 0).

02:44: У arsijo теперь тоже 90+51+0 и пятое текущее место в общем зачете. С хорошей вероятностью это уже окончательное золото.

02:42: demon1999 за последний час несколько раз посылала prize, но все на 20. Переживаем.

02:37: То же самое сделал и kilt_01. Если все эти ребята соберут и очень популярные 50 по books, у всех с хорошей вероятностью уже будет не хуже серебра.

02:27: К клубу набравших присоединяется giraffeh и подбирается вплотную к границе золота.

02:21: То же самое делают и Arthur и Mediocrity.

02:19: Egor.Lifar тоже набирает 51 по simurgh. Пока участников с таким баллом меньше десяти, приятно, что двое из них из России. #interactivepride

02:14: Помимо трех русских участников в текущей зоне золота находится arsijo из Украины, благодаря отличному результату на первом туре. Довольно близки к границе MadNick из Казахстана, а также kefaa и gepardo из Беларуси.

02:03: Опасный Lukas Michel из Германии первым на этом туре решил две задачи (практически) полностью: books и prize.

01:57: demon1999 все-таки включилась в набирание баллов по prize, начала с простого бинпоиска за 20.

01:55: Egor.Lifar и voidmax перебрали все остовы и набрали 13 по simurgh.

01:42: У Denisson 51 по simurgh.

01:39: У американца, чудом приехавшего на IOI вместе с делегацией Китая, 90+, 51 и 50. Кажется, это ровно те баллы, для получения которых не надо придумать что-то нестандартное.

01:27: Участник из Германии получил первую сотню по books.

01:20: Chmel_Tolstiy замечает, что команда Таиланда занимает 91, 92, 94 и 95 места.

01:19: demon1999 решила набрать 12 баллов по books.

01:13: В топ-20 три участника из России, один из Украины и двое из Грузии.

01:03: А вот и voidmax ворвался с 97.42 по prize. Уже порядка двадцати участников имеют  ≥ 90 баллов, скорей всего, эти баллы будут необходимым условием для серебряной медали.

00:57: Egor.Lifar тоже быстро справился набрать все необходимые баллы по prize. Володя и Саша пока с нулями, ждем от них сразу хороших баллов.

00:40: У Denisson 94.9 баллов по prize, это очень хороший старт. Кроме него 90+ по prize у какого-то участника из Таиланда.

00:27: Появились 50 баллов по books и 13 баллов по simurgh от sancho. Denisson также заработал свои 20 баллов по prize.

00:09: Таблица результатов обновилась и в ней стали появляться первые участники с 20 баллами по первой задаче.

00:00: Соревнование началось по расписанию.

Всем привет!

Через полчаса начнётся второй тур международной олимпиады школьников. Вчера ребята посетили шестую по высоте башню мира Milad Tower; фотки с экскурсии, как обычно, можно увидеть в нашем телеграм-канале.

Мы с Михаилом Endagorion, как и позавчера, будем делиться мыслями по поводу происходящего на туре. Напомним, что по итогам первого тура 21 место (в официальном зачёте) занимает Владимир voidmax Романов, 28 место принаждлежит Денису Denisson Шпаковскому, на 37 месте расположился Егор Egor.Lifar Лифарь, и, наконец, на 54 месте находится Александра demon1999 Дроздова. Также отметим выдающийся результат украинского школьника Антона arsijo Ципко, занимающего на текущий момент 7 место.

Пожелаем всем участникам удачи!

Полезные ссылки (список будет пополняться):

• Обсуждение первого дня.
• Официальная таблица результатов.
• Таблица реузльтатов от неутомимого snarknews с множеством разной дополнительной интересной информации.
• Список всех участников IOI в соответствии с прекрасной базой данных
• Сайт IOI
• Пост от SeyedParsa, посвящённый IOI.
• Онлайн-трансляция на Яндекс.Контесте.

Всем привет!

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

Всем лучей добра!

Приглашаем вас поучаствовать в предстоящем 426-м раунде, который пройдет в это воскресенье в 17:35 по московскому времени. Если вы считаете, что раунд от фиолетового — это плохой знак, то спешим вас огорчить (или, наоборот, обрадовать): над раундом трудились сразу двое фиолетовых — я (xen) и GreenGrape!

Раунд будет проведен по классическим правилам Codeforces и будет включать в себя по пять задач для каждого из дивизионов, три из которых — общие. Длительность раунда — два часа. О разбалловке по давно сложившейся традиции мы сообщим лишь незадолго до начала раунда.

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

Тестировать задачи нам помогали Кирилл Seemann Симонов, Евгений rek Тушканов, Егор Voudy Спирин, Евгений WHITE2302 Белых, Владислав winger Исенбаев и Александр AlexFetisov Фетисов. Спасибо Артуру tunyash Рязанову за предложенные идеи по задачам, нашедшие отражение в нашем проблемсете. Огромное спасибо координатору Николаю KAN Калинину за то, что помог нам довести дело до конца (и терпел нас, пока мы кропотливо фиксили косяки), и, конечно же, Майку MikeMirzayanov Мирзаянову за замечательные платформы Codeforces и Polygon!

Будет ли раунд рейтинговым, спросите вы? Мы ответим, что сделали все возможное для этого, и не намерены отступать от плана :)

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

UPD. Разбалловка будет такой:
Div. 1: 500 – 1250 – 1500 – 2250 – 2500
Div. 2: 500 – 1000 – 1500 – 2250 – 2500

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

Div. 1:

1. Radewoosh
2. LHiC
3. VivaciousAubergine
4. SanSiroWaltz
5. W4yneb0t

Div. 2:

1. nguyenthibanh
2. ColdSu
3. LLX
4. EnjoyCallen
5. pr3pony

UPD 3. Разбор

art by Ilya Shapovalov