Hello, Codeforces!

In the spring 2016 the company CROC together with Codeforces will hold the third Russian Open programming championship «CROC – 2016». The goal of this project, as before, — encourage of the most talented and innovative young specialists and stimulate interest to the information technology.

As usual CROC company pays great attention to social projects, associated with the development of the IT-industry, to promotion of IT-professions and to the increasing interest in modern technology. CROC has rich experience of cooperation with universities, the organization of courses, seminars and competitions for pupils, students and experienced professionals.

The registration to the championship will be open from March, 1st to March, 16. Anyone, regardless of nationality, place of residence and level of education, can be a participant. The official language of the competition is Russian. Championship participants will take part in two main rounds: elimination round, which will take place in early March, and the final. There will be 50 strongest participants competing in Moscow on April, 15. CROC will cover transport costs in the amount of no more than 10000 rubles (it is about 135 USD). All finalists should confirm their will and ability to visit Moscow to take part in the Final before March 25. CROC will not be able to help you with visa (if it needed), so our primary target audience is Russian participants and participants from some ex-USSR countries. But two years ago rng_58 visited our Finals!

A warm welcome, meeting with the organizers of the event and experts in software development in the CROC, a festive buffet, a fascinating game round and great prizes and gifts are waiting for the finalists. Previous programming championship by CROC was held in 2013 and brought together ~3500 programmers from all over Russia, CIS and other countries.

Prizes

• 1 place — 100000 rubles
• 2 place — 70000 rubles
• 3 place — 50000 rubles

The prize for the winner of the game round is a laptop.

Schedule stages of the championship

• Qualification Round – 16 of March
• Elimination Round – 18 of March
• Finals will be held on April 15 in Moscow in the office of the CROC (50 participants)

All rounds will be open for unofficial participation for everyone. The Elemination and Finals rounds will be rated regardless of participation type (official or not).

Registration

To take part in the championship you have to register on the special page. Registration will be open until the end of the qualification round. Compete with the best programmers in the Open Championship "CROC-2016"!

The history of the CROC championships

The upcoming championship will be the third championship, conducted by the CROC on Codeforces. You can find the information about this championships by clicking on the links below:

• championship CROC 2012
• championship CROC 2013

Hello.

Now Codeforces will be more convenient to browse from mobile platforms. For the majority of them mobile view is available now. The menu goes to the left panel and sidebar — to the right. Both panels are available either on special icon at the top of the page, or by swipe left/right. You can hide them by touch in the main area of ​​the page, or by reverse swipe. In the mobile view fonts are enlarged, so on most screens it is possible to read the website without zoom.

So, for example, how the sidebar appears on my phone:

You can switch off mobile view (or to switch off) by clicking the special link in the bottom of any page.

P.S. In old browsers, and generally on a non-webkit it may work incorrectly. Not sure it is easy to fix :-(

Hello!

Here are some statistics about 2015. I'm glad to see our growth. Frankly, each year I'm afraid to see that we stop to grow, but each year I see 20-50% growth! Thank you for your interest :-)

In addition, I have written before about progress in the development and championships and rounds with partner companies in 2015. If you have not read, please read.

Here are the funny pictures with the statistics:

Growth of registerations. This year we overcame 300K users!

Hello!

I congratulate New Year to the entire Codeforces community! I wish you interesting problems, beautiful solutions and successful attempts in the last seconds! I wish not to lose interest in programming, to believe in themselves and regularly find confirmation of this belief. And do not get sick and more smile (even if your rating decreases). Hooray!

The profile settings appear magical section. Happy New Year!

Hurry! Only until the 10th of January, you can change your handle (but only once)! Note that it will be possible to roll back the changes or change the handle again only after a year. Be careful what you wish for.

You can change your handle to the new one which wasn't used before by anybody or which was used by you before. The links to a profile page with old handle 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!

Hello!

