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.

December 11, 2011 Youth Research Society "Q-BIT" and the Department of Information Systems, Kharkiv National Economic University, conducted a traditional Kharkov Open Championship on sports programming.

Registration for the competitions:

• for onsite participants to December 5, 2011
• for online participants to December 10, 2011
  

Stay tuned for news on the site http://qbit.org.ua!
More information about the championship on the official website of the Championship http://khcup.qbit.org.ua

Informal unrated contest Codeforces Testing Round #3 is scheduled on December, 2 (Friday), 15:00 (UTC). We will test the latest innovations on Codeforces that they do not affect the contests. If not, we will fix it quickly :) So, this round will take place "as is", no warranty about it.

Problems for the round may be famous to someone, but I'll try to make them such not for any of you. It will be 3-4 problems, as quite simple and something more tricky. The contest duratiuon is 1 hour.

I say thanks in advance to all those who will come and test the system. Thank you!

The ACM-ICPC Northeastern European Regional Contest 2011 is over. Congratulations to the winners! I especially want to mention the team that will represent our region on the World Finals in Warsaw:

1. SPb NRU ITMO 1 (Kapun, Kever, Nigmatullin) — 1-st place, champions
2. Moscow SU 1 (Fedorov, Kaluzhin, Rogulenko) — 2-nd place
3. Belarusian SU 1 (Bahdanau, Pisarchyk, Sobol) — 3-rd place
4. Saratov SU 2 (Ivanov, Kuznetsov, Rakhov)
5. SPb SU 1 (Andreev, Boykiy, Fondaratov)
6. Moscow IPT 1 (Dlugach, Gimadeev, Shishkin)
7. Ural FU 1 (Dolgorukov, Schelkonogov, Soboleva)
8. Altai STU 1 (Silin, Uvarov, Yesipenko)
9. Ufa SATU (Lezhankin, Mazgarov, Ripatti)
10. Nizhny Novgorod SU (Lyulkov, Shmelev, Vadimov)
11. Belarus SUIR 2 (Berezhnov, Brukau, Ropan)
12. Udmurt SU (Abizyaev, Kibardin, Urbanovich)
13. Latvian U 2 (Kalinicenko, Vihrovs, Vilcins)
14. Kazakh-British TU 3 (Aitbayev, Satylkhanov, Almakhan)
15. Tomsk SU 1 (Chadnov, Kolupaev, Afanasev)
16. Volgograd STU (Agafonov, Chalyshev, Zhorin)

Codeforces wishes all future World Finals participants the success in preparing for the competition and good results in the final!