Please put to main page. So we won't see blogs like https://codeforces.com/blog/entry/70236 in the nearest future.

In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.

Hope you remember it and will never make such a stupid mistake!

Hello everyone,

At May 19 there was an annual programming contest in Samara University, and yet again we copy it into Codeforces Gyms. The gym contest takes place on Saturday, May 25, at 10:00 MSK.

Contest link
Virtual participation link

Fourth time in a row it is a personal contest. So we ask everyone to participate solo. The contest is the most interesting for blue and violet coders.

Hi,

I was allowed to upload two contests from Petrozavodsk camps, Yandex Cups 2018 and 2019, into Codeforces Gyms:

• 2018 Petrozavodsk Winter Camp, Yandex Cup
• 2019 Petrozavodsk Winter Camp, Yandex Cup

These contests are mostly authored by Zlobober and ifsmirnov, with the help of some other people. Yandex Cup 2018 has more easier problems and less hard problems.

The 2018 one is also known as Grand Prix of Khamovniki (discussion on CF), the 2019 one was never published before.

Enjoy!

Please vote: https://github.com/Codeforces/polygon-issue-tracking/issues/312

@MikeMirzayanov

Hello!
I want to solve different contests to learn a new language (Kotlin), but I have a busy shedule (and cannot write regular contests in suitable time), so the only way for me is to train using virtual contests.
There is a great variety of contests on Codeforces (thanks to Mike!) and consequently it is not easy to decide which contests to solve.
I love random, but I have a better idea. Let's make the list of not anime-themed contests! But I need your help (in comments) to find them all...

Hello everyone,

At March 11 there was an annual programming contest in Samara University, and yet again we copy it into Codeforces Gyms. The gym contest takes place on Sunday, March 18, at 11:00 MSK.

Third time in a row it is a personal contest. So we ask everyone to participate solo. The contest is the most interesting for blue and violet coders.

And as usual,

Qualification Round has ended, but no blog on Codeforces yet. What happened to my Codeforces?

Main page: https://hashcode.withgoogle.com/

Judge system: https://hashcodejudge.withgoogle.com/

Our points: 10 / 176877 / 15824126 / 11808094 / 21465945, total score 49275052, 55th place.

How did you solve all the subtasks? I'm most interested in C and D.

Some weeks ago I read a Quora answer by I_love_Tanya_Romanova (link). The 4th paragraph attracted me, here is it's short content:

There are jokes about these typical problem statements: “Little Rohit got an array as a birthday present”. I’m also not getting why these trashy statements should be writtten instead of formal model of the task. It is awesome to have fictional statement when it makes sense, or when it comes from real life; it is at least funny to have stuff like problems I mentioned above. And I know that some of the platforms I mentioned are requiring problems with fictional statements and say that formal models are bad. Well, OK, “Parents asked little Chandan to perform following operations…”. May I go to some other site and solve normal problems, please? That’s a matter of taste — but for me this kind of statements is something that makes strong negative impression, and I think I’m not the only one.

I also don't like statements where characters were added just because there were no characters originally. You read such statement and think: "Why do they added this Alice with her birthday present? It has nothing to do with the problem".

I think there must be some rules that authors should use when they write a problem statement:

1. If the problem comes from real life or from some situation that may appear in real life / fiction book / computer game — use the original statement. Those who will solve this problem will be clearly understand what's going on.
2. If the problem originally had the formal statement (e.g. you have an array and you have to answer some queries, you have an array and you have to find a subarray with maximal xor / and / or, and so on): use formal statement.
3. Never introduce a setting if the problem originally had formal statement.

I've just met a comment with a link to a problem statement. There was such text in the statement:

Soon the professor realized that reconstructing Anatoly’s code and the test tree from his output was not a simple task and that the result might be ambiguous. You will have to help her find all possible reconstructions of Anatoly’s code.

Don't you see something weird here? I think it should be:

Soon the professor realized that reconstructing Anatoly’s code and the test tree from his output was not a simple task and that the result might be ambiguous. You will have to help him find all possible reconstructions of Anatoly’s code.

or:

Soon the professor realized that reconstructing Anatoly’s code and the test tree from his output was not a simple task and that the result might be ambiguous. You will have to help them find all possible reconstructions of Anatoly’s code.

