By Radewoosh, history, 27 hours ago, In English,

Hello, codeforces!

The community wants so the community gets it! :D Here it is, my very first blog about tasks and algorithms. At the beginning I've decided to post my entries on codeforces, maybe I'll switch to something different if it becomes uncomfortable.

To pour the first blood I decided to choose a task from one of the old ONTAK camps. Task's name is "different words". The statement goes as follows:

You are given n words (2 ≤ n ≤ 50 000), every of length exactly 5 characters. Each character can be a lowercase letter, an uppercase letter, a digit, a comma... basically, it can be any character with ASCII code between 48 and 122 (let's say that k is the number of possible characters). A task is to find all pairs of indexes of words which are . Two words are if they differ at all 5 corresponding positions. So for example words and are really different and words and are not, because in both of them the third character is . As there can be many such pairs (up to ), if there are more than 100 000 pairs, then the program should print that there are only 100 000 and print this number of pairs (arbitrary chosen).

Please, note that this task comes from the contest which took place a few years ago, so don't think about bitsets. :P

So, how can we attack this problem? At first, you may think about some meet in the middle. It turns out to be hard, even if you can come up with something with k3 in complexity, then it'll probably be multiplied by n. O(k5) is also too much. Inclusion-exclusion principle unfortunately also won't be helpful, as we want to find those pairs, not only count them, and working on sets of words won't be so effective.

The biggest problem is that k is big. If it'd be, let's say, up to 10, then it'd be solvable in some way, but I won't go deeply into this solution, cause it isn't interesting and k is of course bigger. But I've mentioned small k. Why couldn't we dream about even smaller k? If k would be up to 2 (so words would consist only of digits 0 and 1) then this task would be trivial. We'd just group words which are the same, and for each word its set of really different words would be the group with words where every zero is changed into one and vice versa. But again, k isn't small...

Buuuuut, we can imagine that it is! Let's say that we assume that characters with even ASCII characters are "new zeros" and characters with odd ASCII characters are "new ones". Then for sure if two words are really different with these assumptions, then they are really different without them, cause if they'd have this same character at some position, then this character would change into this same "new character". This allows us to find some pairs, unfortunately not all of them, but the way definitely looks encouragingly.

If we've found some of the pairs, maybe we should just try one more time? But how should we change characters now? Now comes an experience: if you have no idea what to do or you don't want to do some complicated construction, then just do something random! So we could randomly change every character into zero or one and then run our algorithm for k equal to 2 — match groups of opposite words. What's the probability for a fixed pair that we'd find it during one run of our algorithm? If we already know what we've assigned to each character of the first word, then on every corresponding position in the second word there should be a different character — for each position we have a chance, that this assigned character will be correct, so we have probability equal to that the whole word will match.

What's the number of needed runs? Looking at limits we can guess that it could be a few hundred. Let's calculate the probability of fail if we'd repeat algorithm 600 times. The probability that we wouldn't find some pair is equal to , the probability that we'd find it, of course, and finally, the probability that we'd find all of them (or some 100 000 of them) is equal to which is greater than 0.999, so it's definitely enough.

There is one more thing. Consider words and . They are really different. Let's say that we've assigned 0 to a. Then we have to assign 1 to b. Then we have to assign 0 to c. Then we have to assign 1 to a. So there is a problem... At first glance, it might look problematic, but it turns out that it's easy to fix it. We shouldn't just assign zeros and ones to characters. We should assign them to pairs (character, position). Then everything will go well.

Total complexity is something like O(n·600·log(n)), but we can get rid of the log factor by using hashmaps.

Sooooo, it's the end of my first blog, sorry if it's too long. I hope that you've found this task useful and interesting. What do you think about this format, what was missing, what was bad? It'd be great to see a feedback from you. See you next time! :D

Read more »

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

By gKseni, 3 days ago, translation, In English,

Important day! Today we will know the winners of VK Cup 2018. The prize fund of the competition — numbers in binary notation:

  • 1 place — 1048576 rubles
  • 2 place — 524288 rubles
  • 3 place — 262144 rubles
  • 4-8 place — 131072 rubles

We are start at 10:40. Monitor the progress here.

Current standings

Good luck to the competitors! At the evening I add the results in this post.

Read more »

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

By gKseni, 4 days ago, translation, In English,

The first day of every year championship for programming VK Cup 2018!

Today VK Cup was opened by Alexander Konstatinov (VK) and Mikhail Mirzoyanov (CodeForces). After that was a non-formal part, there we looking for funny photos of our competitors and know some interesting facts about them.

Some teams from the top-20 of Round 3 have refused to participate in the final to save the chance for the next year. We invited the following by rating. So, this year's finalists, meet!

  1. Нижний Магазин SU: V--o_o--V & LHiC
  2. ИТМО 2.0: senek_k & demon1999
  3. 120 Minutes Adventure: sinesight & SpyCheese
  4. Кекс столичный: Melnik & hloya_ygrt
  5. Z: egor_bb & Nikitosh
  6. Saint Veronika: aytel & Constantius
  7. Road to the Gucci store: Golovanov399 & I_hate_ACM
  8. Группа внутренних автоморфизмов: MrKaStep & bixind
  9. Keksik: Tinsane & kb.
  10. Свист минигана: Sert & Alexandr_TS
  11. Ананас: AllCatsAreBeautiful & arsijo
  12. Pareidolia: Copymaster & Lilith
  13. я и моя девушка: aid
  14. Типичная вечеринка с бассейном: Au-Rikka & Seemann
  15. Accepted, cats and dogs: Andrew_Makar & BigBag
  16. Московский Вентиляторный Завод: Дудка и Трубник: mHuman & komendart
  17. QuietGenius: [user:Semenar & [user:Vaterlou]
  18. Влюбленные Мудаки: super_azbuka & Khusainov
  19. R3tired: Z38
  20. Вупсень и Пупсень: Ajosteen & adedalic

Trial round reviewed our system — trial round! The first problem of trial round was a quiz. The question was about Codeforces and VK. First team that solved it is Saint Veronika: Constantius, aytel. Сongratulate! :)

Yesterday finalists went to the Hermitage Museum and carting. Today we had a lunch on the ship.

Competitors now take part in Code Game Challenge. In 2018 this is football. At evening we will watch results. For winners, VK has very nice prizes.

Tomorrow we give a link to results and you can watch and chatter for the favorite teams ;) More about the competition you can watch at VK Cup group.

