Hi Codeforces!

We want to remind everyone that the 3rd Hello Barcelona Programming Bootcamp, which is from Sept 26 — Oct 4, is right around the corner, and the teams are gathering from all over the world!

We, alongside world champions Moscow State University, gold medalists Moscow Institute of Physics Technology, University of Tokyo, and bronze medalist ITMO, would like to extend a warm welcome to some of the newest teams to join us from Nanjing University, Universidad de La Habana, Lund University, Reykjavik University, Colorado School of Mines, University of British Columbia and Vilnius Gediminas Technical University. The teams will be training side by side in preparation for the upcoming regionals, and 2019 World Finals — we’d love to see you there!

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. See you there!

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: hello@harbour.space

PREVIOUS BOOTCAMPS' PARTICIPANTS

I invite you to participate in the rated Codeforces Round #499. Date and time of the round: Jul/26/2018 18:05 (Moscow time).

Those whose rating is not less than 1900 can participate in the round Div.1. Other can participate in the round Div.2.

Do not skip this contest, because the next Codeforces Round (Div.1, Div.2, or Div.3), which number begins with the digit '4', will be through the 3501 rounds!

This is the first competition I proposed. I hope that you will enjoy it.

The round will have 6 problems for each division (4 problems are common). The contest will last for 2 hours.

The main heroine of the competition is astronaut Natasha, Mars researcher. If you solve all problems, her flight will pass successfully.

Five problems of the contest are invented by me, Vladislav Zavodnik (VladProg), problems Div2.A and Div2.B are invented by Mike Mirzayanov (MikeMirzayanov), and problem Div1.F is invented by Ildar Gainullin (300iq) and Dmitry Sayutin (_kun_).

Also thanks to:

• Ildar Gainullin (300iq), Dmitry Sayutin (_kun_), and Mike Mirzayanov (MikeMirzayanov) for help in preparing the problems;

• Ivan Safonov (isaf27), Andrew Rayskiy (GreenGrape), Egor Gorbachev (I_love_isaf27), Grigory Reznikov (gritukan), Costin-Andrei Oncescu (geniucos), Yuhao Du (OO0OOO00O0OOO0O00OOO0OO), Ziqian Zhong (fjzzq2002), Andrey Khalyavin (halyavin), and Shuyi Yan (fateice) for testing the round;

• Mike Mirzayanov (MikeMirzayanov) for Codeforces and Polygon platforms.

Scoring distribution will be announced later.

I wish you a high rating and I am looking forward to see you at the competition!

UPD1

Pay attention: count of problems at the round was changed. The round will have 6 problems for each division (4 problems are common).

The round will have one interactive problem for both divisions. Please, read the post about it here: Interactive Problems: Guide for Participants.

UPD2. Scoring distribution:

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

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

UPD3. The contest is over. Congratulations to the winners!

Div.1:

1. Kostroma

2. cki86201

3. Benq

4. Petr

5. scott_wu

Div.2:

1. mayaohua2003

2. SqwrIwy

3. _yesname

4. llgyc

5. Meple

UPD4. Editorial is published.

Hi all!

I invite you to take part in Codeforces Marathon Round 2. The contest will start on Tuesday, July 24, 2018 at 15:00 MSK, and will last for 7 days. There will be one problem based on game mechanics of a couple of board games for children. The problem most likely does not have a fast and full solution. So the solutions will be given scores, and the winner will be the one who gets the highest total score.

The contest will be unrated because the problem is considerably different from the problems of rated rounds.

During the time of the contest, the solutions will be checked on examples and preliminary tests. After the contest is over, the final solution of each contestant will be checked on the final test set, and the total score for this test set will determine the final scoreboard. The contest will take place on Codeforces platform and is supported by the Community Of Master Programming at St. Petersburg State University (link in Russian) and 90.01 Group.

The Codeforces platform has seen only few marathons so far. So, if something breaks, don't be upset, just write about it, and we will try to fix it.

Good luck in the contest!

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.

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) { return hash<int>{}(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.

Hello!

Finally I am freed from the big part of summer cares and I can continue the preparation of Div. 3 rounds! I decided to add something written by me to this blog because TryToKnowMe (and many others, i think) noticed that i am really copy and paste this text from one announcement to another changing only contest name and start time. But... Who knows, may be this time which is saved by copy-pasting the announcement allows me to prepare the problems better?... Let it stay a mystery. So, let's go.

Codeforces Round #498 (Div. 3) will start at Jul/16/2018 17:35 (Moscow time). 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 first division will not be at all interested by this problems. And for 1600-1899 the problems will be too 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.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

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.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

UPD: Also great thanks to the testers uwi, mareksom and ivan100sic for their invaluable help with the round preparation!

UPD2: Results table!

Congratulations to the winners:

Congratulations to the best hackers:

199 successful hacks and 232 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

UPD3: Editorial is published.

Hello Codeforces!

On Jul/14/2018 17:35 (Moscow time) Educational Codeforces Round 47 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extented ACM ICPC rules. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

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

The problems were invented and prepared by Ivan BledDest Androsov, Vladimir Vovuh Petrov, Maksim Ne0n25 Mescheryakov, Aslan ag2cidk Tamaev and me.

Good luck to all participants!

I also have a message from our partner, 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: hello@harbour.space

Congratulations to the winners:

Congratulations to the best hackers:

And finally people who were the first to solve each problem:

UPD: The editorial is posted

Hello, everyone!

We are a Death Metal band Skyglow. Recently we released our first album. And since we happen to be sport programmers, we decided to make a Codeforces round in honor of this!

The round will take place on Jul/13/2018 17:35 (Moscow time). There will be five problems for each division, three of them will coincide. The problems were made up by me and SirRembocodina, the contest was also prepared with the help of TeaPot, GrumpyKitten, mingaleg and niyaznigmatul. Thanks to demon1999 and winger for testing, our coordinator arsijo and, of course, MikeMirzayanov for Codeforces and Polygon platforms.

You can listen to the album by following the link:

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

It would be a great help if you repost us, even if you don't listen to this kind of music.

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

We will present an album on a CD to every contestant who expresses a wish. (If there are many of such, we will choose several of them with the best result in the round). Write me a private message.

Good luck on the contest!

UPD1. We will present an album on a CD to the top 10 contestants who would like to get one. Just send me a private message before the contest with your address, postal code and full name.

UPD2. Scoring distribution is as follows:
Div2: 500-1000-1500-2000-2500
Div1: 500-1000-1500-2250-2500

UPD3. We are still deciding if we should make this round rated or not. You can share your opinion about the round in the Mike's blog.

UPD4. We decided to sort the participants by the rating change. So the following users will receive a CD:
riela, +332
DongwonShin, +278
Erdenebayar, +176
DOlaBMOon, +148
Muhimin_Osim, +121
ciphereck, +117
Oliveira_medalha_de_ouro, +104
luismo, +94
zubec, +72
yagyanshbhatia, +70

UPD5. Congratulations to winners!

Div1:

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

Div2:

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

UPD6. The editorial was published!

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 _kun_ for poining it) and I removed them and wrote a new problem.

Codeforces Round #496 (Div. 3) will start on Jul/09/2018 18:35 (Moscow time). 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, _kun_, 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
• AKfun
• qaweqa
• sorry_dahaodl
• liv1n9

Unofficial Top-5 (+ untrusted)

• BigBag
• kmjp
• quailty
• TangentDay
• AeonHQ

UPD 2: The editorial is available by the link.