In 2015 we have not only engaged in the organization of rounds and championships. Every day we write the code, debug, test and explore a variety of tools and technologies to make Codeforces better. Even if in some periods you have not seen great changes on the website, it does not mean that the development was stopped — just some of the innovations relate solely to infrastructure, architecture or administrative interfaces and are not visible to the users.

I have collected in a list of all the innovations, which touch users in some sense. This faceless list includes results of many days of work of each member (sometimes with prefix ex-) of Codeforces technical team: MikeMirzayanov, MaximShipko, kuviman, fcspartakm, Avalanche. There are valuable helpers Edvard (helped with the introduction of educational rounds), stingray (constant help with the administration and configuration of servers is priceless), demlit and lthirteenthl (assistance with the administration and hardware). And I just listed those who assist in technical terms — there is an important list of all of those who contributed to the life of Codeforces in other aspects. Thank you!

Here is the promised list of completed (sometimes partially) cases in 2015, the year.

Hello everybody!

I hope you have the holiday spirit!

Later I will publish statistics for the year and tell you about our achievements of this year, and for now I will talk about championships and competitions that we made with our partners in 2015. My speech does not include any activities that we have conducted very far from the Codeforces site (e.g., Russian AI Cup).

This year is remembered by many interesting events that we did not by ourselves, but together with partners. I am particularly pleased that all companies who wished to fill the ranks of their employees found worthy candidates among our members. And someone said that the Olympiads are not needed! That is a lie. Here is the list of events:

VK Cup 2015

Team Championship for young participants, was conducted in Russian. 2349 registered teams of two (rarely of 1 participant). The coolest prize money and rich finals in St. Petersburg. Organizer is the VK company.

Rockethon 2015

Open individual competition by the original rules of the Rocket Fuel company. More than 3600 participants and 6565 registrations!

ZeptoLab Code Rush 2015

Individual competition by the classical rules of the ZeptoLab company. 3090 participants and 5504 registrations, excellent presents for the winners! And insanely beautiful drawings from ZeptoLab artists!

Looksery Cup 2015

! Looksery

Individual competition by the classical rules of the Looksery company. This company did not only congratulate us on our 5th anniversary, but conducted such a cool round. And the fund of the company's founder had very cool initiatives supporting the development of sports programming! 3528 participants and 5714 registrations. Yes, the gifts are yet on the way!

AIM Fund Round 2015

Individual competition in two divisions by the classical rules of the AIM Fund company. Prepared in the context of congratulating Codeforces on the 5th anniversary, thank you! 4064 participants and 6721 registrations. I've heard a lot about the after-party in Petrozavodsk. I wish I had been there!

Call To Code 2015

A competition for Irish schoolchildren by unusual rules. It was not conducted on the Codeforces site, but on our platform. Organized by the Google company.

Hello.

Now you do not have to go into Google if you need to search blog posts. You can do it directly on Codeforces. The implemented search is based on Apache Lucene . The index contains all open public posts, which are already more than 15,000 documents.

Temporarily search for tags are now available (tags will be added to the index soon), but instead you have the opportunity to find posts and even sort using different criteria. By the way, you can use complete syntax of Lucene queries to search. Here is a short description of main features.

You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author.

Some examples:

• 305 — search for 305, most probably it will find blogs about the Round 305
• andrew stankevich contests — search for words "andrew", "stankevich" and "contests" at the same time
• user:mikemirzayanov title:testlib — search containing "testlib" in title by MikeMirzayanov
• "vk cup" — use quotes to find phrase as is
• title:educational search in title

Regarding indexing comments, solutions and problem statements I have a feeling that it may be useless. Too difficult to find something relevant (or maybe not). What do you think: should we implement it?

Hello,

We are launching new feature on Codeforces, in early beta mode. I hope it will be useful to many active users of the web-site. Now you can create, manage and use the "user lists".

Partially, it is a kind of generalization of "friends." You can create a list of users interesting to you (you can create many lists) and, using the list, filter the results of rounds, quickly analyze what problems are solved in the problemset, etc. This feature is a helpful tool for coaching — I'm using it. By combining in a list of all practicing students, it is easy to pick up problems that have not been solved (and even not attempted) by any student.

