Hi everyone!

It has been almost 2 years since I joined Codeforces, and it has been a great journey as a contestant. I now try to take a shot at problem-setting with my friend Mahir83.

With that said, I bring to your attention my new Codeforces Round 508 (Div. 2) that will take place on Sep/06/2018 18:35 (Moscow time). If your rating is less than 2100, this round will be rated for you; otherwise, you can participate out of competition.

I would like to thank Mahir83 for his help with preparing problems, cdkrot & 300iq for coordinating my round and Um_nik, craborac, vintage_Vlad_Makeev, vovuh & BledDest for testing my problems. I would also like to thank MikeMirzayanov for Codeforces and Polygon platforms.

You will be given 6 problems and 2 hours to solve them. Scoring distribution will be announced later.

Good luck!

UPD: Scoring Distribution: 500-1000-1500-1750-2250-2750

UPD2: Editorial

Всем привет!

В эти дни в Москве проходит уже третья Международная олимпиада мегаполисов — международное соревнование для школьников из крупнейших городов и столиц мира, одной из дисциплин которого является информатика. Над турами по информатике имели удовольствие работать члены члены жюри, приглашённые из Санкт-Петербурга, Минска и Белграда, а также Московская методическая комиссия, известная вам по Московской командной олимпиаде, Открытой олимпиаде школьников по программированию и Московской олимпиаде для 6-9 классов (раунды 327, 342, 345, 376, 401, 433, 441, 466, 469).

В составе жюри олимпиады: darnley, Endagorion, Jelena Hadži-Purić, Елена Андреева, Zlobober, GlebsHP. Задачи олимпиады разрабатывали kraskevich, ch_egor, cdkrot, Schemtschik, GoToCoding, malcolm, akvasha, darnley, wrg0ababd, achulkov2, vintage_Vlad_Makeev под руководством GlebsHP и Zlobober.

Задачи адаптированы под codeforces KAN и cdkrot, спасибо MikeMirzayanov за системы codeforces и polygon, который использовался при подготове задач этой олимпиады. Также спасибо за тестирование LHiC и V--o_o--V!

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

Раунд состоится 05.09.2018 19:35 (Московское время) и будет идти два часа. В раунде будет 5 задач у каждого дивизиона.

P.s. Мы просим всех, кто участвует или знает задачи с основного соревнования, воздержаться от участия в раунде и публичного обсуждения задач, в противном случае вы можете быть дисквалифицированы.

Upd: Разбор был опубликован здесь!

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

Div1:

1. Um_nik
2. 300iq
3. webmaster
4. ksun48
5. Anadi

Div2:

1. GSHSIF
2. gosuto
3. Onjo
4. sturdyplum
5. LYJabc

Привет, Codeforces!

Фонд Виктора Шабурова Botan Investments возобновляет прием заявок на участие в грантовой программе в области Machine Learning. Все желающие могут оставлять заявки по ссылке. Прием заявок продлится до конца сентября.

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

В начале лета мы отобрали четыре команды из трех вузов (СПбГУ, УлГТУ и ОмГУ), которые уже получили первые инвестиции и сейчас активно работают над созданием прототипов. Ждем хороших результатов от остальных участников!

Условия программы остаются прежние:
- Нужно собрать минимум 6 человек (две команды) и проводить командные очные встречи как минимум два раза в неделю.
- Тренировки проводятся на Kaggle, мы будем следить за количеством контестов и успехами в них. При необходимости будем требовать ежемесячные отчеты по участию в соревнованиях, гипотезах по решению, реализованных подходах и полученных результатах.
- Если к январю 2019 г. студенты показывают хорошие результаты, то фонд готов выделить 3 миллиона рублей на создание прототипа коммерческого проекта
- Преподаватель получает долю в проекте и продолжает получать грант за организацию работы команд.
- Участвовать могут преподаватели российских вузов (кроме Москвы). Напоминаем, что преподаватель не должен являться студентом, он может быть сотрудником или аспирантом вуза
- Количество участников ограничено, поэтому мы оставляем за собой право отказать в участии в программе без объяснения причины.

Перспективы:
- Уникальная возможность стать основателем стартапа в области machine learning
- Мы поможем с регистрацией компании, юридической поддержкой и поиском первых клиентов
- После успешного запуска прототипа объем финансовой помощи будет увеличен

Также хочу напомнить о программах Botan Investments в области спортивного программирования:

- 10К для преподавателей
Программа нацелена на преподавателей региональных вузов, регулярно организующих для студентов тренировки по спортивному программированию на платформе Codeforces. Условия участия можно найти тут.

- 50К и поездка в Сочи для гроссмейстеров с Codeforces
Этот грант могут получить гроссмейстеры Codeforces, учащиеся в региональных вузах на 4 курсе или старше. Полные требования — по ссылке.

По всем вопросам, связанным с участием в наших программах, пишите на [email protected]. Будем рады видеть новых участников!

Don't use rand(). Why? Let's jump right into some code. What value will the following code print, approximately?

#include <cstdlib>
#include <iostream>
using namespace std;

const int ITERATIONS = 1e7;

int main() {
    double sum = 0;

    for (int i = 0; i < ITERATIONS; i++)
        sum += rand() % 1000000;

    cout << "Average value: " << sum / ITERATIONS << '\n';
}

