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 2015! Hello Codeforces!

It seems it is time to take stock. Frankly, I was almost feared to start summing statistics of 2014. In 2013 Codeforces showed rapid growth so that it would not be surprising to look bad on the background of 2013. Certainly not! I was pleasantly surprised by the statistics and reports!

Just below is a list of major events and achievements of Codeforces over the year. For you, it's just a list, but please note — every item includes hard work of multi-day Codeforces team, writers of problems, the organizers of contests and tournaments, problem testers and volunteers. Yay! Together we have done all of this:

• introduced Codeforces API
• added (and sometimes improved) all Andrew andrewzta Stankevich contests
• Codeforces supported mode to work as iframe-widget, and Codeforces helped Google to run https://www.calltocode.ie/ for Ireland high school children
• nearly 70 rounds have been hosted for our beloved users
• nearly 450 new and interesting problems were prepared for the contests on the Codeforces platform
• supported new programming languages
• together with CROC was held Coder-Strike 2014
• hosted April Fools Day Contest 2014 from magnificent Maria Nickolas Mykhailova

• together with the jury of Russian Code Cup 2014 held RCC Warmup, who opened the RCC for a wide range of Codeforces users
• Codeforces played a role of press-partner of RCC, ACM-ICPC Finals in Ekaterinburg, Yandex.Algorithm
• we held ZeptoLab Code Rush 2014 (Om Nomes!)
• helped wonderful company RocketFuel to run Rockethon 2014 (on Codeforces)
• hosted MemSQL Start [c] UP 2.0 with the finals the MemSQL office!
• had 11 episodes of Codeforces Trainings Season 02
• together with the jury Bayan Contest held Bayan Contest Warm Up
• updated Polygon (http://polygon.codeforces.com/) introducing an infinite number of small improvements
• supported tutorial in Polygon
• file system queries caching in Polygon has led to significant acceleration of most pages
• together with GridDynamics held GridGames (for Saratov university students)
• broke all records: 6274 registrations on Good Bye 2014!

In this cold January day, I send warm greetings to the Codeforces team and our friends: developers, problem coordinators, problem writers, testers, tireless bloggers and all of you — the knowledge-hungry competitors!

And here is a comparison with previous years of Codeforces. Clearly. In Pictures.

Recently magic item has been appeared in settings of a profile. Happy New Year!

UPD: New Year holidays are finishing, magic is disappearing... This year the magic features has been used 7482 times. Here are statistics about target handle colors.

Hurry! Only until the 10th of January, you can change your handle! Note that it will be possible to roll back the changes or change the handle again only after a year.

You can change your handle to the new one which wasn't used before by anybody or which was used by you before. Soon, the links like http://mirror.codeforces.com/profile/Alex_KPR would automatically redirect to the actual profile.

Talking about handles I always reminisce the following story. Once a user wrote me the message: "Please change my handle from I_love_Valya to I_love_Sveta, as I no longer love Valya ..."

Happy New Year!

Welcome to 2014-2015 CT S02E11: Codeforces Trainings Season 2 Episode 11 (2011-2012 ACM-ICPC Latin American Regional Contest + Extended). The training duration is 5 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be availible as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.

Good luck!

It is not visible from user point of view, but we've introduced some changes in Codeforces backend to improve system performance. And now we want to test the system before Round 278.

I invite you to take part in Testing Round 11. It will start soon, on November, 20 21:30:00 (UTC). It will be unofficial unrated round.

Pretests are unusually weak to trigger more hack.

If you see any unexpected behavior or bugs, please inform us via comments.

Thanks.

UPD.: Thank you for participation.

Welcome to 2014-2015 CT S02E10: Codeforces Trainings Season 2 Episode 10 - 2014 Amirkabir University of Technology Annual Programming Contest (AUT APC 14). The training duration is 5 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be availible as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.

Good luck!

489A - SwapSort

All you need is to swap the current minimum with the i-th element each time. You can do it with the code like:

    for (int i = 0; i < n; i++)
    {
        int j = i;
        for (int t = i; t < n; t++)
            if (a[j] > a[t])
                j = t;
        if (i != j)
            answer.push_back(make_pair(i, j));
        swap(a[i], a[j]);
    }

This solution makes at most n-1 swap operation. Also if (i != j) is not necessary.

489B - Бал в БерлГУ

There are about 100500 ways to solve the problem. You can find maximal matching in a bipartite graph boys-girls, write dynamic programming or just use greedy approach.

Let's sort boys and girls by skill. If boy with lowest skill can be matched, it is good idea to match him. It can't reduce answer size. Use girl with lowest skill to match. So you can use code like:

sort(boys.begin(), boys.end());
sort(girls.begin(), girls.end());

for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        if (abs(boys[i] - girls[j]) <= 1)
        {
            girls[j] = 1000;
            result++;
            break;
        }

489C - Даны длина и сумма цифр...

There is a greedy approach to solve the problem. Just try first digit from lower values to higher (in subtask to minimize number) and check if it is possible to construct a tail in such a way that it satisfies rule about length/sum. You can use a function `can(m,s)' that answers if it is possible to construct a sequence of length m with the sum of digits s:

bool can(int m, int s)
{
    return s >= 0 && s <= 9 * m;
}

Using the function can(m,s) you can easily pick up answer digit-by-digit. For the first part of problem (to minimize number) this part of code is:

    int sum = s;
    for (int i = 0; i < m; i++)
        for (int d = 0; d < 10; d++)
            if ((i > 0 || d > 0 || (m == 1 && d == 0)) && can(m - i - 1, sum - d))
            {
                minn += char('0' + d);
                sum -= d;
                break;
            }

The equation (i > 0 || d > 0 || (m == 1 && d == 0)) is needed to be careful with leading zeroes.

489D - Невыносимая запутанность бытия

Let's iterate through all combinations of a and c just two simple nested loops in O(n²) and find all candidates for b and d inside. To find candidates you can go through all neighbors of a and check that they are neighbors of c. Among all the candidates you should choose two junctions as b and d. So just use https://en.wikipedia.org/wiki/Combination All you need is to add to the answer , where r is the number of candidates (common neighbors of a and c). The code is:

    for (int a = 0; a < n; a++)
        for (int c = 0; c < n; c++)
            if (a != c)
            {
                int r = 0;
                for (int b = 0; b < nxt[a].size(); b++)
                    if (nxt[a][b] != a && nxt[a][b] != c && g[nxt[a][b]][c])
                        r++;
                result += r * (r - 1) / 2;
            }

It is easy to see that the total complexity is O(nm), because of sum of number of neighbors over all junctions is exactly m.

P.S. I'll be grateful if some of you will write editorial of E and F in comments because of now I should leave Codeforces and will return back some hours later. Thank you for participation!

Hello, Codeforces!

Actually, I didn't understand how, but I've prepated a round for the second division. I think it is subconscious wanted to soften the hard memories of the round of 276.

I hope that very much that the round will be held without any technical issues, as was the 277th.

I express my sincere gratitude to all involved in the preparation — Maxim Zlobober Akhmedov, Maria Delinur Belova, Polygon System, servers and James Gosling for Java. Also I am immensely grateful to the driver, who did not knock down me by car, although I, thinking about the problems, was crossing road on red.

It will be rated round, 6 problems and non-typical progressive scores: min(500 + i*500, 2500).

Wish you to see many Accepteds.

UPD. The Round moved 5 minutes forward. I want very much so that no one be late! Sorry.

UPD 2. Rating has been updated. But if we will find any cheaters, they will be punished and we will recalculate ratings. Thank you for participation!

Welcome to 2014-2015 CT S02E09: Codeforces Trainings Season 2 Episode 9 - 2006-2007 ACM-ICPC Northeastern European Regional Contest (NEERC 06). The training duration is 5 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be availible as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.

Good luck!

Hello,

I'm really starting to think that plans to host ACM-ICPC World Finals bring misfortune. ACM-ICPC World Finals 2011 initially were planned to be in Egypt, but revolution has changed plans.

What do you think about chance to drop World Finals in Morocco because of Ebola Virus?

Welcome to 2014 Benelux Algorithm Programming Contest (BAPC 14), 2014-2015 CT S02E08: Codeforces Trainings Season 2 Episode 8. The training duration is 5 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be availible as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.

Good luck!

Hello Codeforces.

Just a reminder about something most of you know. Polygon is a service to prepares programming problems and contests. It is usually used to prepare problems for olympiads/programming contests but it is also often used to prepare educational content. It is located at https://polygon.codeforces.com/ and is open to everybody.

I have recently found out that it's been more than five years since the creation of Polygon. It's high time to summarize the experience we've accumulated.

I first publicly spoke about Polygon in a narrow circle of Russian teams' coaches on ACM-ICPC World Finals in 2009. I cannot say that everybody was enthusiastic about the innovation. Some people were openly skeptical about such system's viability and relevance. After 5 years on the ACM-ICPC finals in Ekaterinburg Oleg Hhristenko (snarknews) said that in his opinion, the creation of Polygon is more of my achievement than Codeforces. Of course I was surprised but I said so to Polygon :-)

When I started working on Polygon (in the autumn of 2008), I understood very well how much this system was needed. By that time I had already been an experienced writer of many problems. The infinite number on highs-school Saratov Olympiads and ACM-ICPC Subregionals. My problems were on the All-Russian Team School Student Olympiad in Programming, the Russian National Olympiad in Informatics (for High-School Children), the ACM-ICPC NEERC Regionals, the TopCoder Open Finals and many other places. In most cases the problems were developed in some VCS (e.g. SVN) everything was structured by some half-formal unspoken naming rules.

I am going to give you some thesis statements on why it is good to use Polygon and bad not to.

1. Polygon protects from errors

Polygon is full of automatization, self-checks and verifications. Some examples:

• it is hard to make a misprint in a sample input/output and forget to actualize it after the tests are changed as it is inserted automatically and the answer is generated by Polygon using the model solution;
• it is hard to leave a non-compiling solution in the archive (even experienced teams like ITMO regularly leave the solutions on Java in the archive where the name of the class doesn't match the name of the file);
• it is hard to forget to make the first test the statement test, Polygon would warn you about it;
• it is hard to write a generator that is initialized from time and thus it prints different tests on consecutive invocations (i.e. not stable), Polygon will run the generator a couple of times with an interval of one second and check if the tests match.

2. The archives (packages) of the Polygon problems are uniform and machine-readable

It's striking that the olympiad community hasn't standardized a method to distribute problems. The problems from Polygon have a uniform and logical way of organizing files and are machine-readable. File problem.xml contains not only the basic meta information like memory limits, but it also has everything you are going to need for the continuing work at a problem. Here are some examples:

• for TL it shows the type of the processor for which the TL was chosen;
• it clearly shows the IO method and file names (if used);
• it supports multiple native languages in for problem title/statements;
• It has an exact way to generate each of the generated tests;
• solution tags (for example, a deliberately slow solution can be tagged as time-limit-exceeded);
• precise paths to tests and other resources.

I don't know any other machine-readable descriptor formats in use that are so complete.

3. Polygon stores files for long-term and keeps them available

I can open the problems of the ACM-ICPC Saratov Subregional 2009 and edit a test. Everybody who has access to the problem can do the same. All the changes will be visible to all the coauthors, they will be notified via email and the automatic testing systems can get the changes when new problem package is built. I can run the solutions as I edit, all tests will be validated, all the solutions will be ran. But what happens if you don't use Polygon? For the time of contest developement a local version control system is used, it is usually shut down later and only the archive remains: we lose editing history, developing access, automated invocations and other things.

4. Polygon decreases the barrier to entry the problem preparation process

The Codeforces problem writers are the contest participants of different level of training, cultural and professional background, for many of them it's their first experience of preparing problems. They almost always easily understand what to do and how to do it, they can add problems. If you don't use Polygon, then the process is usually regulated by a system of unspoken rules (like, add suffix _slow, or _tl to the title of the slow solution), an unexperienced participant gets lost and cannot understand what to begin with and how to work. Besides, it usually requires some knowledge of basic principles of working with svn and command line and work differs for the Windows and Linux users.

5. Polygon helps you manage access

In Polygon you can give access to the problem to any registered user. If you work without Polygon, it is usually done by the version control system server administrator and you don't even have the list of your co-authors. You cannot manage access on your own, the access is usually managed at the contest level, not problem level.

6. Polygon has issue-tracking

When there is more than one developer working simultaneously, they absolutely need to be able to add and manage issues. Besides, issue-tracking is useful in individual work as well. It structures work, helps you not to lose track of the details. Whenever I've worked outside Polygon, the best task management I saw was a special file with a numbered list of tasks.

7. Polygon is easily integrated with online judges

Polygon offers machine-readable problem packages with prepared tests (for both Windows and Linux) or enables to generate them at package deploying. Polygon has a simple HTTP POST-based API to access data. While POST-queries are formed, you need to set the user's login and password parameters (and optionally, revision).

• https://polygon.codeforces.com/p/username/problemname — download the last package (unless the revision is defined);
• https://polygon.codeforces.com/p/username/problemname/problem.xml — download the descriptor from the last package (unless the revision is defined). For example, in order to see that the revision has changed and we need to re-download the package;
• https://polygon.codeforces.com/c/contestid/contest.xml — download the descriptor of the contest
• https://polygon.codeforces.com/c/contestid/english/statements.pdf — download the PDF with statements in English, all the statements are listed in the contest's descriptor.

Say no to manually copying problems into the judging system, let the system upload the problem for you and deploy or update it.

8. Without Polygon the developer needs to have some special soft on his PC

For example, a developer with Windows may need bash to run doall.sh that generates all the tests. Or a Java programmer will have to install C++ to compile the checker. Use LaTeX to compile the statement. Polygon sets you free from all of that, lots of work is done on the side of the server.

9. Polygon is safer than most alternative ways of shared development

Polygon uses HTTPS, you can attach browser session to IP-address (it is optional, of course), session is attached to User-Agent, we use CSRF-tokens everywhere.

10. Polygon classifies and indexes problems

You will never get lost in problems. I have about 500 problems in Polygon made by me only, but due to tags, filters, search and sorting into contests I never get lost in them and can quickly find what I need.

The End

Those are only the first reasons that came to my mind at 2 AM. I am sure that we can come up with some more of them after some thorough thinking.

The conclusion is simple. Every time you make a problem not in Polygon, god kills a kitten.

Welcome to 2014-2015 CT S02E07: Codeforces Trainings Season 2 Episode 7. The training duration is 4.30 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be availible as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.

Good luck!

The contest has been moved to the Gym.

Today it will be ACM-ICPC, NEEERC, Southern Subregional Contest! As a head of judges I wish good luck to all the participants!

• standings link: http://contest.sgu.ru/monitor/?id=1

On Saturday (October, 25), 07:00 (UTC) it will be a internet-mirror: [contest:481]. Interesting problems are waiting for you. Judges tried to prepare problems of wide difficulty range: for newcomers and for expirienced teams.

For sure, it will be unrated contest. We recommend you to take part in teams. I think, the contest will be moved to Gym later.

Good luck!

MikeMirzayanov, head of judges.

P.S. Saratov Views:

Because of the Codeforces Round 273 (Div. 2) the training contest 2014-2015 CT S02E06: Codeforces Trainings Season 2 Episode 6 - 2007 Benelux Algorithm Programming Contest (BAPC 2007) will be moved one day forward.

Welcome to 2014-2015 CT S02E05: Codeforces Trainings Season 2 Episode 5 - 2009-2010 ACM-ICPC, NEERC, Southern Subregional Contest. The training duration is 4.30 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be availible as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.

Good luck!

Welcome to 2014-2015 CT S02E04: Codeforces Trainings Season 2 Episode 4 (US College Rockethon 2014 + COCI 2008-5 + GCJ Finals 2008 C). The training duration is 4.30 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be availible as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.

Good luck!

Welcome to 2014-2015 CT S02E03: Codeforces Trainings Season 2 Episode 3 (NCPC 2008 + USACO DEC07 + GCJ 2008 Qual). The training duration is 4.30 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be availible as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.

Good luck!

Welcome to 2014-2015 CT S02E02: Codeforces Trainings Season 2 Episode 2 (CTU Open 2011 + misc). The training duration is 4.30 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be availible as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.

Good luck!

Welcome to 2014-2015 CT S02E01: Codeforces Trainings Season 2 Episode 1 (NEERC 99 + misc). The training duration is 4.30 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be availible as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.

Good luck!

The new season of a collegiate team championship ACM-ICPC is about to start. For example, the registration for the Southern (Saratov) Subregional Contest is already running. I am sure that many participants of the Codeforces rounds will take part in ACM-ICPC this year.

We are launching a series of weekly practice trainings on Codeforces. Naturally, they will be held within Codeforces::Gym. Feel free to participate!

The practice starts on Thursdays at about 12:10 PM (UTC), which is 16:10 Moscow Time. Expected duration is 4-5 hours. We are going to practice using the problems of different contests of the past years. All you need is common sense and observing these simple rules:

• We will not publish the problem source before the practice starts. We want you to solve the problems on your own in a fair competition. If you use somebody else’s code or cheat in any other way, you will be disqualified. If you don’t want to solve on your own, that’s fine, you don’t have to. But spoiling the practice for others is unacceptable.
• Do not discuss the problems till the practice ends.
• We will rarely answer the questions about problems. If you’ve found some obvious bug, please let me know. We will fix the bug and send everybody the note about the fix.
• If you have a coach account (and you do not participate in the practice), we will be grateful for your help.
• Please register for the practice with the people from your team who actually participates in it.
• From time to time, I am going to ask some of the jury of the past contests or coaches from other higher educational institutions to help with preparing or share materials — your understanding and help will be greatly appreciated!
• if you solved the contest problems before just switch to another training or inform us via problem questions form, we will move you to out-of-competition role.

The first contest 2014-2015 CT S02E01: Codeforces Trainings Season 2 Episode 1 (NEERC 99 + misc) takes place on September, 11, at about 12:10 PM (UTC).

I've got challenge from agul and caustique. Challenge accepted!

Challenge thrown to TopCoder employees: rng_58 and ivan.metelsky.

Dear friends, you might have noticed that the VK logo has disappeared from the Codeforces pages and all of a sudden the place got sort of empty and a little bit gloomy. By the way, it happened not because the VK company lost the interest towards Codeforces and programming contests. Not at all. On the countrary, we have great plans to carry out together! We are infinitely grateful to the VK company for the 4 years of help and support.

We are glad to inform you that now a wonderful company called Telegram is going to help Codeforces. The company is founded by Pavel Durov and it united many brilliant developers with a rich olympic past. It is pleasant and important for us to see Codeforces helped by the people who understand programming contests, love them and value the skills of the community members. The Codeforces team is happy to get the opportunity to continue working and promises to continue dazzling you with contests, innovations and improvements.

Mike Mirzayanov and the Codeforces team