Hi Codeforces!

My name is Maxim Gusarov and I joined the Codeforces developer team in September and am recently working with Vitaly kuviman Kudasov on improving the Polygon system.

Today I would like to introduce you to the new potential of the system where all problems for the Codeforces rounds and many other programming contests are prepared.

Update 1

As a user logs into the system, she can now use either the login or the email given at the registration. You can also attach the session to the IP address to enhance security.

Update 2

Any user who has the access to edit a problem can become its supervisor. The supervisor will always get email notifications about the changes committed to the problem even if they were committed as “Minor changes”. What you need to do is to open the problem, go to the “Manage Access” tab and set “Supervisor” after your name.

This option can be used for the problem author or the contest coordinator not to miss a single change.

Hello, Codeforces!

In late December and early January, I wrote a proof-of-concept of separate service in C ++, to take out heavy data from the Codeforces Java-code to C++. Long time I have not written in C ++, experienced a funny sense of immersion into another world.

I was surprised to find the lack of open-addressing hashmap in the C++ standard library, and indeed in the boost, and in other popular libraries. It is strange somehow, because often open addressing should be better than separate chaining both in time and memory. And since I intend to keep small objects, then sure.

I quickly sketched a prototype that actually shows that open addressing in 2-3 times faster than the standard std::unordered_map. Here's the output of the benchmark on my laptop:

std :: map takes 15779 ms
std :: unordered_map takes 4698 ms
oaht :: hash_map takes 1473 ms

I think that there is no good implementation of such container in stl-style with the support of C++11 (move semantics). Maybe someone will show, but I have not found.

Here is my prototype on github: https://github.com/MikeMirzayanov/open_addressing_hash_table Unfortunately, I'm not cool C ++ expert, and I have no time to implement.

On the other hand, on Codeforces where were many C ++- discussions, and seems there many users who understand modern C ++. Also algorithms are water and air of Codeforces!

Hello Codeforces!

evima, yosupo and I would like you to participate in Codeforces Round #286. It will be held on Sunday, January 18th at 16:00 MSK. Please note that this round starts on unusual time.

Great thanks to Zlobober who helped us prepare this round, Delinur who translated statements into Russian and MikeMirzayanov who created Codeforces and polygon.

This is the 3rd time(following #162 and #263) for me, and the 1st time for evima and yosupo to prepare a Codeforces Round.

Scores of the problems will be

500-1000-1750-1750-2500 for Div.1, and

500-1000-1500-2000-2750 for Div.2.

In this round, you'll help a man named Mr. kitayuta. I hope he will participate :)

The system tests are now over! The top-5 are as follows:

Div.1:

1.ilyakor

2.kcm1700

3.LayCurse

4.RomaWhite

5.TankEngineer

Div.2:

1.Konijntje

2.cpcpc

3.zgzjsxshycxksxhsh

4.Ronnie007

5.sha384

Also, special congrats on Petr, who solved problem E in Div.1, which anyone else could not solve.

Here are the editorials

Round 1 FHC starts in January, 17, at the 18.00 UTC.

Look this and other information here. The top 500 finishers will advance to Round 2, as well as contestant who gets the same number of points as the 500th contestant.

Round 1 will last 24 hours. This is not virtual contest, when you can choose moment when you start during these 24 hours, but 24-hour contest of full value. It is unusually decision. It is clearly that organizers wants all participants to find the convenient time to solve the problems. I hope the problemset we be completed such a way so how many times does participient can spend to solve the problems, 2 hours or 24, will not have a big impact to his result. Perhaps it is assumed that a certain set of problems will be solved by large number of participants, much more than 500, but very few people will be able to solve something else.

(I will glad to see the remarks about translation mistakes)

From 24 February to 6 March 2015, the Moscow Insitute for Physics and Technology will host the sixth Winter Computer Camp 2015 (WCC-2015) in the city of Dolgoprudny. Students of upper grades are welcome to participate.

The program of the camp includes::

• Daily studying contests: preparation to the finals of the Open Olympiad, finals of national programming Olympiads.

• Olympiads in programming and mathematics.

• Lectures by workers of base organizations of FIHT about actual tasks in the IT Industry.

• Lectures by professional scientists on combinatorial mathematics.

• Sports and intellectual games.

How to get to the school:

1. Fill in the registration form.
2. Participate in the online selection rounds for the camp. Pay attention that the selection is conducted thoroughly in compliance with the results of the selection rounds.

Online selection rounds*:

• 18.01.2015 10:00 мск — first round,

• 31.01.2015 15:00 мск — second round,

• 07.02.2015 15:00 мск — third round,

• 08.02.2015 10:00 мск — fourth round

**the dates and time of the rounds can change, follow the information on [our website].(http://it-edu.mipt.ru/zksh2015).

Cost of participation:

• Free participation is guaranteed to the winners and prizers of the final stage of the All-Russian Olympiad for School Students (or CIS Olympiads) in Informatics and Mathematics.

• 5900 for winners and prizers of the ALl-Russian Team Olympiad for School Students in Programming and the Open Olympiad for School Students in Programming.

• 9900 rubles for participants of the final stage of the All-Russian Olympiad for School Students (or CIS Olympiads) in Informatics and Programming

• 18900 rubles for other participants.

For any occuring questions, leave messages on the organizing committee email: [email protected]

The programming committee of Winter Computer Camp 2015 includes: map, Kostroma, Endagorion, DPR-pavlin, ifsmirnov, riadwaw, Babanin_Ivan, Golovanov399, Skird, gchebanov, savinov, Arterm, zemen, kuzmichev_dima, pershik and others.

The organizing committee and the programming committee start its work! See you in February!

Today I want to introduce you some very very useful data structures.

In this lecture, we are trying to improve your data structures skills, stay with us and click on read more.

Hi, Codeforces!

Codeforces Round #285 will be held at 12 January, 12.00 MSK. Problems are authored by me, Evgeny Savinov. This is my first round at Codeforces. I hope that this isn't the last one.

I want to thank sokian and Golovanov399 for help in preparing and testing round, Zlobober for invaluable help in preparing round, AlexFetisov for testing round, Delinur for translating problem statements in English, and of course, MikeMirzayanov for great systems Codeforces and Polygon.

By the way, today(11 January) is MikeMirzayanov's birthday. Happy birthday, Mike!

The round will be for both divisions. Information about score distribution will be posted just before the round starts.

UPD1: Scoring system will be dynamic. Problems will be arranged in ascending expected difficulty order.

UPD2: The editorial can be found here. I'm sorry for the delay.

Mapping a permutation to a number has attracted much social concern. In shortest-path problems, in case a node (or state) is a permutation, we should convert states to integers, in order to BFS or Dijkstra on new graph comfortably. Many coders have known using std::map or trie to do this work. However, both have certain disadvantages. My writing will introduce a new way to solve this problem.

It is hard to write both long and detailed blog. Therefore, you can comment anything which you didn't understand well. I will reply (or update this blog if it is necessary).

To understand the role of mapping a permutation to a number, consider problem POSLOZI from COCI. Our goal is to find the length of the shortest path from a permutation S to an other permutation T using allowed operations. A valid operation is swapping two elements in the permutation. We are given a list of pair (p, q) denote we can swap the element indexed p and the element indexed q. Any other swapping operations are not allowed. A possible strategy is to BFS simultaneously from both S and T.

.

I see lots of programmers write code like this one:

pair<int, int> p;
vector<int> v;
// ...
p = make_pair(3, 4);
v.push_back(4); v.push_back(5);

while you can just do this:

pair<int, int> p;
vector<int> v;
// ...
p = {3, 4};
v = {4, 5};