Oh yes! Only a few days left before the Championship finals! The teams have already gathered in Yekaterinburg, most of them have registered and are watching a game between Russia and Belgium.

I want to start from some history and remember that the tradition to publish travel notes about Saratov State University's trips to finals started back in 2005. The regular pattern is that almost every year when we made notes, our team won a medal. I won't try my luck, so here are some of the first impressions of this year.

We've introduced API and now we want to test the system before Round 251.

I invite you to take part in Testing Round 10. It starts on usual time, June 3rd. It will be unofficial unrated round.

I tried to pick up the problem to make the round interesting for many of you. Pretests are unusually weak to trigger more hack.

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

Thanks.

After a short delay (but Oscar is given in spring too, huh?) we are pleased to announce the Cormen Medal laureates for 2013. This year, we’ve decided to slightly upgrade nominations again, so this year's Cormen Medal is given in two nominations:

• Best Progress
• Best Problemsetter

Best Progress

The Cormen Medal laureate in this nomination is Scott Wu (scott_wu, USA). Note the sharp upward dive his rating line takes. His achievements in 2013 are not limited by the spectacular dive into the best 10 participants on Codeforces: he got the 5-th place on IOI, won the 2013 season of the USACO contests, got target on TopCoder! We congratulate Scott and wish him many more achievements!

Best Problemsetter

We didn't have to search far and wide for the winner in this nomination. Naturally, the Cormen Medal goes to the most productive and loved by many author of 2013, Sergey Nagin (Sereja, Ukraine). Sergey prepared and conducted 7 rounds (all of them Div1+Div2) on Codeforces. Sergey's problems gained popularity among the Codeforces coders and we will be happy to see his contests again in the future! Sergey has already been awarded by a Medal and an Award Plate in February in Kharkov training camp.

Looks like it's becoming a good tradition. The laureates will be sent a book by Thomas Cormen (Introduction to Algorithms or Algorithms Unlocked), signed by the author.

History

Let us remind you that the Cormen medals have been awarded for the fourth year. tourist (Gennady Korotkievich) became the best participant three years in a row (in all the years when this nomination existed). Alex_KPR (Alexander Kouprin) became the best blogger in both years when this nomination existed. My favourite nomination "Best Problemsetter" was awarded to: natalia (Natalia Bondarenko) in 2010, Ripatti (Artyom Ripatti) in 2011, and witua (Vitaly Gerasimov) in 2012. Besides, in 2012 there was a medal for "Codeforces Spirit of Community 2012", the laureate was Nickolas (Mariia Mykhailova).

https://get.google.com/albumarchive/pwa/114907919772955385569/2014CoderStrike?authuser=0&feat=directlink

Hello,

Once again I'd like to host unusual unrated round. With your help we want to test untypical scoring system and unusual problems.

The contest will start today on 18:30 (UTC). We will add large and bright special link to enter into the contest area. The contest duration is 90 minutes. But it will be easy problems and hope that many participants will solve all of them before the end.

Go to the Contest →

It will be two types of problems: logic puzzles and programming tasks.

A logic puzzle is a task that is designed to be solved by hand (but it is not forbidden to write some helper code to do this). Each logic puzzle consists of one or more tests. Each question can be answered separately from the others. There is a "Submit" button below each test. To answer the question, press "Submit" button. Your answer will be acknowledged and checked after the end of the contest. You can change your answer any number of times – only the last attempt is checked. For the correct answer to the question you will get the number of points which is indicated in the question description.

A programming task is which you usually see in Codeforces rounds. Solutions can be submitted at any time during the contest. A solution is evaluated on a fixed set of tests right after it is submitted. For each passed test, a contestant will get a fixed amount of points. The sum of points for all passed tests is the total points received by the solution. The contestant can submit a solution several times. The contestant will receive points for only one solution per problem. The solution with the maximum amount of points will be chosen.

If a pair of contestants have the same number of points gained in contest time, they will be ordered according to the time (in seconds) of the last submission which gave them an improved positive score.

For each programming task, we will consider only the best submission (or if there are many submissions which are equally correct, the earliest). For logic puzzles, we will judge last submission per test.

In other words, it's always safe to submit a new answer for programming tasks (you can only improve your situation). It is not always safe to do that for logic puzzles – consider carefully whether or not you want to do that (you may replace correct answer with incorrect).

Many thanks to all of you who will help. Waiting for your feedback in comments.

The round will start on 08:00 (UTC) of April, 13. It will be a kind of unusual round because at first for a long time Gerald didn't work much on round. It was prepared by me (how it is interesting to write a round!), Nerevar with the help of Gerald and Fefer_Ivan-а. Maria, many thanks for translations!