A user list has name and a pair of two relatively secret keys & mdash; one for view/usage and one for editing. For example, here is the key to view a list of ACM-ICPC students at Saratov State U for autumn of 2015: 15c68c2cf878267d59373d1e56be8c9a

This means that on some pages, you can use the optional parameter ?list=key to apply the list. Here is an example of the screen by the link http://mirror.codeforces.com/problemset/page/3?list=15c68c2cf878267d59373d1e56be8c9a:

Yeah, in the recent training I can give the problems 538H - Summer Dichotomy and 538G - Berserk Robot . In additional information the first number indicates the number of users solved problem, and the second is the number users attempted problem. Codeforces searches solutions/attempts not only for this particular problem, but all the possibilities of its use (say, someone can solve it in other division or in a mashup).

There are additional controls to make it more comfortable to use lists:

At the moment, the lists can be applied:

• in the problemset (shown number of solvers/attempters for each problem)
• in list of rounds/trainings in Gym (shown number of solvers/attempters for each problem)
• on the standings page (to filter the rows)

I remind you that the functionality is in early beta mode & mdash; there may be some issues. We will return to development and bug fixing after ACM-ICPC Regional Contest NEERC 2015.

And what other use of the lists can offer you?

Educational Codeforces Round 1 is over. During 24 hours after coding phase many of you tried to hack other's solutions. And it were many successful hacks!

It was 573 successful hacks, made by 101 hackers. Here are most effective:

Thank you! Now I'm pretty sure that tests of this problems are really complete. Moreover hacks shown that writer's tests are often incomplete. In short, it seems it was really good idea to make open hacks phase.

I'd like to crowdsource editorial for such rounds. Please, write in comments if your are ready to write/improve a editorial for problems C-F. For sure, you should solve problem to help with editorial.

Please, write in comments your feedback. It is very important for us to get it. Thanks!

Hi everybody!

First, I invite you to take part in an official Testing Round 12. The fact is, the Codeforces team has made numerous changes to the platform (details are below), and we want to be sure that the basic functionality remained unchanged. This round will have a shortened duration of 1.5 hours, consist of 3 (maybe 4) problems that you might have already seen before. Its purpose is to test the system on the one hand, and on the other hand — to brighten up a Wednesday evening. Of course, the round will be unrated.

Now the main thing. This coming Friday (yes, the 13th of November) Codeforces starts another line of rounds. We called them Educational Rounds. Using my students at the Saratov State University Programmings Competitions Training Center as an example, I regularly notice that even those who have a considerable progress in the results on the rounds often have narrow purview in terms of standard topics and ideas, they are not familiar with many well-known problems and methods. The fact is, the rounds often avoid any folk or classical subjects, thus underdeveloping the purview of young generation of the participants.

We are pleased to announce the start of a series of educational rounds! They will take place with the regularity of a round 2-4 times per month.

Their characteristics are like that:

• The duration is classic — 1.5 — 2.5 hours;
• The goal is rather to practice and to educate, than to compete;
• Not only problems, but also exercises can be used;
• Useful, even well-known ideas will be reused in order to introduce them to a wide range of participants;
• Often the formal text of the statements;
• Unrated (perhaps for now);
• We will try to conduct them in the ACM-ICPC mode (if there are long waiting lists, we may change the approach);
• The results that are obtained after the end of the round, are preliminary;
• After the end of the round will be a 24-hour period of open hacks — any visitor of Codeforces may try to hack any complete solution to a problem of the last round (either from a contest, or from practice), the source code of hacking solution is available (you can copy the text and, for example, stress it);
• All successful hacks from the previous item will be added to the official test set and after as long as 24 hours after the end of the round retesting of all complete solutions will be made;
• Only after the final standings based on improved test data, the results are final;
• The results of a round are calculated separately by division;
• Our ability to process such problems are limited, so actually the test suites from the jury are expected to end up incomplete — we are looking forward to your hacks!

Basically, we will be oriented towards the members of the second division, but often these rounds will be of interest to more experienced participants.