Read more »

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

By _kun_, history, 7 days ago, translation, In English,


Summer Informatics School (SIS / LKSH) is a summer school for students in grades 6-10. SIS is focused mainly (but not only) on students participating in the Olympiads in Informatics — from beginners to participants of international competitions. SIS is held in July and August, each of them is visited by about 200 students from all over Russia and abroad. The language of the camp is Russian. Additional information about SIS is posted at

Right now, the August branch of the Summer Computer School is running, and on August 11 the traditional team Olympiad is going to place. I am happy to present a rated round based on it!

The round will be rated for both divisions, will be held in Aug/11/2018 16:35 (Moscow time), in each division there will be 5 tasks and 2 hours to solve them.

The problems of this round and the SIS olympiad were authored and prepared by SIS's teachers: izban, achulkov2, Schemtschik, i_love_isaf27, senek_k, asokol, WreckingBall, burunduk2. Also, I would like to thank Dembel for his help with olympiad's organization.

Thanks to our problems testers: _meshanya_, burunduk2, gritukan, niyaznigmatul, manoprenko!

Thank you, MikeMirzayanov, for the codeforces and polygon systems!

Yes, we are aware, that this contest clashes with ProCon Junior on codechef. However, given the schedule of the SIS and the approaching VK cup finals we can't do anything with it, sorry for that =/

Good luck!