It will be classical points: 500 — 1000 — 1500 — 2000 — 2500.

Hi!

I think everybody can remember a case when

Probably everyone remembers in practice a case when after implementation of correct algorithm you receive Wrong Answer. In such a situation, sometimes works: to send solution on another compiler.

Gerald and Nerevar have found severe bug, which gives one more argument to use the rule above.

Look closely, now it will be a miracle! 

Some months ago we've found that YuukaKazami took part in contests using one more account. We've contacted him and he pleaded guilty and deplored about it. That acccount has been banned and YuukaKazami was disallowed to take part in rounds for two months.

Now he can take part and we hope to see him again in standings.

About two days ago Java 8 has been released! It is a great update with many interesting improvements and features. If you do not plan to use new language syntax, probably Java 8 will please you with performance improvements.

I've added Java 8 with options like for other versions of Java: java.exe -Xmx512M -Xss64M -DONLINE_JUDGE=true -Duser.language=en -Duser.region=US -Duser.variant=US -jar %s.

Right now, Java 8 supported in testing mode. Let's try it together on problemset problems.

You may see new features in this code — it sorts lines in non-increasing lexicographical order:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            List<String> lines = new ArrayList<>();
            while (scanner.hasNextLine()) {
                lines.add(scanner.nextLine());
            }
            lines.stream().sorted((a, b) -> b.compareTo(a)).forEach(System.out::println);
        }
    }
}

On 02.03.14 there was a serious technical failure: Codeforces and related infrastructure hard drives have been corrupted. Unfortunately, it turned out that in contrast to all other components, the Codeforces database was not replicated properly. Polygon and Gym files were not injured. However, the Codeforces data has been significantly damaged.

We've rolled back the system to the state on February 7. It will remove 22 days of Codeforces life. Immediate efforts will be directed at the total exclusion of such situations. This is a very serious loss for me personally, which I can only blame myself.

Many thanks for all of you who supported us on a temporary Codeforces page. You helped much to find motivation in this difficult situation.

Currently the Gym is disabled. It will be opened back soon. We will return official contests and gym trainings with problems (but not results).

Data to be recovered:

• official contests with problems (but without results);
• public trainings in Gym;
• non-public trainings in Gym, but we do not know their owners — write me if you've prepared non-public training in Gym (not a mashup).

Sorry again for the inconvenience.

The contest Testing Round 9 is a special contest to test recent Codeforces internal improvements. Please, take part in it to help us to be ready for Codeforces Round 224 (Div. 2).

The Testing Round 9 will be completely unofficial and unrated. We will use problems from some Saratov contests, they will be new for many of you.

If you see any issues in Codeforces behaviour, write a comment here.

Thank you!

UPD. The contest completed. Thanks to all the participants.

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.

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! Do you feel the breath of New Year?

The clock shows a day before New Year, so it is time to sum up the past. I do not have speech-writers for words in the style of "what recently seemed almost impossible, it becomes a fact of life" so I'll be short. Thank you all! Your unfading interest and constant help inspire Codeforces team for new achievements! Brilliant writers, invisible soldiers: testers, tireless and greedy for knowledge participants — all of you help Codeforces do better!

I've dug into the records and made a partial list of the most notable major improvements of 2013. Some large improvements of our infrastructure are not in the list, as the community can not see them directly.

• A simple way to add contest from Polygon to Codeforces::Gym.
• Drafts embedded in text form fields in Codeforces and Polygon.
• Multiple interface improvements in the contest area.
• Many improvements of Testlib.
• Notably improved performance of Polygon on large manual tests.
• Repeatedly updated compiler versions to the nearly latest.
• Supported languages: MS C#, Python 3, Go, JavaScript V8.
• Updated Codeforces testing servers.
• Polygon supported HTTPS.
• Organized the first season of weekly Codeforces trainings 12 episodes.
• Supported organizations in the profile and rating of organizations.
• Added numerous contests to Codeforces::Gym. Probably the most valuable — a large number of Andrew Stankevich Сontests.
• Implemented checker and validator tests in Polygon.
• Implemented macro language support in test scripts in Polygon.
• Groups on Codeforces have appeared, they can contain contests and blogs.
• Introduced Mashup Contests — special contests for personal and group training, can be easily composed by problems from rounds or from Polygon.

In addition, in 2013 we not only hosted 64 classical Codeforces rounds, but hosted some tournaments:

• Croc Champ 2013
• MemSQL start[c]up
• ABBYY Cup 3.0

Also we took a role of ACM-ICPC 2013 World Finals Press Partner!

