By Morphy, history, 8 years ago, In English

Codeforces Round #328 (Div. 2) will take place on October 31, 19:30 MSK, as usual Div. 1 participants can join out of competition.

Problem Setter: Morphy (Alei Reyes)

Coordinator: GlebsHP (Gleb Evstropov)

English to Russian translator: Delinur (Maria Belova)

Codeforces and Polygon: MikeMirzayanov (Mike Mirzayanov)

Hope you enjoy the problem set.

The score distribution will be announced later.

UPD. Score Distribution: 500 — 1000 — 1500 — 2000 — 3000

UPD. Problem Analysis is available

Congrats to the winners!

Div. 2

 shamir0xe

 lbn187

 SuperLoser

Div. 1

 uwi

 NanoApe

 Haghani

Full text and comments »

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

By MikeMirzayanov, history, 8 years ago, translation, In English

Starting from October 2015 ratings formulas are open. They are given in the post. It is likely that from time to time we will change them slightly, it will be reflected here.

The basic idea of Codeforces rating system is to generalize Elo rating to support games with multiple participants.

Each community member is characterized by value ri — integer number. Roughly speaking, the higher value means better results in the contests. Rating is calculated/recalculated so that the equality strives to be correct:

where Pi, j is probability that the i-th participant has better result than the j-th participant. Therefore for two participants the probability to win/lose depends on subtraction of their ratings. For example, if the difference of ratings is equal to 200 then stronger participant will win with probability ~0.75. If the difference of ratings is equal to 400 then stronger participant will win with probability ~0.9.

After a contest the values ri change in a way to satisfy main formula better.

Let’s calculate expected place seedi for each participant before contest. It equals to the sum over all other participants of probabilities to win (to have better place than) the i-th plus one because of 1-based place indices:

For example, before Codeforces Round 318 [RussianCodeCup Thanks-Round] (Div. 1) tourist had rating 3503 and his seed was ~1.7, and Petr had rating 3029 and expected place ~10.7.

General idea is to increase ri if actual place is better than seedi and to decrease ri if actual place is worse than seedi.

Having seedi and actual place, let’s calculate their geometric mean mi. You can think about it as an something average between seedi and actual place shifted to the better place. Using binary search find such rating value R which the i-th participant should have to have a seedi = mi. Obviously the rating ri should be modified to become closer to R. We use di = (R - ri) / 2 as rating change for the i-th participant.

It's almost all except the phase of fighting against inflation. Inflation works as follows: the rich get richer. We will try to avoid it. If we assume that the rating was already calculated fair (i.e. everybody has perfect statistically based rating) then expected change of rating after a contest is equal to zero for any participant.

Choose a group of the most rated (before the round) participants and decide that their total rating shouldn’t change. We use heuristic value as a size of such group. Let’s find the sum of di over participants from group and adjust all values di (for all participants) to make the sum to be zero. In other words, ri = ri + inc, where inc =  - sums / s, sums is sum of di over s participants from chosen group.

After the round 327 we restricted the effect in following way. Firstly, we do ri = ri + inc, where inc =  - sum(di) / n - 1, sum(di) is sum of all di. It makes the sum of all di to be near zero and non-positive in the same time. Secondly, we apply idea from the previous paragraph, but inc = min(max( - sums / s,  - 10), 0). Thus, the effect of modification can not reduce rating for more than ~10 points.

By the way, for any consistent rating the following assertions should be true:

  • if the participant A had worse rating than the participant B before the contest and finished the contest on the worse place then after recalculations the the rating of A can’t be greater than the rating of B
  • if A finished the contest better than B but A had worse rating before the contest then A should have equal or greater rating change than B.

In particular, formulas are tested to satisfy the both items on each ratings recalculation.

You may read the actual Codeforces code to recalculate ratings here: 13861109.

Full text and comments »

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

By GlebsHP, 8 years ago, translation, In English

Hello, dear participants of Codeforces community!

Starting from Codeforces Round #327 I'll be the new coordinator and will manage preparation process for all regular Codeforces rounds and other contests held on this platform. I'll do my best to increase the quality of contests we offer you, though Zlobober already raised this bar high. Let's cheer him once again, for all the great job he had done!

Tomorrow round will be held using the problems of Moscow team olympiad for high-school students. Do not be tricked by the word "school" — there will be a gold medalist of IOI 2015 participating and some candidates to this year Russian IOI team, meaning the level of the problems will be appropriate. I am sure everyone will find an interesting problem to enjoy.

