Приглашаю Вас поучаствовать в рейтинговом Codeforces Round #499. Дата и время проведения раунда: 26.07.2018 18:05 (Московское время).

В раунде Div.1 могут участвовать те, рейтинг которых не меньше, чем 1900. Остальные могут участвовать в раунде Div.2.

Не пропустите этот контест, ведь следующий Codeforces Round (Div.1, Div.2 или Div.3), номер которого начинается с цифры '4', будет через 3501 раунд!

Это первое соревнование, предложенное мной. Надеюсь, что оно Вам понравится.

На раунде будет по 6 задач для каждого дивизиона (4 задачи общие). Контест будет длиться 2 часа.

Главная героиня соревнования — космонавт Наташа, исследователь Марса. Если вы решите все задачи, её полёт пройдёт удачно.

Пять задач из контеста придумал я, Владислав Заводник (VladProg), задачи Div2.A и Div2.B придумал Михаил Мирзаянов (MikeMirzayanov), а задачу Div1.F придумали Ильдар Гайнуллин (300iq) и Дмитрий Саютин (cdkrot).

Также большое спасибо:

• Ильдару Гайнуллину (300iq), Дмитрию Саютину (cdkrot) и Михаилу Мирзаянову (MikeMirzayanov) за помощь в подготовке задач;

• Ивану Сафонову (isaf27), Андрею Райскому (GreenGrape), Егору Горбачеву (peltorator), Григорию Резникову (vintage_Vlad_Makeev), Costin-Andrei Oncescu (geniucos), Yuhao Du (jqdai0815), Ziqian Zhong (TLE), Андрею Халявину (halyavin) и Shuyi Yan (fateice) за тестирование раунда;

• Михаилу Мирзаянову (MikeMirzayanov) за платформы Codeforces и Polygon.

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

Желаю высокого рейтинга и жду Вас на соревновании!

UPD1

Обратите внимание: количество задач на раунде изменилось. На раунде будет по 6 задач для каждого дивизиона (4 задачи общие).

На раунде будет одна интерактивная задача для обоих дивизионов. Пожалуйста, прочитайте пост об этом здесь: Интерактивные задачи: руководство для участника.

UPD2. Разбалловка:

Div.2: 500, 1000, 1250, 1500, 2000, 2500

Div.1: 500, 750, 1000, 1500, 2250, 2750

UPD3. Соревнование окончено. Поздравляю победителей!

Div.1:

1. Kostroma

2. molamola.

3. Benq

4. Petr

5. scott_wu

Div.2:

1. mayaohua2003

2. SqwrIwy

3. _yesname

4. llgyc

5. Sakits_tjm

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

Всем привет!

Приглашаю вас поучаствовать в Codeforces Marathon Round 2. Это соревнование начнётся во вторник, 24 июля 2018 года в 15:00 MSK, и продлится 7 дней. В соревновании будет одна задача, основанная на механике пары детских настольных игр. Скорее всего, задача не имеет быстрого полного решения. Так что решения будут оцениваться баллами, и победит тот, кто наберёт больше всего баллов.

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

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

На Codeforces пока проведено не так уж много марафонов. Так что, если что-то сломается — не расстраивайтесь, а напишите об этом, мы постараемся всё исправить.

Успехов в соревновании!

Hello, Codeforces.

This is a short blog to introduce you recent updates in Testlib and Polygon.

Testlib

Generate a Permutation

Now, you can easily generate a permutation with codes like this:

Function println

Now, you can easily print space-separated lines in a generator. A println uses cout, thus prefer faster method if you print huge data.

Some examples:

Here is the example of a generator to print a permutation:

#include "testlib.h"

using namespace std;

int main(int argc, char* argv[]) {
    registerGen(argc, argv, 1);
    
    int n = atoi(argv[1]);
    println(n);
    println(rnd.perm(n, 1));
}

Function readInts and similar

Just as a reminder. Use functions readInts/readLongs/readStrictDoubles or readTokens/readLines in a validator to read and validate a sequence of values. To read a size of an array and array itself, use:

int n = inf.readInt(1, 200000, "n");
inf.readEoln();
inf.readInts(n, 1, 1000000, "a");
inf.readEoln();
inf.readEof();

Polygon

