Welcome to 2016-2017 CT S03E05: Codeforces Trainings Season 3 Episode 5 (2016 Stanford Local Programming Contest, Extended). 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 available as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

Visit Codeforces::Gym to find the contest and register.

We are planning to start on October, 5, 2016 13:10 (UTC).

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 2016-2017 CT S03E04: Codeforces Trainings Season 3 Episode 4. 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 available as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

Visit Codeforces::Gym to find the contest and register.

We are planning to start on September, 28, 2016 13:10 (UTC).

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 2016-2017 CT S03E03: Codeforces Trainings Season 3 Episode 3 - 2007-2008 ACM-ICPC, Central European Regional Contest 2007 (CERC 07). 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 available as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

We are planning to start on September, 21, 2016 13:10 (UTC).

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 2016-2017 CT S03E02: Codeforces Trainings Season 3 Episode 2 - 2004-2005 Open Cup, Volga Grand Prix. 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!

We are planning to start on September, 14, 2016 13:10 (UTC).

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 2016-2017 CT S03E01: Codeforces Trainings Season 3 Episode 1 - 2010 Benelux Algorithm Programming Contest (BAPC 10). 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 Wednesdays at about 13: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 2016-2017 CT S03E01: Codeforces Trainings Season 3 Episode 1 - 2010 Benelux Algorithm Programming Contest (BAPC 10) takes place on September, 7, at about 13:10 (UTC).

I am glad to inform you that C++14 has been added to the list of supported languages ​​on Codeforces. The choice fell on the compiler MinGW-w64, version of GCC 6.2.0 (will be updated on new releases). If you have Windows, you can easlily install it using PBOX with one command pbox install mingw-w64.