Should be about 500,000, right? Turns out it depends on the compiler, and on Codeforces it prints 16382, which isn't even close. Try it out yourself.

What's happening here?

If you look up C++ documentation on rand(), you'll see that it returns "a pseudo-random integral value between 0 and RAND_MAX." Click again on RAND_MAX and you'll see that "This value is implementation dependent. It's guaranteed that this value is at least 32767." On the Codeforces machines, it turns out RAND_MAX is exactly 32767. That's so small!

It doesn't stop there though; random_shuffle() also uses rand(). Recall that in order to perform a random shuffle, we need to generate random indices up to n, the size of the array. But if rand() only goes up to 32767, what happens if we call random_shuffle() on an array with significantly more elements than that? Time for some more code. What would you expect the following code to print?

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int N = 3000000;

double average_distance(const vector<int> &permutation) {
    double distance_sum = 0;

    for (int i = 0; i < N; i++)
        distance_sum += abs(permutation[i] - i);

    return distance_sum / N;
}

int main() {
    vector<int> permutation(N);

    for (int i = 0; i < N; i++)
        permutation[i] = i;

    random_shuffle(permutation.begin(), permutation.end());
    cout << average_distance(permutation) << '\n';
}

This computes the average distance that each value moves in the random shuffle. If you work out a bit of math, you'll find that the answer on a perfectly random shuffle should be = 1,000,000. Even if you don't want to do the math, you can observe that the answer is between = 1,500,000, the average distance for index 0, and = 750,000, the average distance for index .

Well, once again the code above disappoints; it prints out 64463. Try it yourself. In other words, random_shuffle() moved each element a distance of 2% of the length of the array on average. Based on my testing, the implementation of random_shuffle() on Codeforces matches the following exactly:

    for (int i = 1; i < N; i++)
        swap(permutation[i], permutation[rand() % (i + 1)]);

So naturally if RAND_MAX is much less than N, this shuffle will be problematic.

rand() itself has more quality problems than just RAND_MAX being small though; it is typically implemented as a relatively simple linear congruential generator. On the Codeforces compiler, it looks like this:

static long holdrand = 1L;

void srand(unsigned int seed) {
  holdrand = (long) seed;
}

int rand() {
  return (((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
}

In particular, linear congruential generators (LCGs) suffer from extreme predictability in the lower bits. The k-th bit (starting from k = 0, the lowest bit) has a period of at most 2^k + 1 (i.e., how long until the sequence takes to repeat). So the lowest bit has a period of just 2, the second lowest a period of 4, etc. This is why the function above discards the lowest 16 bits, and the resulting output is at most 32767.

What's the solution?

Don't worry, as of C++11 there are much better random number generators available in C++. The only thing you need to remember is to use mt19937, included in the <random> header. This is a Mersenne Twister based on the prime 2¹⁹⁹³⁷ - 1, which also happens to be its period. It's a much higher-quality RNG than rand(), in addition to being much faster (389 ms to generate and add 10⁸ numbers from mt19937 in Custom Invocation, vs. 1170 ms for rand()). It also produces full 32-bit unsigned outputs between 0 and 2³² - 1 = 4294967295, rather than maxing out at a measly 32767.

To replace random_shuffle(), you can now call shuffle() and pass in your mt19937 as the third argument; the shuffle algorithm will use your provided generator for shuffling.

C++11 also gives you some nifty distributions. uniform_int_distribution gives you perfectly uniform numbers, without the bias of mod -- i.e., rand() % 10000 is more likely to give you a number between 0 and 999 than a number between 9000 and 9999, since 32767 is not a perfect multiple of 10000. There are many other fun distributions as well including normal_distribution and exponential_distribution.

To give you a more concrete idea, here's some code using several of the tools mentioned above. Note that the code seeds the random number generator using a high-precision clock. This is important for avoiding hacks specifically tailored to your code, since using a fixed seed means that anyone can determine what your RNG will output. For more details, see How randomized solutions can be hacked, and how to make your solution unhackable.

One last thing: if you want 64-bit random numbers, just use mt19937_64 instead.

#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
using namespace std;

const int N = 3000000;

double average_distance(const vector<int> &permutation) {
    double distance_sum = 0;

    for (int i = 0; i < N; i++)
        distance_sum += abs(permutation[i] - i);

    return distance_sum / N;
}

int main() {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    vector<int> permutation(N);

    for (int i = 0; i < N; i++)
        permutation[i] = i;

    shuffle(permutation.begin(), permutation.end(), rng);
    cout << average_distance(permutation) << '\n';

    for (int i = 0; i < N; i++)
        permutation[i] = i;

    for (int i = 1; i < N; i++)
        swap(permutation[i], permutation[uniform_int_distribution<int>(0, i)(rng)]);

    cout << average_distance(permutation) << '\n';
}

Both shuffles result in almost exactly 10⁶ average distance, like we originally expected.

Additional References

This post was inspired in part by Stephan T. Lavavej's talk "rand() Considered Harmful": https://channel9.msdn.com/Events/GoingNative/2013/rand-Considered-Harmful

If you want even faster, higher-quality random number generators, take a look at this site by Sebastiano Vigna.

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. EvenImage
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. Две команды могут получить возможность бесплатного участия — об этом подробнее на сайте.

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

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