Example Problems

I've introduced three example problems. Each Polygon user has READ-access to them. Please, use them as examples how to write a problem in Polygon. They are:

• example-a-plus-b: simple A+B problem
• example-almost-upper-bound: simple problem to illustrate non-standard checker (always consider to use readAnswer function like in the example), generators and stress tests
• example-interactive-binary-search: simple interactive problem on a binary search

Other Small Fixes

• Allow to upload files (for example, images) as a contest property/file to use them in the statements.ftl. File names should start with 'statements-'.
• API has been improved to support general description, general tutorial, tags, test groups and points.
• Show problem ID on the summary box (on the righmost top block).
• Replace UTF-8 typographic characters to their ASCII equivalent (for example, replace em dash — with ---).
• Caching issue has been fixed. Previously, it could show RJ on tests even if the reason has been fixed.

Thanks to fcspartakm for implementing most features in Polygon.

TL;DR

The Policy Hash Table has 3-6x faster insertion/deletion and 4-10x increase for writes/reads. As far as I can tell, there are no downsides. The policy hash table (specifically the open-addressing version), beats out unordered_map in all my benchmarks.

PS: Make sure you read the section a better hash function and use it — I'd recommend this one: https://github.com/kth-competitive-programming/kactl/blob/master/content/data-structures/HashMap.h

Background

I've often been irritated by how slow unordered_map is in C++. Too often, I have something that runs fast enough in terms of complexity, but the constant factor from unordered_map slows down the solution too much. Yesterday though, after using the useful order statistics tree from https://codeforces.com/blog/entry/11080, I was curious if there were any other useful data structures hiding in the Policy STL. And lo and behold, I found a hash table.

Benchmarks

Well, enough backstory, let's look at some numbers. All benchmarks below are compiled with C++14 -O2.

unordered_maplinear insertion:                                  0.689846
cc_hash_tablelinear insertion:                                  0.408233
gp_hash_tablelinear insertion:                                  0.256131

unordered_maplinear read/write:                                 1.69783
cc_hash_tablelinear read/write:                                 0.202474
gp_hash_tablelinear read/write:                                 0.26842

unordered_maprandom insertion:                                  2.90184
cc_hash_tablerandom insertion:                                  3.15129
gp_hash_tablerandom insertion:                                  0.56553

unordered_maprandom read/write:                                 2.02336
cc_hash_tablerandom read/write:                                 0.333415
gp_hash_tablerandom read/write:                                 0.403486

While for linear insertions, the policy hash table gives modest improvements, the policy hash table blows the unordered_map out of the water when it comes to reads/writes. These are order of magnitude improvements that make hash tables usable when they previously weren't. "Official" benchmarks done by the DS authors can also be found here

Example

Benchmarks of course, don't always reflect the real world. So here's an example of it allowing a solution to be accepted that TLE's with unordered_map.

Example problem (5000 ms time limit)
Solution with unordered_map: (TLE on test case 8)
Solution with policy hash table directly substituted in: (TLE on test case 26)
Solution with unordered_map, rewritten to not use clears: (TLE on test case 26)
Solution with policy hash table and rewritten to not use clears: (AC with max time of 3180 ms)

Usage

To use this data structure:

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
gp_hash_table<int, int> table;

From there, the API seems almost exactly the same.

Defeating Anti-Hash tests

One weakness of hash tables is that mean people can find hash collisions offline and blow up the complexity of your hashmap. In my opinion, the easiest way of solving this is below. There's no need to define your own custom hash function.

const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    int operator()(int x) const { return x ^ RANDOM; }
};
gp_hash_table<key, int, chash> table;

Why is it so much faster?

See my comment here

A better hash function

There is one issue with using policy hash tables as is. The default hash function for numerics in C++ is just the identity. This is especially problematic for using hash tables for something like a fenwick tree, especially since the default bucket structure for policy_hash_tables is based of powers of 2 and not primes. If you're using policy hash tables for fenwick trees, you have 2 options. 1. Choose to use prime table sizes, as done here. 2. Choose a better hash function for integers, as done here.

Thanks to adamant for his post that revealed to me the existence of policy data structures, and thanks to ed1d1a8d for the discussion.

