By Edvard, 11 years ago, translation, In English

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).

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +23
  • Vote: I do not like it

By Edvard, 11 years ago, translation, In English

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)

3. stx2

Congratulations to winners!!!

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +141
  • Vote: I do not like it

By KADR, 11 years ago, translation, In English

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)


In this problem one had to read a permutation and output the inverse permutation to it. It can be found with the following algorithm. When reading the i-th number, which is equal to a one can store i into the a-th element of the resulting array. The only thing left is to output this array.

The complexity is O(N).

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +87
  • Vote: I do not like it

By KADR, 11 years ago, translation, In English
Hello everyone!

Codeforces Beta Round #97 will take place on Friday, December 9th at 19:00 MSK. This will be my second classical Codeforces round and I hope it won't be the last one :)

I'd like to thank maksay, Shtrix, it4.kp, RAD and Delinur for their help in preparing contest, testing problems and translating them into English.

Good luck!

UPD: Due to technical reasons the round start time is shifted 5 minutes forward.

UPD 2: Due to the large number of participants and large number of tests the testing will finish not soon.

UPD 3: The testing is over. Thanks for participation! I apologize for a very long testing process.

The winners:

UPD 4: The editorial is released.

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +237
  • Vote: I do not like it

By Nickolas, 11 years ago, translation, In English

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.

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +58
  • Vote: I do not like it

By Nickolas, 11 years ago, translation, In English

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.

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +135
  • Vote: I do not like it

By ag45root, 11 years ago, In English

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

Full text and comments »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By MikeMirzayanov, 11 years ago, translation, In English

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!

MikeMirzayanov

Full text and comments »

Announcement of Codeforces Testing Round #3
 
 
 
 
  • Vote: I like it
  • +81
  • Vote: I do not like it

By MikeMirzayanov, 11 years ago, translation, In English

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!

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +92
  • Vote: I do not like it

By MikeMirzayanov, 11 years ago, translation, In English

Hello!

On Friday, November 25 at 19:00 I'm waiting you on the Codeforces Beta Round #95 (Div. 2). This round is prepared by me. It is not easy to prepare a round, but it is always useful and interesting. By my example, I want to hint to top participants that rounds of famous people — it's always interesting!

Apart from me RAD, Nickolas and Delinur were doing work on the round. Moreover, Edvard still do not know, but very soon I will ask him to solve this round as a tester:)

It will be unusual round because you will find six problems. It's a little experiment — I hope that it will help each participant to find interesting problems to themselves.

I believe that the out-of-competition participants from Div.1 will have some fun solving the round.

The problem scoring is: A - 500, B - 1000, C - 1500, D - 2000, E - 2500 and F - 2500.

Good luck!

MikeMirzayanov

UPD. The competition has ended. Here are the results. First place was taken by the representative of China — liuq901. Congrats! It was nice to see such interest to the contest. Thank you for your participation!

Unfortunately, I do not have the opportunity to write a tutorial. If you deal with it I will be grateful.

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +75
  • Vote: I do not like it