UPD: The round will have one interactive problem for both divisions. Please, read the post about interactive problems here: Interactive Problems: Guide for Participants.

Congratulations to winners!


  1. Marcin_smu
  2. Radewoosh
  3. Swistakk
  4. Panole233
  5. ko_osaga


  1. Onuz
  2. aurelio
  3. usachevd0
  4. jebouin
  5. etiennerossignol

Upd Thank you for participation! Due to vk-cup conduction rating recalculation will happen slightly later, than usually.

Upd The editorial is published!

You may also check the unofficial editorial, written by neal.

Read more »

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

By Magolor, history, 8 days ago, In English,

This round is in memory of Leopoldo Taravilse.

Leopoldo Taravilse (ltaravilse) was a distinguished member of the competitive programming community in Argentina and Latin America. As a contestant, he reached the ACM-ICPC World Finals in 2010 and 2012, and was active in CodeForces and TopCoder. After 2012 he became a problemsetter for the ACM-ICPC South American regionals and the Argentinian Programming Tournament, and later coach for a World Finalist team in 2016.

Leopoldo's passion was helping others realize their full potential in competitive programming. He taught at various competitive programming schools in Brazil, Cuba, Peru and Bolivia, and his role organizing the Argentinian Training Camp cannot be overstated. Under his wing, it grew from a small group of friends in 2010 to a major event featuring international sponsors and having hundreds of participants coming from all corners of Latin America. Through successive editions of the Training Camp, Leopoldo inspired students to learn and improve, to give back to the community, and to have fun doing it.

With his intelligence, warm heart, relentless work ethics and witty sense of humour Leopoldo touched countless lives. We will miss him as a friend, a mentor, a teammate, a drinking buddy, a role model, an overall great person.

Rest in peace my dear Leo.

You can see this blog: A round in the name of ltaravilse.

And you can donate for prizes of this round: In Memory of Leopoldo Taravilse.

Hello everyone!

I'm pleased to announce: Codeforces Round #502!

This round will take place on Aug/08/2018 17:05 (Moscow time). It is rated for all participants and everyone will have 8 problems and 2 hours 15 minutes to solve them.

The contest is created by Magolor. This is the first competition I proposed. I hope that you will enjoy it. The heroes are from a TV show that I like and do not have any relation to Leopoldo.

6 of the 8 problems are created by myself. Thanks to:

  • ODT for inspiring me and discussing the problems with me.
  • Anton arsijo Tsypko for examining my problems, helping me a lot on this contest and designing problems B and G.
  • Max zubec Zub, Danya danya.smelskiy Smelskiy, Sofia Sonechko Melnyk, Stanislav StasyaCat Bezkorovainiy, Vitaliy kuviman Kudasov, Aleksandr Kostroma Ostanin, for testing the round and improving the problems and solutions.
  • Mike MikeMirzayanov Mirzayanov for Codeforces, Polygon and the help he offered to me.
  • Nikolay KAN Kalinin for helping with the contest and designing problem G.
  • Ahmed ahmed_aly Aly for his initiative to host this round in memory of Leopoldo.

...Yet Another Chinese Round...?

Scoring distribution: 500-1000-1500-1500-2000-2500-3000-3250.

Prizes distribution: $153 for top 30, delivered using bitcoin or amazon gift card (each contestant chooses).

UPD1: Chinese Editorial is published. You can view it through This link. English Editorial well be published soon.

UPD2: Congratulation to winners!

  1. Benq

  2. 000000

  3. mcfx

  4. Swistakk

  5. orbitingflea

  6. ivan100sic

  7. ko_osaga

  8. dreamoon

  9. fjzzq2002


UPD3: English Editorial is published.

Read more »

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

By PikMike, history, 13 days ago, translation, In English,

On Aug/03/2018 17:45 (Moscow time) Educational Codeforces Round 48 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extented ACM ICPC rules. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were invented and prepared by Ivan BledDest Androsov, Roman Ajosteen Glazov, Adilbek adedalic Dalabaev, Vladimir Vovuh Petrov and me.