I know that people either use the gender that is more common for a person, e.g. he for drivers and she for nurses, or just use they (my English teacher said they is correct). I've wandered across Wikipedia (here is one of the links: https://en.wikipedia.org/wiki/English_personal_pronouns#Use_of_he.2C_she_and_it), but haven't found anything about preferrable usage of female pronouns.

However, I've read really a lot of English statements, and everywhere the female pronouns are used! For children and professors, for drivers and miners, for rabbits and foxes, for everything and everyone. Why?

Hello everyone,

Some days ago there was an annual programming contest in Samara University, and yet again we copy it into Codeforces Gyms. The gym contest takes place on Saturday, 8 April, at 9:30 MSK. Site clist.by says that there are no intersections with something important that day.

Second time in a row it is a personal contest. So we ask everyone to participate solo. It must be very interesting for yellow and lower guys, and, who knows, maybe for reds too. You can start virtual participation at any time.

And as usual,

Hello,

Another contest from Samara reached Codeforces Gyms. It will be held on Saturday, November 5, at 10:00 MSK. Please don't participate if you know the problems.

And as usual,

Hello everyone,

Some days ago we had an annual programming contest in Samara, and yet again we copy it into Codeforces Gyms. The gym contest takes place on Sunday, 17 April, at 11:00 MSK. Site clist.by says that there are no intersections with something important that day.

Previously, it was a team contest, but this year we decided to make it personal. So we ask everyone to participate solo. This is how the results will be the most adequate.

And as usual,

Hi all!

On September 13, a qualification contest for ACM ICPC was held in Samara SAU. We always put our contests to Codeforces Gyms, so this Saturday, November 14, 11.00 MSK everyone will be able to enjoy it.

The contest will be held at Codeforces Gyms, it will be unrated and will last for 5 hours. The problems were prepared by craus and Shlakoblock.

And here is the full list of our previous contests:

• 2012, V Samara Regional Intercollegiate Programming Contest
• 2012, Samara SAU ACM ICPC Quarterfinal Qualification Contest
• 2013, VI Samara Regional Intercollegiate Programming Contest
• 2013, Samara SAU ACM ICPC Quarterfinal Qualification Contest
• 2014, VII Samara Regional Intercollegiate Programming Contest
• 2014, Samara SAU ACM ICPC Quarterfinal Qualification Contest
• 2015, VIII Samara Regional Intercollegiate Programming Contest

What's going on here? This contest was held two years ago. Just look at its id: it is 100187. Someone has managed to change its start date (and also to make it invisible for everyone but the author, which is fixed now), but how is it possible? Any permission settings? What if I go and reschedule all the contests in the gym? What if I hide them all? It must be a bug, admins, look into it, please.

P.S. Don't participate if you remember the problems.

UPD. Looks like gym vandals continue their work:

540A - Combination Lock

For every symbol we should determine how to rotate the disk. This can be done either by formula: min(abs(a[i] - b[i]), 10 - abs(a[i] - b[i])) or even by the two for cycles: in both directions.

540B - School Marks

First count the number of marks that are less than y. If there are more than such marks, we can't satisfy the second condition (about the median), and the answer is -1. Otherwise we can get exactly such number of y marks so that the total number of marks greater than or equal to y is at least (maybe it's already satisfied). This is the required action for satisfying the second condition.

Now, in order not to break the first condition, get the remaining marks as lower as possible — all ones — and check the sum of the marks. If it is greater than x, the answer is -1, otherwise the correct answer is found.

540C - Ice Cave

There are three cases here, though some of them can be merged.

1. If the start and finish cells are equal, let's count the intact neighbours of this cell. If there is one, move there and instantly move back — the answer is YES. Otherwise it's NO.
2. If the start and finish cells are neighbours, the solution depends on the type of the destination cell. If it's cracked, the answer is YES — we can just move there and fall down. Otherwise it must have at least one intact neighbour to get the positive answer — we can move to the finish cell, then to this intact neighbour, and then return to the finish cell.
3. In the general case, check if the path from the start cell to the finish cell exists. If it doesn't, the answer is NO. Otherwise check the type of the destination cell. If it's cracked, it must have at least one intact neighbour, and if it's intact, it must have two intact neighbours.

