#IjustWantContribution

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 a₀, a₁...a_n - 1, we call this sequence satisfies a linear recurrence relation p₁, p₂...p_m, 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(fx²)... = 0. So G(fg) = 0 (g is any polynomial).

What we want is G(x^k). Because G(f⌊ x^k / f⌋) = 0, then .

Hello.

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 (cdkrot) who is actually coordinating this round, Kolya (KAN) who brought me here, and also Grisha (vintage_Vlad_Makeev) 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. DearMargaret
3. Kostroma
4. Benq
5. AwD
6. xumingkuan
7. webmaster
8. TLE
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!

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: [email protected]

Congratulations to the winners:

Congratulations to the best hackers:

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

UPD: The editorial is posted

Hi!

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 awoo and vovuh have prepared other tasks for the full round.

The problems of this round are proposed, prepared and tested by: MikeMirzayanov, awoo, 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!

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·10⁹]. You are also given an integer k (1 ≤ k ≤ 10⁹). 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.

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

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.

1. 120 Minutes Adventure: el_sanchez, SpyCheese
2. я и моя девушка: aid
3. Нижний Магазин SU: V--o_o--V, LHiC
4. Road to the Gucci store: Golovanov399, -imc-
5. Ананас: AllCatsAreBeautiful, arsijo
6. Accepted, cats and dogs: Andrew_Makar, BigBag
7. ИТМО 2.0: craborac, demon1999
8. Pareidolia: Copymaster, Lilith

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: craborac & demon1999
3. 120 Minutes Adventure: el_sanchez & SpyCheese
4. Кекс столичный: Melnik & hloya_ygrt
5. Z: egor_bb & Nikitosh
6. Saint Veronika: aytel & kokokostya
7. Road to the Gucci store: Golovanov399 & -imc-
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: Semenar & Vaterlou
18. Влюбленные Мудаки: super_azbuka & Khusainov
19. R3tired: totsamyzed
20. Вупсень и Пупсень: Roms & 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: kokokostya, 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.

Hi!

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 lksh.ru

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, peltorator, craborac, asokol, Morokei, Burunduk2. Also, I would like to thank Kurpilyansky for his help with olympiad's organization.

Thanks to our problems testers: meshanya, Burunduk2, vintage_Vlad_Makeev, 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!

Div1:

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

Div2:

1. wnsh
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.