By MiptLited, 5 days ago, translation, In English,

November 6–13, 2018 the boot camp for competitive programming Moscow International Workshop ICPC will be held at MIPT. We invite students to participate from all over the World!

The International workshop helps students to prepare for the regional contests and World Finals of the ICPC championship.

The official language of educational program is English. The trainings include every-day contests, tasks analysis and lectures from coaches from former participants and winners of ICPC and the best Russian universities professors. Program includes interesting entertainment program in a free time. Training will be conducted in two divisions:

Division A is designed to prepare students to participate and win medals in the next ICPC World Finals.

Division B is designed to help teams prepare for the regional and international competitions.

Contests are moderated by Oleg Khristenko: coordinator of the Pankratiev Open Cup and the main editor of Snarknews. Heads of Programming Community are Mikhail Tikhomirov and Gleb Evstropov.

The sooner the payment is made, the lower the cost of participation become. Citizens of the Eurasian Economic Union (EAEU) countries may pay in Rubles and others in American Dollars. This cost includes the academic curriculum, catering, accommodation on the MIPT campus, as well as excursions, sportive activities, collective games in the days-offs.

Cost per person: $630 USD until September 21. Two teams have an opportunity to take part in the workshop for free – learn more about it on the site.

Register for Moscow International Workshop ICPC and win!

Read more »

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

By Radewoosh, 19 hours ago, In English,

Hello, codeforces!

This time I've decided to choose a task from my own contest which took place last April and was known as the Grand Prix of Poland. If you want to write this contest virtually in the future, then consider not reading this blog. If you've participated in this contest and maybe even solved this task, then anyway I recommend reading it, cause this task has many very different solutions, each of them being very interesting (in my opinion). It's also a reason why this blog is longer than previous ones.

I'll write about task C "cutting tree" (not uploaded to the ejudge yet :/). The statement goes as follows:

You are given a tree with n vertices (1 ≤ n ≤ 2·105). The task is to calculate f(k) for each integer k from the range [1, n] where f(k) is defined as the maximum number of connected components of size k which we can "cut off" from the tree. A connected component of size k is a set of k vertices such that it's possible to traverse in the tree between any pair of these vertices using only vertices from this set. Chosen components are not allowed to intersect, so each vertex must belong to at most one component.

Read more »

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

By fjzzq2002, history, 36 hours ago, In English,


It seems there isn't any blog about Berlekamp-Massey Algorithm around here, so I decided to go on a try. :P

Acknowledgement: Hats off to matthew99 for introducing this algorithm.

What is 'linear recurrence'?

Assuming there is a (probably infinity) sequence a0, - 1, we call this sequence satisfies a linear recurrence relation p1,, iff . (Obviously, if m ≥ n any p can do :P)

How to calculate k-th term of a linear recurrence?

For a polynomial , we define .

Obviously G satisfies G(f) ± G(g) = G(f ± g).

Because , if we let , then G(f) = 0. Also G(fx), G(fx2)... = 0. So G(fg) = 0 (g is any polynomial).

What we want is G(xk). Because G(fxk / f⌋) = 0, then .

Read more »

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

By GreenGrape, 2 days ago, translation, In English,


On Aug/19/2018 16:35 (Moscow time), Codeforces Round #505 takes place. This is a paired round to #504.

Some problems are taken from VK Cup 2018 Finals (ashmelev, Errichto, lewin) and some are proposed by me. I'd like to thank my fellows — Dima (_kun_) who is actually coordinating this round, Kolya (KAN) who brought me here, and also Grisha (gritukan) and Ildar (300iq) just for being nice.

I'd also like to express my gratitude to MikeMirzayanov for multiple bug fixes and awesome Codeforces!

There will be seven problems will the following scoring:
500 — 1000 — 1500 — 1750 — 2250 — 2750 — 3500

UPD. The system testing is over. Editorial (with problem E now)

Congratz to the winners!

  1. Swistakk (after all these years, yay)
  2. CongLingDanPaiShang3k5
  3. Kostroma
  4. Benq
  5. AwD
  6. xumingkuan
  7. mcfx
  8. fjzzq2002
  9. Egor
  10. kriii