The problemset was prepared by the team of Moscow authors (list is incomplete): Zlobober, romanandreev, meshanya, wilwell, glebushka98, timgaripov, thefacetakt, haku, LHiC, Timus, Sender, sankear, iskhakovt, andrewgark, ipavlov, StopKran, AleX leaded by your humble servant GlebsHP and the chairman of the jury Helen Andreeva.

Special thanks to Delinur for translation and stella_marine for correction.

Five problems will be offered in both divisions and the scoring distribution will be announced later (good traditions should live).

UPD. Round time. Please note that Russia is not changing the timezone this night, while about 100 countries do so. Be sure to check when round starts in your timezone!

UPD2. Please note, that the distribution motivates you to read all the problems! Div1.: 750-1000-1250-1750-2500 Div2.: 500-1000-1750-2000-2250

UPD3. The results and the editorial will be published later, after the closing ceremony of the official competition.

UPD4. The system testing is over, results are now final. Feel free to upsolve and read other contestants code. Congratulations to Div. 1 top-5:

  1. Endagorion
  2. JoeyWheeler
  3. sdya
  4. RAD
  5. -XraY-

UPD5. Problem analysis is now available.

Full text and comments »

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

By gen, 8 years ago, In English

Hello, Codeforces!

I'm glad to invite you to participate in the online mirror of the Baltic Selection Contest for ACM ICPC 2015–2016 that will take place in Gym on the 22nd of October, 13:00 UTC.

This competition determines the best teams throughout the universities of Latvia, Lithuania and Estonia that will participate in ACM ICPC NEERC Western subregional contest in Minsk, Belarus. The onsite contest was held on the 12th of October. The participating universities were University of Latvia, Vilnius University, Kaunas University of Technology, Vilnius Gediminas Technical University, Estonian Information Technology College and others.

As a bonus, I'm posting some photos of the onsite action at University of Latvia. :)

The top 5 teams at the onsite competition were:

  1. LU: 64428b862de0207ba0385b1ed2df43e1 (Alex_2oo8, zmad)
  2. VU: 2B||!2B (vstrimaitis, jDomantas, JustasK)
  3. LU: 0x7DF (Pakalns, Candyman, A_Le_K)
  4. LU: leet (Instasamka, how_to_become_purple, JustN)
  5. KTU #1 (wi_lius, lukgar, ASBusinessMagnet)

The detailed onsite standings will be posted after the contest.

The problems were prepared by a group of authors from University of Latvia: gen, KarlisS, andreyv, cfk.

Good luck & have fun!

Full text and comments »

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

By MikeMirzayanov, history, 8 years ago, translation, In English

You may print PDF-statements: http://assets.codeforces.com/statements/589.pdf

Recently 2015-2016 ACM-ICPC, NEERC, Southern Subregional Contest has been finished. On behalf of jury and hosts I congratulate winners and advancers to the semifinals. Prize places are (horray!):

  • 1 place: Nizhny Novgorod State University #1 (Vladislav vepifanov Epifanov, Nikolay KAN Kalinin, Mikhail mike_live Krivonosov)
  • 2 place: Innopolis University #1 (Evgeniy savinov Savinov, Sergey sokian Kiyan, Alexander map Mashrabov)
  • 3 place: Saratov State University #1 (Edvard Edvard Davtyan, Vitaliy kuviman Kudasov, Danil danilka.pro Sagunov)

On Saturday (October, 17) в 08:00 (UTC) we will host unofficial online mirror. Interesting problems are waiting for you. Judges tried to prepare problems of wide difficulty range: for newcomers and for expirienced teams. This will be a team/personal contest on Codeforces, with teams consisting of up to three people or individual participants. The contest will not affect Codeforces ratings.

For sure, it will be unrated contest. We recommend you to take part in teams. I think, the contest will be moved to Gym later.

Good luck!

MikeMirzayanov, head of judges.

P.S. We are aware that this mirror will overlap with some other online tournaments, but unfortunately we are unable to change the current time slot, due to the online mirror of the Moscow Subregional of NEERC scheduled on Sunday. All school teams are recommended to pay attention to Online-mirror of the Ural regional team championship.

Full text and comments »

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

By PrinceOfPersia, history, 8 years ago, In English

Hello Codeforces.

I'm honored to announce you, that Codeforces round #326 is gonna take place soon on Codeforces.

Writers are AmirMohammad Dehghan(PrinceOfPersia) and Ali Haghani(Haghani). There will be 6 problems in each division(4 problems are common) and you'll have 2 and a half hour to solve them. I hope you enjoy the problems.

