By NALP, 7 years ago, translation, In English,

Dear friends!

The next competition - Codeforces Round 101 for participants Div2 will take place through a pair of hours, but the others can traditionally participate out of competition. It has been prepared by a small command of authors: me (NALP), Polina Bondarenko (Polichka) and Gerald Agapov (Gerald). There were Artem Rahov (RAD), Maria Belova (Delinur) and Michael Mirzayanov (MikeMirzayanov) with us as always.

It is a little bit about authors: all of us study at the Saratov State University at faculty of Computer Sciences and Information technology on 4th course. Now in free time from competitions and problems we pass the exams :) I’m a 1/3 part from command Saratov SU#2, and Gerald with Polina - 2/3 from Saratov SU#1. We would like our rounds became kind tradition on Codeforces and you have seen us among authors soon again.

We hope that this problems will be pleasant to all participants and everyone will take the deserved high place in the total table. Today you will help Santa Claus, Elf, Vasya and the other characters. All the similarities to real people are casual :)

The points on problems are distributed today in this way: 500-1000-2000-2000-2500

UPD: You can read the tutorial here.

UPD: Thanks all for participation! The round has turn out difficult enough and only one person among all participants (including Div. 1) has solved all offered problems - akim239. Our congratulations for him!!

UPD: our congratulations for Top-10 participants in competition:
3. frp
6. hex539
7. not
10. ggbuaa

Read more »

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

By natalia, 7 years ago, translation, In English,

Hello everybody!

I hope you have finished New Year celebrations, or you are ready to make a small break to take part in the anniversary Codeforces Round #100. Round will have place January 4 at 15:00 (UTC). There will be a common contest for participants of the both divisions with the same set of 6 problems. The top 100 participants of the contest receive prize t-shirts.

Score distribution: 500-1000-1500-2000-2500-3000 

As you may have guessed, the author of the problems is me. Invaluable help in preparation (and a bit in inventing) of problems was provided by Artem Rakhov (RAD) and in translation of the problem statements into English by Maria Belova  (Delinur).

Under the influence of my festive mood, the problem statements turned out to be about different characters celebrating New Year. All characters and events are fictional, please take any resemblance as completely coincidental :) 

The contest is over. Codeforces team and I personally want to thank all who take part in the greatest round in Codeforces history! Much to our surprise, the 100th place was shared by two contestants: pooya_ and Timur_Sitdikov. Of course, they both will receive prize t-shirts as all others who took higher places. Prizewinners will receive special emails.

Congratulations to the winners:

1. Egor
4. Petr
6. e-maxx
9. Coder

Read more »

Announcement of Codeforces Round #100
 
 
 
 
  • Vote: I like it  
  • +314
  • Vote: I do not like it  

By MikeMirzayanov, 7 years ago, translation, In English,

Hello

We've scheduled Codeforces Testing Round #4 on January, 3 15:00 (UTC). It will be non-rated event, just to test system before important Codeforces Round #100. The round duration is 1 hour and it will contain just two problems. I do not promise something interesting and exciting, but as a small warm-up will be nice :)

I'll be glad to see you on the round,
MikeMirzayanov

The testing is successfully completed. Thank you for participation. I hope you like this sprint.

Read more »

Announcement of Codeforces Testing Round #4
 
 
 
 
  • Vote: I like it  
  • +92
  • Vote: I do not like it  

By MikeMirzayanov, 7 years ago, translation, In English,

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

Read more »

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

By MikeMirzayanov, 7 years ago, translation, In English,

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)

Read more »

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

By MikeMirzayanov, 7 years ago, translation, In English,

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

Read more »

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

By Endagorion, 7 years ago, translation, In English,

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.

Wish you luck. Have fun during the contest and show your best.
Happy new year! =)

UPD:
Round finished. Thanks everybody! Hope you enjoyed it.
Winners:
Div1:
1. ivan.popelyshev
2. al13n
3. WJMZBMR
4. yeputons
5. romanandreev
6. dolphinigle
7. wata
8. Shef
9. shangjingbo
10. azizkhan

Div2:
1. s-quark
2. wayne-ho
3. emrevarol
4. agh
5. lzqxh

Due to some techinical problems, server was unavailable for few minutes before the end of the contest. Out of two unpleasant options: make the round unrated or stay as it is, we choose the second one as it affects the less number of contestants. We apologize to those participants who are affected by this.

UPD2: Editorial is finally translated.

Read more »

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

By Edvard, 7 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).

Read more »

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

By Edvard, 7 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!!!

Read more »

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

By KADR, 7 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).

Read more »

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