Hi all!

The main phase of Codeforces Marathon Round 2 has ended. In the preliminary standings, contestants Rafbill and hakomo have got very close results, at the same time getting far enough from the next group of contestants. Will they manage to maintain the lead after the final testing, and who will come out on top? We will know in a few hours.

For now, I encourage the contestants to share their solution ideas in the comments below, or in separate posts.

<copy-pasted-part>

Hello!

Codeforces Round 501 (Div. 3) will start at Jul/31/2018 17:35 (Moscow time). You will be offered 6 or 7 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 or 7 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 awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

</copy-pasted-part>

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

UPD1: Editorial is published.

UPD2:

Congratulations to the winners:

Congratulations to the best hackers:

604 successful hacks and 446 unsuccessful hacks were made in total!

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

Hello everybody!

On July 28 and 30 will take place tours of EJOI — individual programming competition for juniors, held under the rules of the International Olympiad in Informatics.

EJOI consists of the most interesting and hard problems that are proposed by a wide community of authors, and that is why we decided to give you an opportunity to crack the complete problemset of the contest. During the second tour of Olympiad, we are going to conduct a rated Codeforces round based on problems of both days of our Olympiad.

We kindly ask all the community members that are going to participate in the competition to show sportsmanship by not trying to cheat in any manner, in particular, by trying to figure out problem statements from the onsite participants. If you end up knowing some of the problems of EJOI (by participating in it, from some of the onsite contestants or in any other way), please do not participate in the round. We also ask onsite contestants to not discuss problems in public. Failure to comply with any of the rules above may result in a disqualification.

The round will happen at Jul/30/2018 11:15 (Moscow time) and will last for 2.5 hours. There will be 6 problems in each division.

The tasks of the round were invented and prepared by tourist, PavelKunyavskiy, niyaznigmatul, 300iq, GlebsHP, pashka, qoo2p5, VArtem, demon1999, Flyrise, ifsmirnov, isaf27, yeputons, cdkrot.

Also thanks for testing never_giveup, vintage_Vlad_Makeev, izban, GoToCoding, Egor, doreshnikov, Sert, disa, wrg0ababd, craborac, budalnik.

And, of course, thanks to MikeMirzayanov for great systems Codeforces and Polygon.

Good luck everybody!

UPD: Congratulations to winners!

D1:

1) Um_nik

2) LHiC

3) dacin21

4) ksun48

5) Swistakk

D2:

1) UnproductiveGuy

2) WaldarDoppen

3) IHaveHir

4) cly_none

5) Shadi.Gh

Hi all!

This post is inspired by a question here which asks yosupo how using the D progamming language compares to using C++. I regularly use D where possible in contests (and problemsetting) since 2014, with some success (for example, a program in D brought me victory in AZsPCs: Alphabet City). So I'd like to share my experience. I'll try to focus on stuff which is important in competitive programming.

The general feeling is as follows. You can write in D as in plain C when you need full control. You can also write more like in Python using the powerful standard library. However, D is a compiled language, so in both cases, the performance is similar to C++. Additionally, when the program is written, it is much easier to debug than a similar program in C++.

For an example, let us look at two solutions of a recent problem.

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 (cdkrot).

Also thanks to:

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

• Ivan Safonov (isaf27), Andrew Rayskiy (GreenGrape), Egor Gorbachev (peltorator), Grigory Reznikov (vintage_Vlad_Makeev), Costin-Andrei Oncescu (geniucos), Yuhao Du (jqdai0815), Ziqian Zhong (TLE), 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. molamola.

3. Benq

4. Petr

5. scott_wu

Div.2:

1. mayaohua2003

2. SqwrIwy

3. _yesname

4. llgyc

5. Sakits_tjm

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.

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://mirror.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.

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 awoo Piklyaev, Maksim Neon 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.