540D - Bad Luck Island (my code: http://pastebin.com/3s6dRK3A)

Let's count the values dp[r][s][p] — the probability of the situation when r rocks, s scissors and p papers are alive. The initial probability is 1, and in order to calculate the others we should perform the transitions.

Imagine we have r rocks, s scissors and p papers. Let's find the probability of the rock killing scissors (the other probabilities are calculated in the same way). The total number of the possible pairs where one species kills the other one is rs + rp + sp, and the number of possible pairs (rock, scissors) is rs. As all meetings are equiprobable, the probability we want to find is . This is the probability with which we go the the state dp[r][s — 1][p], with the number of scissors less by one.

In the end, for example, to get the probability of the event that the rocks are alive, we should sum all values dp[i][0][0] for i from 1 to r (the same goes to the other species).

540E - Infinite Inversions (my code: http://pastebin.com/QFEMRbNP)

At first find the position of each element which is used in swap (using map). Now let's find the answer. It consists of the two parts. First part is the number of inversions formed by only whose elements which took part in the swaps. They can be counted by one of the standard ways: mergesort or Fenwick tree. The second part is the number of inversions formed by pairs of elements where one element has been swapped even once, and the other element stayed at his position. Let's consider the following test:

2
2 6
4 8

The global sequence will look as follows: [1 6 3 8 5 2 7 4 9 ...], and here is the array of swapped elements: [6 8 2 4].

Let's understand with which numbers the number 8 forms the inversions. The only elements that could do that are the elements between the initial position of the number 8 (where the number 4 is now) and its current position: [5 2 7]. There are two numbers on this segment which didn't take part in swaps: 5 and 7. The number 2 should not be counted as it took part in the swaps and we have already counted it in the first part of the solution.

So we should take the count of numbers between 8's indices in the global sequence (8 - 4 - 1 = 3) and subtract the count of numbers between its indices in the swaps array (4 - 2 - 1 = 1). We'll get the number of inversions formed by the element 8 and the elements which haven't moved at all, it's 2. Counting this value for all elements which have been swapped at least once, we get the second part of the answer. All operations in the second part of the solution can be performed using sorts and binary searches.

Hi all,

I was honored to open the fourth hundred of Codeforces Rounds. Unfornunately, neither I nor my friends couldn't invent any hard problems, so it's only a Div. 2 Round. But we'll definitely prepare a full round in the future! As always, I thank Zlobober for his help in preparing the problems, Delinur for English translations and MikeMirzayanov for the Codeforces itself.

The problems must be pretty easy for Div. 1 guys, so let's start a challenge: reds should solve everything in 30 minutes, yellows — in 1 hour, and violets — in 1 hour and a half. How many people will be able to make a success?

The score distribution will be standard. Wish you accepted solutions and successful hacks!

UPD 1. Congratulations to the winners in Div. 2:

1. PauGra
2. 233333333
3. tgehr

and in Div. 1:

1. niyaznigmatul
2. I_love_Tanya_Romanova
3. dreamoon

UPD 2. This is the editorial: /blog/entry/17643.

Hello guys,

I'm going to tell you about one of the negative aspects of Java on programming contests (actually, not only on contests), or, more precisely, how I have tried to resolve it. As you may know, Java has the disadvantage related to its collections library: the constraints of this language make you use object types even when using primitive types should be enough. Compare ArrayList<Integer> and vector<int>: Java list stores objects of type Integer, which are created every time when you add an element into the list (it's called boxing / unboxing), whereas C++ vector just stores ints. This behaviour slows down Java programs, and many people don't like it.

All this shit comes from the language design: you can't simply write a primitive type inside the angular brackets in Java. Some months ago I was thinking about this problem and came to the solution: why not just write my own collections library, with primitive types? Moreover, I haven't found any library with really all collections in the Internet.

That's how my small project EZ Collections (Github repository) was born. Of course, I haven't written all possible collections for all possible datatypes. Instead of that I have written each collection only once, leaving some hints for Maven plugin to generate everything as needed.

I have to say that this library is designed to use on programming contests or private purposes. It's thread-unsafe, it has some missing validations, it's prohibited to modify the collection during the iteration, it doesn't support serialization and maybe something else. But the problems on the contests can be solved without any troubles.

To use this library, you need:

1. Install Git and download the repository using git clone command (the URL is specified on the main page of the project). Or you can just download it using Download ZIP button.

2. Download Maven (link to the download page), install and configure it (if you don't know anything about it — use Google, but, as far as I remember, it's enough just to set the path to Maven in the system variables).

3. Enter the root directory of the library and execute command mvn clean install. After that two jar files will appear in your local Maven repository, and also in the target folder. One of these jars contains class files, and the other one — source files. Now you can use them in your Java project.

But it's still unclear how to use it on contests. You need Egor's plugin CHelper for IntelliJ IDEA. After it had moved to Github, it became possible to merge the pull request that fixes some problems. The last pre-built version (commit 29dc20b), which includes my pull request, can be downloaded from here and installed in IDEA on your own.

After plugin update you can include the library into your contest project, specifying the path to the jar file with sources. That's all!

This is the example: let's solve the problem 118E - Bertown roads

• use List<Integer>[] for storing the graph: 8293080 — 1060 ms, 39100 KB
• use EzIntList[] for storing the graph: 8293086 — 654 ms, 12148 KB

(this problem has quite large input, the larger it is, the more performance you gain)

One more example: solve the problem Timus 1521

With the TreeList's help the solution takes only a few lines:

int n = in.readInt();
int k = in.readInt();
EzIntList a = new EzIntTreeList(n);
for (int i = 0; i < n; i++) {
    a.add(i);
}
int idx = 0;
for (int i = 0; i < n; i++) {
    idx = (idx + k - 1) % a.size();
    out.print(a.removeAt(idx) + 1);
    out.print(' ');
}

What do we get using EZ Collections? For now, the following data structures are implemented:

• ArrayList
• ArrayDeque (with the possibility to get the element by its index)
• Heap
• Sort (guaranteed NlogN implementation)
• HashSet
• HashMap (I've used open addressing approach. I'm quite sure that it's not hackable)
• TreeSet
• TreeMap
• TreeList (the array that can perform add, set, insert and removeAt operations in logN time)
• Pair classes

Also I have to mention that there is famous Trove library (its repository can be found here) which has the similar idea, maybe some of you use it at work, but the problem is that only ArrayList, HashSet and HashMap are implemented in Trove. It's not enough for programming contests.

Some notes and plans:

• NaN, POSITIVE_INFINITY and other similar stuff is not supported. You know who you are, if you use such things.

• As it's impossible to return null (because EZ Collections store primitive types), method returnedNull() is added in every class where it's necessary. You must call it to perform null-check immediately after calling the method which could have returned null in usual Java Collections. For instance, these code fragments are identical:

    TreeSet<Integer> set = new TreeSet<Integer>();
    Integer lower = set.lower(42);
    if (lower == null) {
        ...
    }

    EzIntTreeSet set = new EzIntTreeSet();
    int lower = set.lower(42);
    if (set.returnedNull()) {
        // don't use the lower variable, it's not guaranteed that it has some certain value
    }

• The current source generation mechanism is ugly and doesn't support some cases that I want to support, so I'm planning to rewrite it. But all collections I wanted to implement in the first version already work.

• boolean is considered to be uncomparable type, so Pairs with booleans don't implement Comparable. It will be fixed after rewriting the source generation.

• Next collections I want to implement are LinkedList (on arrays). But it's only when I rewrite the source generation.

• The next planned thing is to implement maps which have primitive key and object value types, or vice versa. It also should speedup programs a bit.

Please write any suggestions and feedbacks using the private messages on Codeforces.

Version history:

• Feb 21, 2015 — version 0.1.0 is released. It contains the identical content comparing to standard Java collections library.
• Mar 15, 2015 — version 0.1.1 is released. TreeList was added. Also the possibility to specify custom hash functions for HashSet/HashMap was added.

Recently we ran another ACM ICPC quarterfinal qualification contest, whose results influenced the list of teams that will go to Saratov this autumn. The corresponding gym contest on Codeforces will be held on Sunday, Sep 21, 2014, at 11:00 AM.

Link to the contest: 2014, Samara SAU ACM ICPC Quarterfinal Qualification Contest

The list of our previous contests:

• 2012, V Samara Regional Intercollegiate Programming Contest
• 2012, Samara SAU ACM ICPC Quarterfinal Qualification Contest
• 2013, VI Samara Regional Intercollegiate Programming Contest
• 2013, Samara SAU ACM ICPC Quarterfinal Qualification Contest
• 2014, VII Samara Regional Intercollegiate Programming Contest