I wanna thank Maxim Akhmedov(Zlobober) for his great helps in preparing this round, MikeMirzayanov for wonderful platforms of Codeforce and Polygon, Delinur for translating problem statements into Russian and MohammadReza Maleki(mruxim) and Ali Bahjati(LiTi) for their great advices (and LiTi again for some graphics).

This is my third round on Codeforces and not the last one, I hope.

This is the last round on Codeforces with Zlobober as coordinator. It was nice working with him. We had a lot of fun and interesting contests during his coordination. I just wanna say: Thank you Maxim for all your contribution to CodeForces community and good luck in the future. After I heard these news, my first guess for the next coordinator was I_love_Tanya_Romanova; But I don't know if CodeForces hires people from out of Russia or not.

The main character of this round is Duff, but you'll also have to help her friend, Malek!

I wish you all high ratings and lots of joy.

Scoring will be posted soon.

GL & HF!

Problems are sorted by the expected difficulty, but we strictly recommend you to read all the problems.

UPD: Scoring is: 750-1000-1500-2000-2500-3000 in Div.2 and 500-1000-1500-2000-2750-2750 in Div.1 .

UPD1: Editorial is published.

UPD2: System test is over. Congratulations to all winners.

Div.1 Winners are:

  1. qwer1561
  2. Endagorion
  3. jcvb
  4. subscriber
  5. wjh720

Div.2 Winners are:

  1. sleepy_mario
  2. BIT-silence
  3. Owaski
  4. Orenji.Sora
  5. JavaInTheSouth

Also congratulations to JoeyWheeler, the only one who solved problem Div.1 D.

Full text and comments »

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

By Edvard, history, 8 years ago, translation, In English

Hi, Codeforces!

Codeforces Round #325 will take place on October 12, 2015 at 09:00 UTC for the first and second divisions. Please note that the round will start at unusual time!

The problems of this round are taken from the Regional stage of the All-Russian school team programming olympiad that will be at the same time in Saratov, Russia. Lets wish school teams good luck on competition!

The problemset for school olympiad differs from problems that will be on round. In addition in problemset for school olympiad there will be some problems, which are not included in the round and vice versa. So don't be frightened by the difficulty of problems given for school teams :-)

The process of problems preapring was very interesting: we were reworking problem statements many times, adding tests, changing limits, even managed to change fully prepared problem with another (we had to stop the conveyor already printing problem statements :-)) Let's thank all who were preparing, helping in preparing, reading the problem statements, writing solutions: Adilbek adedalic Dalabaev, Roman Roms Glazov, Vladimir vovuh Petrov, Oleg Oleg_Smirnov Smirnov, Alexey Perforator Ripinen, Maxim Neon Mescheryakov, Ilya IlyaLos Los, Vitaliy gridnevvvit Gridnev, Danil danilka.pro Sagunov, Alexander fcspartakm Frolov, Pavel HolkinPV Kholkin, Igor Igor_Kudryashov Kudryashov, Elena elena Rogacheva, Dmitriy Nerevar Matov, Vitaliy kuviman Kudasov. Chairman of the jury of the Olympiad is Mikhail MikeMirzayanov Mirzayanov (also he is the author of some of tasks). I (Edvard Edvard Davtyan) prepared some tasks and coordinated the work of the authors. So we are a large team of writers (I hope I did not forget anyone)!

Also let's thank Max Akhmedov (Zlobober), The-One-Who-Must-Not-Be-Named (if I am not wrong, he or she is right now solving the round problems) for their help in problems preparing, Maria Belova (Delinur) for translating problems in English and again Mikhail Mirzayanov (MikeMirzayanov) for the Codeforces and Polygon systems.

You will have only two hours to solve six problems. The scoring distribution will be anounced a little before the round. I wish high rating to all participants! Good luck and have fun!

P.S.: Also I want to wish good luck to the participants of the ACM ICPC Southern Subregional Programming Contest that will be held on Wednesday.

UPD Due to technical reasons round is delayed by 10 minutes.

UPD: In problem Subway roller there were tests with trains of length one. At this moment authors are discussing how much it troubled the round results. We are apologize to participants who had problems with that. We will announce our decision about this problem soon.

UPD2: There were trains with length equal to one in tests for problem Subway Roller. Jury decided to accept the first right solution of each user that passed all tests except the wrong, also other submissions were ignored. In addition we accept all successed hacks, although the hack is not correct and the hacked solution passed all other tests. Contest will be rated, but any user who think that this situation is cardinally affected to his/her result can send me in 24 hours a message and jury will discuss the question to make round unrated only for that participant. We are apologize to participants one more time for this situation.

UPD3: Editorial

Full text and comments »

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