Mail.Ru Group совместно с МФТИ, МГТУ им. Н. Э. Баумана и Codeforces в четвертый раз запускает «Технокубок» — олимпиаду по программированию для школьников. В прошлом учебном году олимпиада вошла в перечень олимпиад школьников, повысив свой уровень до второго — круг учебных заведений, дающих льготы победителям и призерам, значительно расширился. Лучшие участники получат ценные призы от компании Apple.

Сразиться за звание самого талантливого молодого программиста приглашаются учащиеся средних образовательных учреждений 8-11 классов.

Победители и призеры олимпиады будут определены по результатам очного этапа, который будет проведен 3 марта 2019 года на базе МФТИ, МГТУ им. Н.Э.Баумана, а также на других региональных площадках по всей России, о которых будет сообщено позднее.

Привет, Codeforces!

В 17.09.2018 11:05 (Московское время) состоится Codeforces Round 510 (Div. 2) для участников из второго дивизиона (участников с рейтингом до 2100). Участники первого дивизиона традиционно могут участвовать вне конкурса.

Раунд будет рейтинговый для участников второго дивизиона (с рейтингом менее 2100). Условия будут доступны как на русском, так и на английском языках.

Этот раунд проводится по задачам школьного этапа Всероссийской олимпиады школьников по информатике 2018/2019 года г. Саратова. Задачи для вас готовили awoo, fcspartakm, Neon, BledDest, Roms и vovuh. Огромное спасибо нашему координатору cdkrot за помощь в подготовке раунда! Также спасибо тестерам DavidDenisov, PrianishnikovaRina, Decibit и Vshining.

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

UPD: Разбалловка 500-1000-1500-2000-2250-2750.

UPD2: Разбор

Привет, Codeforces!

В 16.09.2018 13:35 (Московское время) состоится Codeforces Round #509 для участников из второго дивизиона. Участникам раунда будет предложено 6 задач и 2 часа на их решение. Обратите внимание на необычное время начала раунда.

Раунд будет рейтинговый для участников второго дивизиона (с рейтингом менее 2100). Условия будут доступны как на русском, так и на английском языках.

Раунд начнется через 2 часа после начала квалификационного этапа и закончится с ним в одно и тоже время. Поэтому мы просим участников квалификационного этапа не распространять задачи до начала раунда. К сожалению, все задачи не поместятся в стандартный Div. 2 раунд, поэтому мы выбрали шесть из них.

Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Иван BledDest Андросов и Александр fcspartakm Фролов.

Благодарим MikeMirzayanov за возможность провести зеркало квалификационного этапа и за платформы Codeforces и Polygon, Антона arsijo Цыпко за помощь в подготовке раунда, а также IlyaLos, Perforator, kuviman, HolkinPV, MaxZubec, stanislav.bezkorovainyi, Karasick за тестирование.

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

UPD: Разбалловка: 500-1000-1500-2000-2500-3000

UPD2: Разбор

В этом году (сезон 2018-2019) второй раз Четвертьфинал ICPC Южного подрегиона NEERC будет содержать дополнительный квалификационный этап. Опыт прошлого года показал, что проводя квалификацию, мы даем возможность большему количеству команд попробовать себя в соревнованиях по программированию. Дата проведения — 16 сентября 2018 г. До 10 сентября необходимо зарегистрировать команду на сайте https://icpc.sgu.ru.

Приглашаются команды студентов/магистрантов/аспирантов из Астраханской, Белгородской, Волгоградской, Воронежской, Курской, Липецкой, Нижегородской, Пензенской, Ростовской, Самарской, Саратовской, Тамбовской, Ульяновской областей, Краснодарского, Ставропольского краёв, республик Адыгея, Дагестан, Кабардино-Балкария, Калмыкия, Карачаево-Черкесия, Чечня, Марий Эл, Мордовия, Северная Осетия, Татарстан, Чувашия. Команды должны состоять из трёх студентов/магистрантов/аспирантов (ниже смотрите формальные требования), представляющих один вуз. Участие в квалификационном этапе бесплатное. Оргвзнос не предусмотрен.

Этап будет одновременно проведен на нескольких площадках в ряде городов Южного подрегиона NEERC. Продолжительность квалификационного этапа 4 часа, язык условий — русский. Будет доступен перевод условий на английский язык.

Hello, codeforces!

Because after Round #507 sad men in suits visited me in my flat, this time I won't write about any task from the future. Instead, this blog will be about my own trick. I said "my own," but probably some of you have already heard about it or even figured it out, but I've developed it by myself, so I consider it as my own.

In particular, it's GEOMETRY TIME!!!. But please, don't escape already. I also don't like this topic so much, that's why I really like this trick. Let me tell you a story from one onsite Polish contest, which took place a few months ago. I was thinking about one of the problems, and I've figured out that I had to do some binary-search (on doubles) and then check if a set of half-planes has a non-empty intersection. The answer would tell me in which direction should I turn in the binary search.

Firstly, I grabbed my head, because I've never written an intersection of half-planes. I had my acm library with Errichto's codes inside, but my knowledge in usage of his part was limited to copy-pasting FFT and Rho-Pollard. Not only I, but also Swistakk figured out the thing about binary search and was trying to intersect half-planes normally, but he failed (we still aren't sure why, probably because of precision issues). Then, I reminded myself a task from eliminations to BubbleCup 2017 (you can find it here), which I solved with the mentioned trick.

Привет, Codeforces!

В такой замечательный день недели, как 07.09.2018 17:35 (Московское время) состоится Educational Codeforces Round 50.

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

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

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

Задачи вместе со мной придумывали и готовили Владимир vovuh Петров, Роман Roms Глазов, Иван BledDest Андросов и Максим Neon Мещеряков.

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

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

Hi Codeforces!

We are excited to announce our Work & Study Programme, geared towards diving into the worlds of Computer Science, Data Science, and Robotics, while kick starting a fulfilling paid internship with one of our industrial partners!

Required Education:

Degree in Robotics or Computer, Electrical, Mechanical Engineering or related disciplines

Qualifications and skills:

• Hands-on robotic programming
• Ideally experience within the automotive manufacturing sector
• Knowledge understanding of robot control interface with ancillary equipment
• Use of robot simulation packages
• Deep experience with all things robotic, from infrastructure-free autonomy, to ROS, computer vision, and machine learning
• Experience working with robot parts and components, developing robotics devices
• Ability to concurrently manage multiple diverse and often complex issues and / or projects at the nexus of software, sensors, and hardware

If you are interested in this opportunity, APPLY HERE!

Should you be selected, we will invite you to a series of interviews with admissions, and our industrial partners.

Our programmes are both fundamental and practical. Upon joining, you start working with professionals from admired technology, design and communications companies. You will have strong technical and academic support, alongside industrial experience. This is a unique opportunity to benefit from both worlds of education and industry, in one of the most innovative cities Western Europe has to offer.

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

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

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

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

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.