Hi, Codeforces!

Codeforces Round #325 will take place on October 12, 2015 at 09:00 UTC for the first and second divisions. Please note that the round will start at unusual time!

The problems of this round are taken from the Regional stage of the All-Russian school team programming olympiad that will be at the same time in Saratov, Russia. Lets wish school teams good luck on competition!

The problemset for school olympiad differs from problems that will be on round. In addition in problemset for school olympiad there will be some problems, which are not included in the round and vice versa. So don't be frightened by the difficulty of problems given for school teams :-)

The process of problems preapring was very interesting: we were reworking problem statements many times, adding tests, changing limits, even managed to change fully prepared problem with another (we had to stop the conveyor already printing problem statements :-)) Let's thank all who were preparing, helping in preparing, reading the problem statements, writing solutions: Adilbek adedalic Dalabaev, Roman Roms Glazov, Vladimir vovuh Petrov, Oleg Oleg_Smirnov Smirnov, Alexey Perforator Ripinen, Maxim Neon Mescheryakov, Ilya IlyaLos Los, Vitaliy gridnevvvit Gridnev, Danil danilka.pro Sagunov, Alexander fcspartakm Frolov, Pavel HolkinPV Kholkin, Igor Igor_Kudryashov Kudryashov, Elena elena Rogacheva, Dmitriy Nerevar Matov, Vitaliy kuviman Kudasov. Chairman of the jury of the Olympiad is Mikhail MikeMirzayanov Mirzayanov (also he is the author of some of tasks). I (Edvard Edvard Davtyan) prepared some tasks and coordinated the work of the authors. So we are a large team of writers (I hope I did not forget anyone)!

Also let's thank Max Akhmedov (Zlobober), The-One-Who-Must-Not-Be-Named (if I am not wrong, he or she is right now solving the round problems) for their help in problems preparing, Maria Belova (Delinur) for translating problems in English and again Mikhail Mirzayanov (MikeMirzayanov) for the Codeforces and Polygon systems.

You will have only two hours to solve six problems. The scoring distribution will be anounced a little before the round. I wish high rating to all participants! Good luck and have fun!

P.S.: Also I want to wish good luck to the participants of the ACM ICPC Southern Subregional Programming Contest that will be held on Wednesday.

UPD Due to technical reasons round is delayed by 10 minutes.

UPD: In problem Subway roller there were tests with trains of length one. At this moment authors are discussing how much it troubled the round results. We are apologize to participants who had problems with that. We will announce our decision about this problem soon.

UPD2: There were trains with length equal to one in tests for problem Subway Roller. Jury decided to accept the first right solution of each user that passed all tests except the wrong, also other submissions were ignored. In addition we accept all successed hacks, although the hack is not correct and the hacked solution passed all other tests. Contest will be rated, but any user who think that this situation is cardinally affected to his/her result can send me in 24 hours a message and jury will discuss the question to make round unrated only for that participant. We are apologize to participants one more time for this situation.

UPD3: Editorial

Hello, Codeforces!

I'd like to invite you to Codeforces Round #324 (Div. 2). It'll be held on Tuesday, October 6 at 19:30 MSK and as usual Div. 1 participants can join out of competition.

Great thanks to Zlobober (Maxim Akhmedov) for helping me preparing the contest, to Delinur (Maria Belova) for translating the statements into English, to MikeMirzayanov (Mike Mirzayanov) for the Codeforces and Polygon. This is my first round, and, I hope, it won't be the last one.

You will be given five problems and two hours to solve them. The scoring distribution will be announced later.

Characters from problems have their prototypes — my friends, familiars, native, and this round is dedicated to them.

UPD : 500-1000-1500-2000-2500

Good luck and high rating!

UPD2 Round has finished, thanks for participation!

Congratulations to the winners!

1). Siunaus

2). aasddf

3). M_H_M

4). lal

5). femsub

Editorial will be published later

UPD3 Editorial

In this post I want to describe in short how to write a formulas on Codeforces. In fact it is short introduction to the markup language used on Codeforces.

Three important rules.

Foremost rule: formula me place in dollars ($), as well as in parentheses.

Another important rule: if you want to apply some operation to some group of symbols it is necessary to form the block using the curly braces. For instance, 2^x+y = 2^x + y, but 2^{x+y} = 2^x + y.

Third rule — for perfectionists. For traffic economy Codeforces print simple formulas by usually text. Sometimes it is not very pretty: C_{x_i+y_i-2}^{x_i-1} = C_{xi + yi - 2}^x_i - 1. Is this case you can add command \relax at the beginning of the formula. Then the formula is guaranteed to be beautiful: \relax C_{x_i+y_i-2}^{x_i-1} = .

Arithmetic operations.

Addition and subtraction can be written ordinary symbols + and -. Multiplication is usually indicated by a null character (xy is the produst of numbers x and y) or by symbol (\cdot). If it is necessary to multiply two complex expressions (), or are important both factors, not just the value of the product (in expressions of type field ), use the symbol  × , which may be obtained by the command \times.