PS: In other posts for unordered_map, I've seen people claim that reserve and max_load_factor could increase performance drastically. They didn't seem to do much for me. However, if you want to do something similar for these hash tables, check out the example here

Code for the benchmarks can be found here

EDIT: I realized that gp_hash_table is the way to go, not cc_hash_table. gp_hash_table sacrifices ~10% reading/writing speed to gain 3-6x in insertion/deletion/clearing. I updated the post to reflect the new numbers.

Привет!

Окончательно освободившись от большей части летних забот, я снова могу приступить к подготовке Div. 3 раундов! Я решил добавить в этот блог что-то от себя, потому что TryToKnowMe (и, думаю, многие другие) заметили, что я правда копирую эту запись от раунда к раунду, меняя лишь название соревнования и дату проведения. Но кто знает, может, экономя время на написании анонса, я успеваю лучше подготовить задачи к раунду?... Пусть это останется тайной. А теперь приступим.

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

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

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

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

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

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

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

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

Удачи!

UPD: Также большое спасибо тестерам uwi, mareksom и ivan100sic за неоценимую помощь в подготовке раунда!

UPD2: Таблица результатов!

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

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

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

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

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

Привет, Codeforces!

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

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

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

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

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

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

Также есть сообщение от наших партнеров, Harbour.Space University:

Hi Codeforces!

We want to remind everyone that the Hello Barcelona Programming Bootcamp is right around the corner, and we’d love to see you there!

Our 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.

We would also like to extend a welcome to some of the newest teams to join us from Colorado School of Mines, University of British Columbia and Reykjavík University.

Be sure to register before August 1st so everyone has time to get visas if needed, and of course for the Early Bird Discount of 15% 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: Разбор опубликован

Всем привет!

Мы дэт-метал группа Skyglow, недавно у нас вышел первый альбом. И поскольку мы по совместительству являмся спортивными программистами, мы решили провести в честь этого раунд на Codeforces!

Раунд состоится в Jul/13/2018 17:35 (Moscow time). В каждом дивизионе будет по пять задач, три из них будут совпадать. Задачи составлены мной и rembocoder, также контест помогали подготовить TeaPot, slavik, mingaleg и niyaznigmatul. Благодарим demon1999 и winger за прорешивание, нашего координатора arsijo и, конечно, MikeMirzayanov за предоставление площадок Codeforces и Polygon.

Послушать альбом можно по ссылке:

• https://skyglow.bandcamp.com/album/thousand-years-of-terror

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

• https://vk.com/skyglowband?w=wall-134984483_323
• https://www.facebook.com/skyglowband/posts/2100310513570956

Всем участникам контеста, изъявившим желание, мы подарим альбом на CD диске. (Если таких окажется много, то мы выберем из них нескольких лучших по результату раунда). Обращайтесь ко мне в личные сообщения.

Удачи на контесте!

UPD1. мы подарим наш альбом на CD диске лучшим 10 участникам, которые хотели бы его получить. Чтобы поучаствовать в розыгрыше, напишите мне личное сообщение до контеста с вашим адресом, индексом и полным именем.

UPD2. Разбаловка выглядит следующим образом:
Div2: 500-1000-1500-2000-2500
Div1: 500-1000-1500-2250-2500

UPD3. Мы всё ещё думаем, нужно ли делать раунд рейтинговым или нет. Вы можете поделиться своим мнением в блоге Майка.

UPD4. Мы решили отсортировать пользователей по изменению рейтинга, так что следующие участники получат диск:
riela, +332
DongwonShin, +278
Erdenebayar, +176
DOlaBMOon, +148
Muhimin_Osim, +121
ciphereck, +117
Dotiros, +104
luismo, +94
MaxZubec, +72
whybee, +70

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

Div1:

1. yosupo
2. Egor
3. fateice
4. Um_nik
5. ksun48
6. wxh010910
7. zemen
8. shpsi
9. mareksom
10. mmaxio

Div2:

1. riela
2. Kato_Megumi
3. luis.trivelatto
4. yukuai26
5. _D41_
6. gls1196
7. TaoSama
8. chenyuqi0215
9. DearMargaret
10. Rena_Takeda

UPD6. Опубликован разбор!

Hello!