Besides trendy features of C++14 (not sure there's a lot to the contests), there are some advantages:

• this compiler is faster than mingw-tdm 5.1.0 on cin/cout — for example, reverse a sequence of 10⁶ integers from 1 to 10⁶ runs 1.5 seconds instead of 2.5 (0.3 vs. 1 if you use std :: ios :: sync_with_stdio (false))
• works correctly to print a double with the both specifiers %f and %lf (you should read using %lf)
• works correctly to read-write long double with the specifier %Lf
• works correctly to read-write long long both with %lld and %I64d

It seems that lately we remove support of MinGW C++/C++11 (especially since it is difficult to upgrade them to GCC 6 due to backward compatibility issues). Of course, after a while C++14 will appear on Polygon.

The language of the round is Kotlin. Kotlin is a statically-typed programming language that runs on the Java Virtual Machine and also can be compiled to JavaScript source code. Its primary development is from a team of JetBrains programmers based in Saint Petersburg, Russia (the name comes from the Kotlin Island, near St. Petersburg).

Here is an example of the simplest program on Kotlin to print sum of two numbers:

fun main(args: Array<String>) {
    val (x, y) = readLine()!!.split(' ').map(String::toInt)
    println(x + y)
}

Here are some links to help you with Kotlin:

• https://en.wikipedia.org/wiki/Kotlin_(programming_language)
• https://kotlinlang.org/docs/reference/
• http://try.kotlinlang.org/ — be careful: reading from the console in the web-IDE is not allowed
• and Google!

You can download standalone compiler (version 1.0.1) by the link http://s.codeforces.com/files/kotlin-compiler-1.0.1.zip Also you need JRE (virtual Java machine), you can find it by the link http://www.oracle.com/technetwork/java/javase/downloads/jre8-downloads-2133155.html

The password from the archives with IDEA (IDE supporting Kotlin out of the box): c8bf9dd9b91ad9ff Links to IDEA are below or you can download it from the official website

Good luck!

====

UPD: You can predownload development pack (sorry, 300MB). In fact, you can take part without it — the Custom Invocation tab will be available during the contest. Also we will publish more compact tools 30 minutes before the start.

All archives are encrypted. The password will be announced 30 minutes before the contest.

========

Surprise Language Round #8 will start on June 16, 16:00 (UTC). It will be unusual entertaining contest. Solutions on the only programming language will be allowed.

Thus, it is expected that during the round, participants can get acquainted with the language and solve a few simple problems. The language will be announced 30 minutes before the start of the round. At the same time (or earlier but encrypted archives) we will publish the archives with the tools to write programs in this language.

I am pleased to announce that the top 20 participants will receive an exclusive t-shirt, and another 10 random participants among those who solved at least three problems will receive an exclusive t-shirt too.

The rules of the contest are as follows:

• The contest is unrated for everybody.
• The round uses ACM ICPC rules: the standing is defined by the number of solved problems, ties are resolved based on penalty time. Initially the penalty is 0, and for each solved problem it is increased by submission time (since the start of the contest) + 20 minutes for each failed submission. The solution is considered to be correct if it passes all tests from a predefined test set; you know whether the solution is right immediately after sending it. There are no hacks.
• The round will have 8-10 problems, sorted by estimated complexity, and you have 2 hours to solve it.
• Solutions are accepted only in one language, which will be announced in 30 minutes before the contest.
• Please reread this post at the beginning of the contest: we will announce the language and add instructions to install the compiler (the contest interface will provide an option to run your solutions online as well) and links to useful manuals. Other than that, learning the language is up to the competitor. You can use any resources to solve the problems (as long as you remember that this is an individual competition); you don't have to limit yourself to the manuals provided in the post.

Good luck!

Sometimes you can meet interactive problems on programming contests (including Codeforces).

In problems of this type, the input data given to your program may be not predetermined but is built specifically for your solution. Jury writes a special program — interactor, such that its output is tranferred to the input of your solution, and the output of your program is sent to interactor’s input. In the other words, your solution and the interactor exchange the data and my decide what to print based on the "history of communication".

When you write the solution for the interactive problem it is important to keep in mind that if you output some data it is possible that this data is first placed to some internal buffer and may be not directly transferred to the interactor. In order to avoid such situation you have to use special flush operation each time you output some data.

Today, June 2, 2016 year, there was a technical failure, which I will remember for a long time. Several factors led to a serious malfunction of the Polygon system.

The fact that in the middle of May Polygon was transferred to servers located in Mail.Ru data centers. To transfer with almost no downtime (Polygon has a lot of data, about a terabyte) lsyncd utility has been used, which quickly pushed the file changes from the old server to the new one.

Today there was a reboot of the old server, which forced the unplanned start of lsyncd daemon. As a result it did the synchronization of data from the old server to the new again. So, data stored in the file system have been rolled back to the transfer time (May 13). The most unlucky fast that, unlike the old server where the backups system was set up well and reliable, on the new server, I quickly managed to set up only replication using the same lsyncd, which does not help in the incident of files deletion (as it forces the removals on the replica). Obviously, RAID-1 disks didn't save the data.

As a result, all file changes in the Polygon system made in three-week period were lost. Some information (statements, etc) is stored in the database, so accessible.

This night I urgently implemented the special link "Scraps" to download the archive with the available data. If a problem has been used in the Codeforces infrastructure, the packages remain in its cache of the judging system, they are available in archive.

I feel lousy realizing that my lack of attention to detail has led to such consequences. I distinctly remember the black day of Codeforces — and as a result many things have been much revised (everywhere mirrored disk arrays, replicas and backups). Unfortunately, this time after moving to new hardware I did not return all scripts and here is the result. Problem writers please accept my deepest apologies for my mistake.

Hi!

I know that it will be obvious for real C++-masters, but for me it is small surprise. I used to think that signed overflow in C ++ does not cause real undefined behavior on a particular platform. That is, it is clear that depending on the big-endianness/little-endian result may be different.

I found short and funny example:

#include <iostream>
int main()
{
    for (int i = 0; i < 300; i++)
        std::cout << i << " " << i * 12345678 << std::endl;
}

Being compiled with -O2 on modern g++ it will run infinitely. Suddenly, right?

ACM-ICPC World Finals 2016 will take place on May, 19, 03:00 (UTC). It is one of the most important events in programming competitions life.

More than 40000 contestants from 2736 universitites from 102 countries had competed in regional competitions. 128 teams had advanced to the World Finals, which are held this year in Phuket, Thailand. Soon we will know which university takes home the most prestigious title in programming — the tile of the World Champion of ACM ICPC!

Useful links:

• current standings
• ICPCLive video
• ICPCNews

I wish the teams good luck and many baloons!

The Finals of ACM-ICPC 2016 in full swing! Teams and organizers gathered in Thailand. The weather is fine — heavy showers at nights, hot days. The rainy season is in action. Here it is about two a.m. now, but as I absolutely can not sleep, I decided to share my impressions and photos from the first two days of the main event.

This year, the teams' resettlement delivers certain inconveniences — teams and coaches live in the same hotel, and all the other members of the delegation live in another. The first hotel (Le Meridien), is probably a bit better — own way out to the ocean and pool make everybody to envy those who lives in the Mövenpick (yes, like an ice cream).

Le Meridien, photo from the official hotel website

Buses ply between hotels, you need an hour to go. A bit uncomfortable that the buses do not run every day, or at least not always, only as scheduled.

On May, 5, 16:05 (UTC) Codeforces Round 350 is going to start! Yes, pay attention to the non-standard start time.

I took advantage of my official position and the round is expected to be a bit experimental with an expanded set of problems. Perhaps for experienced participants (sorry, Div 1) it could seem easy. This time, emphasis was placed on the main target audience of the round: so in the round will be a lot of very simple problems, but even the top of the second division will find something interesting. In addition, one of the problems will be offered in two versions — in a simplified version with small constraints and in a harder version with greater constraints. Thus, if you immediately realize solution for large constraints, you can write and submit the same code on the both version.

The problem writers are me and fcspartakm. We hope that you will enjoy the problems and the round will be fun and useful!

The expected scoring is:

• A: 500
• B: 750
• C: 1000
• D1: 1000
• D2: 500 (i.e. the complete solution of D is 1500 points)
• E: 2000
• F: 2500

Good luck!

UPD: As it was pointed in the comments we have a tricky point about hacks with problems D1/D2.

1. To avoid the situation when participant locks the problem D1 and looks the solution of the problem D2 in his room, you are allowed to lock the problems D1/D2 only together in the same time and only if both of your solutions for this problems passed the pretests. In the other words, the possibility to lock D1/D2 will appears only after you solved both problems. The problems D1/D2 will be locked together in the same moment.

2. To avoid the situation of double reward for hack of D1 and D2 of the same participant, the participant A after successful hack of the participant B on the problem D1 loses the possibility of the hack B on the problem D2. Similarly if the participant A successfully hacks the participant B on the problem D2, then A loses the possibility of the hack B on D1.

UPD 2: The round is over. My congratulations to the winners! Here are the heroes of the round.

The Top-5 among the official participants:

1. xlk200
2. TableEnterer_Lin
3. cykhhq595
4. xxxholic
5. A_Navie_Moer

The Top-5 among the unofficial participants:

1. anta
2. -XraY-
3. Um_nik
4. halyavin
5. Enchom

UPD 3: Problem analysis is now available.

April 25, 18:00 (UTC) the second Wild-card round of VK Cup 2016 will take place.

Participants are invited to achieve progress in solving an unusual problem. VK Cup teams which were advanced to the Round 2 (and didn't advance to the Round 3) will take part in VK Cup 2016 - Wild Card Round 2 officially. In addition, this round will be open to the public for unofficial participation for everybody. Registration will be open for the whole round duration.

The round will be one week long. After the end latest submission (with positive score) of each participant will be judged on system tests.

Good luck!

UPD 1: Unfortunately, it turned out that most of current tests were not various enough and did not cover different scenarios of the testing system. Tests in the system have been updated, all submissions will be rejudged. Perhaps the rejudging process will take some time. In addition, the scoring function has been updated (its monotony maintained). Because of this, points for your submissions changed a bit. The restriction on the number of submissions has been added (up to 20000). Check out the updated statement for details.

Hello!

Last weeks I was concerned (and probably, you too) about abnormal rating growth of our leaders. Of course, first of all I'm talking about tourist, his rating is just rushed into the sky.

There were even comments from a series of "I told, and it happened"

After the first round of VK Cup 2016, I carefully investigated the reasons of such growth and found a simple and trivial bug in the rating formulas. It's funny that even after being published, nobody found it. Look at this function:

    private double getSeed(List<Contestant> contestants, Contestant contestant, int rating) {
        Contestant extraContestant = new Contestant(null, 0, 0, rating);
        double result = 1;
        for (Contestant other : contestants) {
            result += getEloWinProbability(other, extraContestant);
        }
        return result;
    }

Remind, this feature is to calculate the expected participant place, if its rating suddenly became equal to rating. Of course, it should not take account of the participant itself (to whom we currently assign new hypothetical rating). The correct code must be:

        for (Contestant other : contestants) {
            if (other != contestant) {
                result += getEloWinProbability(other, extraContestant);
            }
        }

This bug led to the fact that taking the first place tourist actually won a very serious opponent. Himself. This led to a significant increase in its rating, even if the first was quite expected.

The good news is that this bug has a statistically significant effect only in the very rare cases when the winner (or close to the winner) had a very high rating (yes, contrary to "anti-heroes" is also true). If we take an arbitrary round and recalculate the rating formulas corrected, almost all participants will receive exactly (or very close) rating.

After consulting with tourist and Petr, I came to the following plan of action:

• Today we had chronologically recalculated all ratings from the revolution of 2015,
• If difference between the change according to the corrected rating formulas and the historical change (according to formulas with a bug) is no more than 3, the historic change continued to be used,
• If difference between the change according to the corrected rating formulas and the historical change (according to formulas with a bug) is more than 3, the change is replaced with the correct rating in history.

It turned out that this bug did not affect practically all users. Bug touched only the top. I apologize to those who had descended from heaven to earth — but it was impossible to leave it as is. I wish leaders to get those ratings that were before rating fix.

Mike.

Sentimental moment for me: going through old things I've found something ancient

What most ancient (or most ancient) contest t-shirt do you have?

Hello.

Now it became much unlikely to skip a round due to carelessness during the registration. In the coming rounds (in experimental mode) we will add new feature extra registration (it is good terminology? additional registration?).

This means that after the period of regular registration (as usual, 5 minutes before the start of a round it will be closed) there will be another additional period of registration. It will start in 10 minutes after the start of the round with duration of 20 minutes, that is, it will close after 30 minutes from the start of the round.

The role of the 10 minutes is twofold:

• on the one hand it is quite possible to solve the easiest problem in the first 10 minutes — so it makes a motivation to register on time,
• on the other hand the system is loaded much during the first minutes of a round, as a registration invalidates some internal caches it is better to open extra registration after 10 minutes.

When registering during the extra time a participant is automatically assigned to a random room (among suitable for its role).