For now preparing problems to these rounds will be concentrated at the Saratov State University Programming Competitions Training Center, most of the work with the problems will be accomplished by Edvard Edvard Davtyan. We wish him good luck, enthusiasm and energy!

See you at the Testing Round 12, and later at the Educational Codeforces Round 1.

Starting from October 2015 ratings formulas are open. They are given in the post. It is likely that from time to time we will change them slightly, it will be reflected here.

The basic idea of Codeforces rating system is to generalize Elo rating to support games with multiple participants.

Each community member is characterized by value r_i — integer number. Roughly speaking, the higher value means better results in the contests. Rating is calculated/recalculated so that the equality strives to be correct:

where P_i, j is probability that the i-th participant has better result than the j-th participant. Therefore for two participants the probability to win/lose depends on subtraction of their ratings. For example, if the difference of ratings is equal to 200 then stronger participant will win with probability ~0.75. If the difference of ratings is equal to 400 then stronger participant will win with probability ~0.9.

After a contest the values r_i change in a way to satisfy main formula better.

Let’s calculate expected place seed_i for each participant before contest. It equals to the sum over all other participants of probabilities to win (to have better place than) the i-th plus one because of 1-based place indices:

For example, before Codeforces Round 318 [RussianCodeCup Thanks-Round] (Div. 1) tourist had rating 3503 and his seed was ~1.7, and Petr had rating 3029 and expected place ~10.7.

General idea is to increase r_i if actual place is better than seed_i and to decrease r_i if actual place is worse than seed_i.

Having seed_i and actual place, let’s calculate their geometric mean m_i. You can think about it as an something average between seed_i and actual place shifted to the better place. Using binary search find such rating value R which the i-th participant should have to have a seed_i = m_i. Obviously the rating r_i should be modified to become closer to R. We use d_i = (R - r_i) / 2 as rating change for the i-th participant.

It's almost all except the phase of fighting against inflation. Inflation works as follows: the rich get richer. We will try to avoid it. If we assume that the rating was already calculated fair (i.e. everybody has perfect statistically based rating) then expected change of rating after a contest is equal to zero for any participant.

Choose a group of the most rated (before the round) participants and decide that their total rating shouldn’t change. We use heuristic value as a size of such group. Let’s find the sum of d_i over participants from group and adjust all values d_i (for all participants) to make the sum to be zero. In other words, r_i = r_i + inc, where inc =  - sum_s / s, sum_s is sum of d_i over s participants from chosen group.

After the round 327 we restricted the effect in following way. Firstly, we do r_i = r_i + inc, where inc =  - sum(d_i) / n - 1, sum(d_i) is sum of all d_i. It makes the sum of all d_i to be near zero and non-positive in the same time. Secondly, we apply idea from the previous paragraph, but inc = min(max( - sum_s / s,  - 10), 0). Thus, the effect of modification can not reduce rating for more than ~10 points.

By the way, for any consistent rating the following assertions should be true:

• if the participant A had worse rating than the participant B before the contest and finished the contest on the worse place then after recalculations the the rating of A can’t be greater than the rating of B
• if A finished the contest better than B but A had worse rating before the contest then A should have equal or greater rating change than B.

In particular, formulas are tested to satisfy the both items on each ratings recalculation.

You may read the actual Codeforces code to recalculate ratings here: 13861109.

You may print PDF-statements: http://assets.codeforces.com/statements/589.pdf

Recently 2015-2016 ACM-ICPC, NEERC, Southern Subregional Contest has been finished. On behalf of jury and hosts I congratulate winners and advancers to the semifinals. Prize places are (horray!):

• 1 place: Nizhny Novgorod State University #1 (Vladislav vepifanov Epifanov, Nikolay KAN Kalinin, Mikhail mike_live Krivonosov)
• 2 place: Innopolis University #1 (Evgeniy savinov Savinov, Sergey sokian Kiyan, Alexander map Mashrabov)
• 3 place: Saratov State University #1 (Edvard Edvard Davtyan, Vitaliy kuviman Kudasov, Danil danilka.pro Sagunov)