Good luck to all participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 eddy1021 7 299
2 djp_cqq 6 240
3 halyavin 6 248
4 BigBag 6 250
5 IcePrince_1968 6 286

Congratulations to the best hackers:

Rank Competitor Hack Count
1 halyavin 80:-21
2 Doriath 45:-10
3 antguz 25:-1
4 applese 12
5 Ne0n25 11:-2
236 successful hacks and 417 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A bazsi700 0:01
B bazsi700 0:05
C yjq_naiiive 0:17
D teja349 0:10
E yjq_naiiive 0:49
F eddy1021 0:41
G .................. 1:16

UPD: Editorial

Read more »

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

By Gassa, history, 2 weeks ago, translation, In English,

Hi all!

The main phase of Codeforces Marathon Round 2 has ended. In the preliminary standings, contestants Rafbill and hakomo have got very close results, at the same time getting far enough from the next group of contestants. Will they manage to maintain the lead after the final testing, and who will come out on top? We will know in a few hours.

For now, I encourage the contestants to share their solution ideas in the comments below, or in separate posts.

Read more »

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

By Vovuh, history, 2 weeks ago, translation, In English,



Codeforces Round #501 (Div. 3) will start at Jul/31/2018 17:35 (Moscow time). You will be offered 6 or 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!


I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

UPD1: Editorial is published.


Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Wavyn 7 245
2 delete4 6 168
3 mafagafogigante 6 212
4 dongshunyao 6 214
5 jiaangk_ 6 217

Congratulations to the best hackers:

Rank Competitor Hack Count
1 halyavin 354:-66
2 test616.cpp 66:-7
3 OlaAdel 18
4 antguz 21:-7
5 wanderer163 20:-5

604 successful hacks and 446 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A 314rate 0:01
B 314rate 0:06
C garipov.roma 0:07
D shanghaiKingCsl 0:12
E1 Ka55un0 0:30
E2 Ka55un0 0:30
F shanghaiKingCsl 0:48

Read more »

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

By 300iq, history, 3 weeks ago, translation, In English,

Hello everybody!

On July 28 and 30 will take place tours of EJOI — individual programming competition for juniors, held under the rules of the International Olympiad in Informatics.

EJOI consists of the most interesting and hard problems that are proposed by a wide community of authors, and that is why we decided to give you an opportunity to crack the complete problemset of the contest. During the second tour of Olympiad, we are going to conduct a rated Codeforces round based on problems of both days of our Olympiad.

We kindly ask all the community members that are going to participate in the competition to show sportsmanship by not trying to cheat in any manner, in particular, by trying to figure out problem statements from the onsite participants. If you end up knowing some of the problems of EJOI (by participating in it, from some of the onsite contestants or in any other way), please do not participate in the round. We also ask onsite contestants to not discuss problems in public. Failure to comply with any of the rules above may result in a disqualification.

The round will happen at Jul/30/2018 11:15 (Moscow time) and will last for 2.5 hours. There will be 6 problems in each division.

The tasks of the round were invented and prepared by tourist, PavelKunyavskiy, niyaznigmatul, 300iq, GlebsHP, pashka, qoo2p5, VArtem, demon1999, flyrise, ifsmirnov, isaf27, yeputons, _kun_.

Also thanks for testing grumpy_gordon, gritukan, izban, GoToCoding, Egor,, Sert, disa, alkurmtl, senek_k, BudAlNik.

And, of course, thanks to MikeMirzayanov for great systems Codeforces and Polygon.

Good luck everybody!

UPD: Congratulations to winners!


1) Um_nik

2) LHiC

3) dacin21

4) ksun48

5) Swistakk


1) AmirHosseinGorzy

2) WaldarDoppen

3) IHaveHir

4) cly_none

5) Shadi.Gh

Read more »

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