And as the detective story can not be without a chase, and the annual report can be do without the fun pictures. Here is a series of images showing the growth of Codeforces:

I've found some time to support JavaScript, which is so popular now. I chose V8 as the most developed implementation of JavaScript.

With the help of a tambourine and a liter of cola I successfully compiled it on Windows. Funny, I was ready to implement workaround to support reading from stdin in JavaScript, but d8 already supports it! Just use readline() to read line from the input.

Here is an example of A+B:

var line = readline().split(' ')
print(parseInt(line[0]) + parseInt(line[1]))

Interesting fact, that if there is no line-break (\r\n) at the end of line, then readline() returns undefined. So it is one more reason for good rule: each line should end with eoln.

As a tiny research I've implemented HeapSort on C++, Java and JavaScript. I have an opinion that all dynamic typed languages are very slow. But...

I've implemented HeapSort on 10⁷ elements from 0 to 9999999. I think it is good benchmark to show how fast can be your code if you write like in Pascal or pure C. The result have surprised me:

JavaScript shows very good performance! I understand that such kind of code is very good for optimization and jit-compilation, but I'm impressed. By the way, Java with its optimized JIT is not as good as it can be.

Actually, I posted the codes in github. You may implement the same algorithm on your favorite language. Here are links to current implementations:

• С++
• Java
• JavaScript
• Pascal
• Python 2
• Python 3
• Ruby
• Scala
• Go
• D
• C#

You may post links to pastebin in comments or give submission id. Better to do a pull request.

If you are planning to write implementation, please write it neat and tidy. Write it as closer to the C++, Java and JavaScript as possible.

UPD 1. With the help of alexei-zayakin, Pascal has been added.

UPD 2. With the help of gchebanov Wizmann and juancate I've added Python 2, Python 3, Ruby, Scala, Go.

UPD 3. Here is V8 (Windows binaries).

UPD 4. I've updated some compilers and the benchmark results.

UPD 5. Added D. Thanks Gassa.

UPD 6. Added C#. Thanks gmogelashvili.

The tutorial has been prepared by Fefer_Ivan and NALP.

371A - K-Periodic Array

For array to be periodic, elements 1, 1 + k, 1 + 2 * k, … must be equal. Also, elements 2, 2 + k, 2 + 2 * k, … must be equal. And so on up to k. So each element of the array is a part of exactly one group. And there are k groups total. Each such group is independent. Let’s consider some group of elements, that contain a ones and b twos. All elements in this group must be equal. So we either change all ones to twos or all twos to ones. First option will require a changing operations and second one — b changing operations. For the optimal solution, you should select the operation with smaller number of changing operations required.

371B - Fox Dividing Cheese

It is easy to see that the fox can do three type of operations: divide by 2, divide by 3 and divide by 5. Let’s write both given numbers in form a = x·2^a₂·3^a₃·5^a₅, b = y·2^b₂·3^b₃·5^b₅, where x and y are not dibisible by 2, 3 and 5. If x ≠ y the fox can’t make numbers equal and program should print -1. If x = y then soluion exists. The answer equals to |a₂ - b₂| + |a₃ - b₃| + |a₅ - b₅|, because |a₂ - b₂| is the minimal number of operations to have 2 in the same power in both numbers, |a₃ - b₃| is the minimal number of operations to have 3 in the same power in both numbers, and |a₅ - b₅| is the same for 5.

371C - Hamburgers

Let's use binary search approach. For given number of hamburgers (say, x) let's find the minimal number of money needed to cook them. Say, for one hamburger Polycarpus needs c_b bread pieces, c_s sausages pieces, c_c cheese pieces. So for x hamburgers he needs: c_b·x, c_s·x and c_c·x pieces (by types). Since he already has n_b, n_s and n_c pieces, so he needs to buy:

• bread: max(0, c_b·x - n_b),
• sausages: max(0, c_s·x - n_s),
• cheese: max(0, c_c·x - n_c).

So the formula to calculate money to cook x hamburgers is:

Obviously, the function f(x) is monotonic (increasing). So it is possible to use binary search approach to find largest x such that f(x) ler.

371D - Vessels

The naive solution for this problem will work like this. Let us store an amount of water in each vessel in some array v. If we need to know how much water is in some vessel, we just take the number from the array. If we need to pour x units of water into vessel number i, we must follow the simple procedure: 1. If x = 0 then all water is poured and we must end the procedure 2. If i > n then all remaining water is spilled on the floor and we must end the procedure 3. If x units of water can fit into the i-th vessel, then add x to v[i] and end the procedure 4. Fill i-th vessel completely and subtract used amount from x. 5. Assign i = i + 1. 6. Go to the first step.