This time decided to fill myself in the shoes of the problem writers. It is very exciting! My challenge was to prepare a round in one day. It's really incredible pleasure to surrender to my passion and all day just work on problems!

Despite the fact that in total I've wrote 8 problems, I made it in time. Initially, I prepared 7 problems, but two of them were found to be used before (thank you, 300iq and cdkrot for poining it) and I removed them and wrote a new problem.

Codeforces Round 496 (Div. 3) will start on 09.07.2018 18:35 (Московское время). You will be offered 6 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the Div. 1 not be at all interested by this problems. And for 1600-1899 the problems will be quite easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 problems and 2 hours to solve them.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Many thanks to the testers: kevinsogo, 300iq, cdkrot, arsijo and adedalic. You really helped to make this round!

Good luck!

UPD 1: The round is over. Thank you for participation!

Official Top-5 (trusted only)

• poteryan_i_ne_naiden
• num2
• qaweqa
• HCMUS-Thanos
• tantam75

Unofficial Top-5 (+ untrusted)

• BigBag
• kmjp
• quailty
• TangentDay
• Aeon

UPD 2: The editorial is available by the link.

Microsoft's Quantum Team and Codeforces are excited to invite you to Microsoft Q# Coding Contest — Summer 2018!

The contest will run from July 6 — 9 and will consist of increasingly challenging tasks on introductory topics in quantum computing: superposition, measurement, oracles and simple algorithms. The top 50 ranked participants will receive a Microsoft Quantum T-shirt!

As a reminder, last weekend we help a warmup round with easier tasks which covered the same topics. The results were quite impressive: 167 participants solved all tasks! You can see the tasks here, and the solutions with explanations here.

Several useful reminders:

• The contest is unrated.
• Solutions are accepted in Q# only.
• Participants are ranked according to the number of correctly solved tasks, with penalty time as a tiebreaker.
• The tasks are grouped by topic, and the tasks within one topic are ordered in approximate order of increasing difficulty. If you find a problem too hard, don't forget to check the next problems in this topic and problems from different topics, they might turn out to be easier.
• Unlike the warmup round, you're not allowed to discuss the tasks during the contest.
• By popular demand, we have added Custom Invocation to allow you to run Q# code on Codeforces servers. Here is the signature of the code you should use to run it (note that the namespace and operation name have to match this code exactly):

namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;

    // ------------- Operation which is called from C# -------------------
    operation RunQsharp () : Bool
    {
        body
        {
            Message("Hi");
            return true;
        }
    }
}

• For tasks which require you to create a certain quantum state or to implement a unitary transformation, any kind of error gives verdict "Wrong Answer". For tasks which have classical return, I tried to differentiate verdicts "Wrong Answer" (your return value was incorrect) and "Runtime Error" (array index out of bounds, qubits released are not in zero state, oracle called too many times etc.).
• NO PURCHASE NECESSARY. Must be 16 years of age or older. Game ends 7/9/18. For details, see Official Rules.

You can find the discussion of the warmup round and pointers to Q#/quantum computing materials here.

For first time Codeforces users:

1. Create user account here.
2. Register for the contest here.
3. Once the contest starts on July 6, access the problems here.

Good luck! We hope you enjoy the contest!

Update. The contest is over. Editorials are published.

Всем привет!

Лето... Прекрасная пора для поездок на отдых, прогулок с друзьями, новых открытий и, конечно же, написания новых увлекательных контестов на Codeforces. Поэтому, я предлагаю к вашему вниманию мой новый Codeforces Round #495 (Div. 2) с интересными задачами и не менее интересными разборами, который состоится в 05.07.2018 19:35 (Московское время). Если ваш рейтинг меньше 2100, этот раунд будет для вас рейтинговым, иначе — вы можете участвовать вне конкурса.

Хочу поблагодарить Михаила MikeMirzayanov Мирзаянова за помощь в подготовке и за системы Codeforces и Polygon. Также Ильдара 300iq Гайнуллина, Дмитрия cdkrot Саютина, Даниила danya.smelskiy Смельского, Chin-Chia eddy1021 Hsu и Kevin ksun48 Sun за тестирование задач.

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

В этом раунде вам предстоит помочь девочке Соне с ее ежедневными проблемами. Удачи вам в этом!

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

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