As in the previous round, thanks to VK social network, GP30 scores will be distributed among the best participants.

Participants are sorted by sum of points for both rounds (if the participant did not participate in one of the rounds, the points scored for it are assumed to be equal to zero), with the maximum time for both rounds from the beginning of the round to the last submission that passed the pretests as tie-break.

Let me remind you that top 10 participants with respect to GP30 score will receive a plush Persik.

Hope you enjoy. Good luck and have fun!

Read more »

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

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

On Aug/18/2018 17:35 (Moscow time) Educational Codeforces Round 49 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. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. 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 Vladimir Vovuh Petrov, Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Mike MikeMirzayanov Mirzyanov and me.

Good luck to all participants!

Our friends at Harbour.Space also have a message for you:

Hi Codeforces!

Our Hello Barcelona Programming Bootcamp will be kicking off next month from Sept 26 — Oct 4, and we’d love to see you there!

The boot camp will once again feature the all-time greats Mike MikeMirzayanov Mirzayanov, Andrey andrewzta Stankevich, Michael Endagorion Tikhomirov, Gleb GlebsHP Evstropov, Artem VArtem Vasilyev, Ivan ifsmirnov Smirnov and other world renowned Russian coaches to train the participants.

You will be competing and learning side by side with some of the greatest teams in the world, while learning from the best coaches the ICPC has to offer.

Be sure to register before September 1st so everyone has time to get visas if needed, and of course for the Early Bird Discount of 5% or the Loyalty Discount* of 20% off registration for the boot camp!

*The loyalty discount is offered to universities and individual participants that took part in Hello Barcelona Bootcamps and Moscow Workshops ICPC.

Learn more about Barcelona ICPC Bootcamp

You can ask any questions by email:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Um_nik 7 179
2 isaf27 7 343
3 RNS_KSB 7 357
4 eddy1021 6 157
5 djp_cqq 6 176

Congratulations to the best hackers:

Rank Competitor Hack Count
1 halyavin 200:-25
2 eR6 87:-58
3 Winniechen 35:-13
4 jhonber 29:-1
5 Kaban-5 19
697 successful hacks and 674 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A arknave 0:02
B eddy1021 0:06
C bekzhan97 0:12
D teja349 0:12
E step_by_step 0:10
F lee_sin 0:24
G uwi 0:39

UPD: The editorial is posted

Read more »

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

By 300iq, 4 days ago, translation, In English,


August 17, Aug/17/2018 17:35 (Moscow time), there will be a rated Codeforces round #504. Some of the problems will be from VK Cup 2018 finals, and PikMike and Vovuh have prepared other tasks for the full round.

The problems of this round are proposed, prepared and tested by: MikeMirzayanov, PikMike, Vovuh, Errichto, lewin, Endagorion, Um_nik, YakutovDmitriy, BudAlNik, izban, Belonogov, scanhex, 300iq, qoo2p5, Livace.

There will be prizes from VK social network in this round as well! The participants who took the first 30 places of this round and the round #505, also partially based on the tasks of VK Cup 2018 Finals, will get GP30 points.

Participants are sorted by sum of points for both rounds (if the participant did not participate in one of the rounds, the points scored for it are assumed to be equal to zero), with the maximum time for both rounds from the beginning of the round to the last submission that passed the pretests as tie-break.

The top 10 participants will receive a plush Persik!

There is no country nor language restriction, everyone can win a prize. One don't have to have participated in VK Cup to receive the prize. Exact selection algorithm will be announced before the start of the round.

Good luck!

Read more »

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

By Radewoosh, history, 5 days ago, In English,

Hello, codeforces!

All signs in the sky and on the ground indicate that you've enjoyed my first blog, so here is the second one. I've decided to choose a Polish task again, as there are plenty of interesting ones. This time we'll take a look at the "plot purchase" (you can submit here), which is a bit easier, but a few years ago I was very proud of myself when I solved it. The statement goes as follows:

You are given a square n × n grid (1 ≤ n ≤ 2000). In every cell, there is a number from the range [1, 2·109]. You are also given an integer k (1 ≤ k ≤ 109). A task is to find a subrectangle of this grid such that the sum of values in this subrectangle lies in the range [k, 2·k] (or report that there is no such subrectangle). Just print coordinates of its opposite corners.

If the problem would be more difficult, and we'd be asked to find a subrectangle with some given sum of values, then it'd be possible to find it in O(n3) time, just by fixing lower and upper sides and then using two pointers to find for every possible right side the proper left side (if existing). O(n3) is too much, so we have to use the fact that we don't have to achieve the exact sum, which looks really interesting, because many known problems become easier/possible to solve when we change the exact requirement to the range one (knapsack comes to my mind).

Let's firstly look at the sum of all numbers in the grid. If it's smaller than k, then we are sure that there is no proper rectangle (because all numbers in the input are positive). If it already lies in the desired range, then we can end and print the answer. If it's bigger than k, then we need to try a smaller one. Here comes idea which most of the people would go through while solving this problem: let's divide this rectangle into two smaller ones. No matter how, possibly somewhere in the middle, because it looks the most natural (but probably it's a bit easier to implement cutting off rows/columns one by one). Also, the dimension which we'd decrease doesn't matter. After this cut, the sum of numbers in the rectangle with greater sum won't be less than the sum of all numbers divided by 2. So, if the sum was greater than k, then it won't be smaller than k.

Sooo, is it the end? Can we just cut the rectangle as long as it has the sum greater than k and then print what's left? Unfortunately, the answer is no. Let's consider a test case with only one 1 in the corner and 1000 in the rest of the grid. If k is equal to 1, then the only correct answer is to print only this corner. In our algorithm, we could lose it quickly if we'd stay in the wrong half (which is more likely as it has greater sum).

So we need some improvements. Firstly: all cells with values strictly greater than k are definitely forbidden, so we can mark them as infinity. Among all rectangles with no forbidden cells we need to find one with the sum of elements not smaller than k — if we'd have it, then we'll run our algorithm on it. Here we'll again use the fact about only positive numbers: if some rectangle is a subrectangle of some bigger rectangle and the smaller one has sum not smaller than k — then, the bigger one also has such sum. This fact implies that it's enough to look only at rectangles maximal by inclusion, which turns out to be a well know task, but I'll describe it anyway.

We'll need some preprocessing. Firstly, prefix sums for each subrectangle with one corner in cell (1, 1). Secondly, for each cell, we know how far can we go down until we meet either a forbidden cell or an edge of the whole grid.

Let's fix an upper side of the rectangle that we want to find and build an array which indicates how far can we go to the down in each of the columns. Then, if we have some interval of columns corresponding to a rectangle, then it's optimal to go as far to the down as the minimum of values in the array (in this interval). It makes sense, cause it means exatly that when we know left, right and upper side, there is only one reasonable bottom side. Let's iterate over possible right ends of an interval and keep track of places on the left where interval's minimum changes. Why only these places? It's clear that if some interval [i, j] has this same minimum as interval [i - 1, j], then it makes no point to consider [i, j], so we are only interested in intervals whose minimums change after extending that interval to the left (we assume that before and after the array there are values equal to  - ∞). So we can keep these places using a stack. When new value comes, we pop out of the stack values greater than the new one and we consider intervals which start at them and end right before the column in which currently we are. It turns out that the number of considered intervals amortizes to O(n) with a fixed upper side of a rectangle (because we consider something only when we remove it from the stack), so in total there are O(n2) considered rectangles. Complexity is the same, cause when we find any rectangle with the sum not less than k, then we can run our partition-algorithm with the knowledge that for sure it'll find the desired rectangle.

What do you think about this task? Was it interesting or maybe too easy? Let me know what you think about it. See you next time! :D

Read more »

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

By Radewoosh, history, 6 days 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" (you can submit here). 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  
  • +1743
  • Vote: I do not like it  

By gKseni, 8 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  
  • +105
  • Vote: I do not like it