On Saturday (October, 17) в 08:00 (UTC) we will host unofficial online mirror. Interesting problems are waiting for you. Judges tried to prepare problems of wide difficulty range: for newcomers and for expirienced teams. This will be a team/personal contest on Codeforces, with teams consisting of up to three people or individual participants. The contest will not affect Codeforces ratings.

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. We are aware that this mirror will overlap with some other online tournaments, but unfortunately we are unable to change the current time slot, due to the online mirror of the Moscow Subregional of NEERC scheduled on Sunday. All school teams are recommended to pay attention to Online-mirror of the Ural regional team championship.

Over the last several months the Codeforces team has been looking anxiously at the inflation in the rating caused by both an influx of new users and the imperfect calculating formulas.

In the end it lead to noticeable shifts in colors and titles. For example, getting red in 2015 became much easier than in 2013.

We conducted a survey about the way to introduce the color bounds. We are happy to announce the updated colors and titles!

A summary of the main changes goes like that:

• a new color: greenish-blue color or cyan — just like the name implies, this color takes its place between green and blue, now the participants of the second division will be better differentiated;
• all the colors shift upwards along the rating scale — see the table below. Now reaching the top positions will be harder;
• the legendary grandmaster — the new title and color for those who reached the sky high rating 2900.

The cold colors (gray, green, cyan and blue) still correspond to the second division and the other ones correspond to the first one.

The requirements to the coach rights haven't changed — you've got to have 2200 or 1900 and a rich history of participations in order to become a coach. Problem tags and groups can be added by the participants from the first division.

The table below illustrates the new values of the color and rank borders:

Active users (who took part in last 6 months) on the moment of October, 1 are counted.

I will write about the changes in the rating formulas as soon as possible, And yes, the formulas will be open!

Hooray! Soon there will happen several updates on Codeforces affecting rating and colors. The second Revolution of Colors and Titles is coming!

You will soon find out a new rating with public formula, new color bounds and even something more...

New bounds will fix the rating inflation of last year, it will return exclusivity of high rating and titles. Don't worry if you end up with lower color; it's a new reason for you to move forward!

While discussing the ongoing change we faced an issue about how to apply new colors with two possible solutions.

First solution: forward without looking back.

When applying new bounds we will update colors everywhere according to a new schema. For example, somebody can possibly lose not only the read color, but he may also regain a new challenge "to become red" since he lost time when he was red before on his rating history. For the first time it doesn't seem as a good solution, but if you think deeper, there is nothing bad in it. Ratings will be whole without cases like "you were read before the revolution, that doesn't count!". In old ranklists there will be no mess within colors of modern contestants (from upsolving or virtual contests) and historical contestants. Irregular visitors of Codeforces won't be confused of the fact that somebody is red in the standings but shouldn't have been red before according to his rating.

We did like this before it worked not bad, if we have changed the color history back then, it would have added mess and confusing.

Second solution: keeping history.

When adding new bounds we will keep old ranklists, posts and comments "as is". This won't break comments like "Congratulations with a red color!" (not sure if they are that valuable) Such solution will keep your achievement "to become red" unlocked, i. e. this part of your biography remains still confirmed by your rating history.

We may even make a rating graph become cut on two parts with a vertical line at the moment of a revolution. The old colors will remain to the left of it, and the new colors will be placed to the right of it. Although this may lead to a confusing of newcomers unprofessionals and rare Codeforces visitors.

Overall

As you see, both solutions have their pros and cons. I don't even know what is better among this two possibilities. That's why I want you to vote for the better choice. If one of the solutions surely wins, we'll use it. Otherwise I'll do as I think it is best.

Please vote only after carefully reading both options. First two comments below correspond to the solutions. Negative voices won't be considered at all, positive will have weights 1-2-4-8-16-32 according to your color (grey-green-blue-purple-orange-red). The vote is secret, results will be available on October, 1st in the evening.

