Codeforces project congratulates everybody who is into sport programming with New Year! A New Year is not just an increment of a year. Let this day be a starting point to your new achievements, accomplishments and success. Codeforces wishes you to find out by the end of 2012 that all your resolutions have been a success! We wish you to have interesting problems, nice solutions, correct code and more and more of beautiful green messages  Accepted.

As well as in the previous year, we enable handle change for ten days. The handle change is available from the "Settings → Handle" tab from your profile page. Handle change will be disabled on January 10, so don't lose the moment!

Happy New Year, Happy New Coding!
MikeMirzayanov

Hi everybody!

The calendar shows the end of December — the year 2011 is about to end. It was an eventful and exciting time for us. You can find pictures below summarizing 2011 in comparison to 2010. In a nutshell, we've made it! We have grown in all parameters! This result is the shared victory of the well-united team. My special thanks go to the VK (VKontakte) and specifically — to Pavel Durov. The programmers' community and its development really matters to them. I want to thank the authors of the problems: preparing contests is tough and you are a significant help to the Codeforces project and to the whole community.

So, comparing the ending 2011 year and the 2010 year in pictures goes like this:

Codeforces users' growth throughout the Codeforces history (by months)

Hello, everybody.

New Year Holiday is a time of miracles and gifts! Quite by chance the 100th Codeforces round coincided with this wonderful moment.

So, January 4 at 15:00 (UTC) the anniversary Codeforces Round 100 will have place. Yes, we say goodbye to the word Beta in round titles :)

It will be a combined round, that is, participants Div1, Div2 and newcomers will compete with one set of problems. To make it interesting for each participant we plan to expand the round to 6 problems.

The most important thing: the best hundred participants of the 100th round will receive an exclusive Codeforces t-shirt!

Happy new year!
Codeforces Team

Hello.

Today round is prepared by me. My name is Mikhail Tikhomirov, i am fourth grade student at mech.-math. dep. of MSU, also i work as developer-researcher at Yandex.

I want to thank Artem Rakhov (RAD) for valuable help and thoughtful coordination, Maria Belova (Delinur) for great-as-always translating statements into English, and alsoMikeMirzayanov for letting us all get together today. =)

Round will be for both divisions. Every division will have five problems as usual, some of them will be the same, some will be not.

Score distribution:

Div1: 500-1000-2000-2000-2500.

Div2: 500-1000-1500-2000-3000.

Today round is the last round in 2011. I want to thank Codeforces team, everyone who invented, prepared or helped in preparing problems this or past years, and those, who help developing the project. Codeforces now is not just a platform for programming competitions, it is a place where everyone can learn something from another, get a bit of knowledge from more experienced fellows, become more advanced by solving contests and trainings, or just enjoy cool and beautiful problems.

Let's wish the Codeforces project good luck in development next year and long years of existence.

A. Postcards and photos

We will move from the left of string to the right. When we passed the whole string, or in the hands of us have 5 pieces, or current object is different from what we hold in our hands, we remove all the items in the pantry. The answer to the problem is the number of visits to the pantry.

The complexity is O(n).

B. Permutation

We can count the number of integers from 1 to n, which occur in sequence at least once. Then the answer is n minus that number.

The complexity is O(n).

C. History

Denote a[i], b[i] - ends of the i-th event. Let's sort pairs (a[i], b[i]) by a[i] and iterate over all pairs. Denote rg the maximal b[i] from already processed. If current b[i] < rg than we must increment answer by one. If b[i] > rg than we must assign rg by b[i].

The complexity is O(n logn).

D. Palindromes

Let's preprocess array cnt[i][j] - the minimal number of changes tha we must do to make substring from position i to j palindrom. We can easy calc cnt[i][j] with complexity O(n^3). Now we can calculate dynamic programming z[i][j] - minimal number of changes that we can do to split prefix of length i into j palindromes. In begining we must assign z[i][j] = infinity for all (i, j) and assign z[0][0] = 0. If we want to make updates from state (i, j) we must fix the length of j-th palindrom - len. We can update z[i + len][j + 1] by value z[i][j] + cnt[i][i + len - 1]. Answer to the problem is the min(z[n][i]), where n is the length of string and i from range [1, k].

The complexity is O(n^3).

E. Last Chance

Let's replace all vowels by -1 and all consonants by +2. Obviously substring from position i to j is good if sum in the substring [i, j] is nonnegative. Denote this sum by sum[i][j]. Obviously sum[i][j] = p[j + 1] - p[i], where p[i] is the sum of first i elements. Now for all i we want to find maximal j such that j >= i and sum[i][j] >= 0. For this let's sort the array of (p[i], i) and build segment tree on this array by i. Let's iterate over all p[i] in nondescending order. Obsiously for fixed i we have that j = max(index[i]), where index[i] is the index of i-th partial sum in nondescending order and i from range [x, n], where x is the position of the first partial sum with value p[i] in sorted array. Than we must update position i by value of negative infinity and update answer by j - i.

The complexity is O(n logn).

Hi everyone!!!

It remains less than 10 hours before Codeforces Beta Round #98 (Div. 2). This round was prepared for you by me, proposed the ideas of the problems. Traditionally, RAD made sure that there is no bugs and that the statements are normal, and Delinur translated the statements into English. Thanks to them!

If you decide to participate in the round you have to help the boy Polycarpus and his classmate Innocentius in all the difficulties they face. The more you help them, the higher you will be placed in the standing.

I hope the problems will be interesting not only for Div. 2 participants, but the participants rated higher than 1699.

I will continue the story about myself (beginning of story in the previous blog entry). Besides programming I love sports. Within a few years before I started writing code, I was seriously involved in rowing. And before that I was going in for almost all sports :-): karate, soccer, hockey and so much more interesting. Now I love (especially at the training camp) to play volleyball and table tennis. I decided to prepare this round despite the fact that during the past two weeks, much has changed inside Codeforces and I took part in this.

Following the fashion trends I have changed my avatar.

Good luck for all on the round!

UPD:

Contest is finished, results are final, ratings are updated.

Top 10 (Div. 2)

Congratulations to winners!!!

Here is the editorial of Codeforces Beta Round #97. If you have any questions or suggestions --- feel free to post them in the comments.

136A - Presents (A Div 2)

A. HQ9+

The problem described HQ9+ programming language and asked whether the given program will print anything. Given the extraordinary simplicity of the language, it was enough to check whether the program contains at least one of the characters H, Q and 9.

Codeforces Beta Round #96 will take place on Saturday, December 3rd, and it will be my first classical Codeforces round. To smoothen the transition between Unknown Language and known ones, I've made the problems of the round follow a certain topic, which is of course programming languages :-)

Thanks to MikeMirzayanov, maksay и RAD for their help in preparing this round.

Good luck!

P.S. Points cost for problems: division 1 — 500-1500-1500-2000-2500, division 2 — 500-1000-1500-2500-2500.