In the worst case scenario such procedure can iterate through all vessels each time. For example, if there are n vessels and each vessels have capacity of one unit of water, each query like 11n will take O(n) time to process.

To make this solution faster we should notice, that once completely filled, vessel can be skipped during the algorithm above because it can not consume any more water.

So instead of i = i + 1 assignment should be like i = findNextNotFilledVessel(i).

To implement this function we can use different structures. For example, we can use sorted set of numbers (set in C++, TreeSet in Java). Let store the set of indices of unfilled vessels. So to find next not filled vessel from i-th vessel, we must find smallest number, that is contained in set and is strictly greater than i. There are built-in methods for it (upper_bound in C++, higher in Java).

Also, each time we fill the vessel, we must erase corresponding index from the set.

So now we can see, that algorithm can not complete more that O((m + n)logn) operations for all queries. Because on each iteration of the pouring procedure either the vessel is filled (which can only happen n times during the whole runtime), or we run out of water (or vessels) and the procedure is stopped. So there will be only total of O(m + n) iterations of the pouring procedure and each iteration require one lookup in the sorted set, which takes O(logn) operations. So the total number of needed operations is O((m + n)logn).

371E - Subway Innovation

It is easy to see that you need to minimize the sum of pairwise distances between k stations. The main idea to do it is to sort them and the required stations will form a continuous segment. It is easy to prove by contradiction.

Huge constraints do not allow to use straight-forward method to find required segment. Let’s call f(i, k) — sum of pairwise distances of k stations starting from the i-th. To find f(0, k) you need to start from f(0, 0) = 0 and use transformation from calculated f(0, i) to f(0, i + 1). You can use equation:

where sum(l, r) means x_l + x_l + 1 + ... + x_r. We can precalculate sum[i] = x₀ + x₁ + ... + x_i and use equation sum(l, r) = sum[r] - sum[l - 1] to find sum(l, r) in O(1).

Actually we need f(0, k), f(1, k) and so on (and find minimal value among them).

To recalculate f(i, k) to f(i + 1, k) you need exclude x_i and include x_i + k. Using the method like in the previous paragraph: f(i + 1, k) = f(i, k) - (sum(i + 1, i + k - 1) - x_i·(k - 1)) + (x_i + k·(k - 1) - sum(i + 1, i + k - 1)).

Please take a notice that recently the schedule has been changed. Twice.

Greetings to the Codeforces community!

I'm glad to announce that we again decided to introduce a round based on one of the programming olympiads for schoolchildren in Saratov. This time it is a round for participants from Division II. Round will start at unusual time for Codeforces: Dec. 7, 07:00 UTC.

The problems were prepared by employees and students of Programming Competitions Training Center of Saratov State U.

Members of the first division can participate out of competition, as usual.

Currently we are planning to use dynamic scoring system.

UPD: Moved from 09:00 to 07:00 because of Kotlin Challenge.

UPD 2: Tutorial has been published.

Tomorrow (December, 1st) at 06:00 (UTC) Northeastern European Regional Contest 2013 will start. Use the link to view the current stangings during the contest.

The contest will take place in four cities at the same time: Saint-Peterburg, Barnaul, Tbilisi, Tashkent. Looking to the standings of the practice session it is clear that totally 235 teams will fight for the honour to take part in the Finals.

NEERC takes place since 1996. Here are NEERC Champions:

I wish all the teams to show their strongest sides. Good luck!

P.S. For sure, I will be rooting for Saratov State University. You know well our leading team: Gerald, Fefer_Ivan, kuviman.

P.S. The contest finished. My congratulations to:

• The 1st place: SPb SU 4 (Kunyavskiy, Egorov, Suvorov)
• The 2nd place: Moscow SU 1 (Pyaderkin, Evstropov, Omelyanenko)
• The 3rd place: Saratov SU 1 (Agapov, Fefer, Kudasov)

The complete standings are here.

Welcome to 2013-2014 CT S01E012: Codeforces Trainings Season 1 Episode 12. 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.

The registration will be available on the Gym page and will be opened until the end of the training. Be careful registering team: please, choose only whose members who will take part in the contest.

Please do not take part in the contest if you have already solved the contest problems before.

Good luck!

Welcome to 2013-2014 CT S01E011: 2013-2014 ACM-ICPC East Central North America Regional Contest (ECNA 2013). 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.

The registration will be available on the Gym page and will be opened until the end of the training. Be careful registering team: please, choose only whose members who will take part in the contest.

Please do not take part in the contest if you have already solved the contest problems before.

Good luck!