UPD: The voting is finished. We congratulate the first option with a confident victory: 6394 points vs 2320 points! The comments for voting have been removed not to affect comment votings statistics. You may expect changes in colors and ranks in the nearest future!

As I work with students I often face the situation when if a problem doesn't seem clear to a student at the first sight, it makes them unable to solve it. Indeed, you always hear about specific methods and techniques. But you don't hear about how to think in order to apply them. In this note I'll try to sum up my experience of solving programming contest problems. However, some pieces of advice will also be applicable for olympiads in mathematics and your first steps in academic research.

So you've read a problem and you don't know how to solve it. Try the following techniques, some of them can often come handy.

Technique 1: "Total Recall"

Try to remember some similar problems that you had to solve. Quite many problems do not have a brand new idea. So probably, you can use your experience of solving a similar problem to solve this one.

Technique 2: "From Specific to General"

Let's say that you've found the solution for the problem (hurray!). Let's consider some particular case of a problem. Of course, you can apply the algorithm/solution to it. That's why, in order to solve a general problem, you need to solve all of its specific cases. Try solving some (or multiple) specific cases and then try and generalize them to the solution of the main problem. Such specific cases can be regarded as the simplifications of the problem, i.e. we can reason by the following principle: "if I don't know how to solve a complex problem, I think I'll simplify it and find the solutions of the simplified version".

The popular examples of simplifications (specific cases):

• you get a problem for a tree. Consider its variant where the tree degenerates into a path;
• the problem has weights? Consider a variant where all the weights are equal either to one or to an arbitrary number, or there are only two distinct weights (and so on).

Note that the solution of a specific case almost always isn't easier than the solution of a general one, so you need to try and find a solution that would be as easy and effective as possible.

Technique 3: "Bold Hypothesis"

Don't be shy of making bold hypotheses that seem true to you. You do not have to prove your solutions during contests, tap your inner intuition. When you've come up with your hypothesis, try to prove it — it may either work out well or give you an idea of how to disprove it. Do test the hypothesis on a wide set of tests as it would be a pain to waste time on implementing a solution based on a hypothesis and only after that disprove the hypothesis.

Examples:

• the solution always exists;
• item the number of states isn't large.

Technique 4: "To solve a problem, you should think like a problem"

I'm serious, put yourself in the shoes of the character of the problem, imagine that it's your job to handle the input sets. Think about how you'd act in this case. Try to process some small samples on your own. If the problem is about a game, play it. Sometimes I try to visualize a process or a model for better understanding. It's a little like how movies show the way scientists think. Try to think in images, imagine the solution, see it unfolding.

Technique 5: "Think together"

This technique is only applicable to team contests. In group of two or three persons start saying some clear facts about the problem. For example: "if n is even, then the answer is always 0", "if n is prime, then the solution should go like that", and so on. Sometimes your teammates will pick up ideas and develop them and this strategy can get you through the problem.

Technique 6: "Pick a Method"

Try coming through popular algorithms or methods that can apply to the problem in any way. It is useful to see the problem limits. Having picked a method, try thinking on the solution assuming that the problem is solved using this method. Your reasonings should be somewhat like this: "Let's assume that the problem is solved by divide and conquer. Then let us solve this problem recursively for the left and right half. Now all that's left is to find a way to unite these solutions. I wonder how we can do that..."

Technique 7: "Print Out and Look"

Quite often (especially in problems with a small input: one/two numbers) there are some patterns in the composition of the solution. To see a pattern, you sometimes need to write some naive method of solving a problem, generate answers for a large number of tests on large limits and meditate on your answers for a while. In order not to keep the computer busy, a good strategy is to print out the acquired results and meditate this time on the print outs.

Sometimes it is a good idea to print not only the answer, but also some extra information, such as a manner of acquiring a solutions.

Technique 8: "Google"

This technique can only be used if the round/contest rules allow it. If the problem is about sequences, then you can look for solutions (see technique 7) on the site https://oeis.org/. It helps to understand the formal model of the problem and google the correct mathematical terms.