The division is somewhat more complicated. Usually in mathematics division is not written in one line, but the desire is not to write the fraction of the blue, too, is understandable. In this case, you can always write a : or / (x:y, x/y).

If you want to write all the same fraction, it has two similar commands: \frac and\dfrac. After any of these commands have to write a block of the numerator and block of the denominator, for example: (\frac{1}{4}). Using \frac small fractions are obtained, which is suitable mainly for the simple fractions. If you want to write a serious big fraction you'll need \dfrac: (\dfrac{x+y}{x^2+y^2}). If the numerator and denominator of a single-character, it can not be enclosed in brackets, for example: (\frac14x), but only if the numerator is not a letter.

The upper and lower indices.

If you want to write a lower index, you will help symbol _ and upper index (basically it is the exponent), the symbol^: (x_i + y_i)² ((x_i + y_i) ^ 2). Same manner as with the fractions in the lower or upper index block can be placed, but if a single-character index, it can not do so.

Other useful tips and special characters

Text — text (---) — not in the formulas, and in the text. This dash, not hyphen (it is not works without surrounding text)
(\dots) — three dots symbol.
∞ (\infty) — infinity symbol.
(\in) and (\ni) — element of the set.
 →  (\to) — arrow right, in expressions such as x_n → 0.
Many well-known mathematical functions can be typed with the '\', then they will look like a formula, rather than simply as text ( = \tg, = \ln, = \lim and so on)
If you want to index are top and bottom rather than the top-right and bottom-right, use the command \limits:
= \sum_{k = 0}^nx^k
= \sum\limits_{k = 0}^nx^k.
If the brackets around a large expression small, you can make them suitable size, written before the left bracket command \left, and before right bracket command \right. For instance: = \left( \dfrac{x+y}{x^2+y^2} \right).

Thank you for the attention!

Hi everybody!

Hope you liked our Revolution of Colors and Titles. Maybe you even have took part in a contest in new status. The last round have set an incredible record: 8000 participants! And I'm glad to tell you that there was no single technical issue during the round time! Consider the 15-minute delay as a part of our evil plan for setting up a new record :)

I'm glad to tell that Codeforces team is able not only to tune colors and formulas, but also to work on new features for you. You may see on contests page that there is a list of authors for each of the rounds! Moreover, in profile of a person there is now an entry called "problemsetting" that allows you to see the list of all contests in whose preparation a person took a part.

Endagorion looks like this.

Greetings, Codeforces!

My name is Danil Sagunov, and I used to be red... Anyway, I wish to congratulate you with the Second Revolution!

I am glad to introduce that this Saturday, 3rd October at 19:30 MSK Codeforces Round #323 for both divisions will take place. Problemset has been prepared for you by me and Vitaly gridnevvvit Gridnev. This is not the first round we are authors of and I'm sure that it's not the last.

Special thanks to our friends Maxim Neon Mescheryakov, Vladimir vovuh Petrov and Roman Roms Glazov for helping us preparing the round. I would like to thank Max Zlobober Akhmedov for his coordinator activity, Michael MikeMirzayanov Mirzayanov for creating and supporting Codeforces and Polygon systems, making this round possible, and Maria Delinur Belova for translating problem statements into English.

Thanks to Vladislav winger Isenbaev and Alex AlexFetisov Fetisov for testing the round problemset!

Both division participants will be given five problems and two hours to solve them. I hope that everyone will find the problems interesting and many of you will return your colors.

UPD The round duration was written incorrectly in the e-mail announcement, the correct duration is 2 hours, not 2.5 hours.

UPD2 Round have been successfully finished! Thank you all for participating.

Congratulations to 1 division winners!

1. ecnerwala
2. ikatanic
3. uwi
4. PavelKunyavskiy
5. sd0061

And the second division:

1. wrong_order
2. ahwhlzz
3. kefaa

My gratitude to fotiIe96, one to solve problem D!

UPD3 Editorial can be found here

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.

Hello, Codeforces!

I'd like to invite you to Codeforces Round #322 (Div. 2). It'll be held on Monday, September 28 at 12:00 MSK and as usual Div. 1 participants can join out of competition. Note that round starts in the unusual time!

This round is held on the tasks of the school stage All-Russian Olympiad of Informatics 2015/2016 year in city Saratov. They were prepared by me and recently returned from army Edvard Davtyan (Edvard).

Great thanks to Maxim Akhmedov (Zlobober) for helping me preparing the contest, to Maria Belova (Delinur) for translating the statements into English, to Mike Mirzayanov (MikeMirzayanov) for the great Polygon platform and ideas of some problems and to Vladimir Petrov (vovuh) for writing solutions.

It will be a little unusual round — you will be given six problems and two hours to solve them. The scoring distribution will be announced later. Good luck everyone!

UPD The scoring distribution today will be 500-1000-1500-2000-3000-3000.

UPD2 Editorial

UPD3 Congratulations to the winners!

1. Moe
2. for_the_pride
3. SakurakoujiRuna
4. VNOI
5. z123z123d