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

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 (_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  
  • +92
  • Vote: I do not like it  

By fjzzq2002, history, 2 days ago, In English,

#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 a0, a1...an - 1, we call this sequence satisfies a linear recurrence relation p1, p2...pm, 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  
  • +1190
  • Vote: I do not like it  

By Radewoosh, 43 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  
  • +634
  • Vote: I do not like it  

By MikeMirzayanov, 46 hours ago, In English,

Hello, friends!

I want to discuss separately the negative feedback on the round 505.

I understand, that many participants are disappointed by solutions, which failed on system tests. In fact, the pretests in problems B, D and E turned out to be weak. The problem C also didn’t gone too smoothly, but I don’t see nothing critical.

Surely, this was a flaw in a work of author and coordinator. Unfortunately, such situations sometimes arise and it is difficult to avoid them at all. For these problems, the number of pretests and their type was not looking too weak.

Problem B: 9 pretests, there are small and large answers, two tests with answer -1, there are pretests with n = 1 and n = 2, there are four pretests with n = 150000.

Problem D: 14 pretests, among them manual tests and four different generators, few pretests with n = 700, majority of answers is ‘Yes’, but there are ‘No’ as well. In my opinion, too little pretests with ‘No’.

Problem E: 14 pretests. Yes, this problem on VK cup finals contained 10 pretests and caused many systests fails for participants. I have added 4 more tests to pretests from tests, which caused system tests fails for onsite participants. I was very surprised to see, that there were still so many fails after systests.

Summing up, the pretests turned out to be incomplete, but it is hard to say, that it was obvious defect by author or coordinator. Probably it is a combined effect from the problem specifics and the lack of experience of _kun_ as a coordinator.

I haven’t examined all the problems thoroughly, but still round seemed interesting to me. There were no serious fails with statements, bugs in tests and solutions. The system was also working smoothly, without large queue.

Please explain your negative feedback about the round. It will be very valuable to read a reasoned opinion from experienced participants.

Thanks, MikeMirzayanov

Read more »

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

By lxn, history, 10 hours ago, In English,

Rating distribution of codeforces users was interesting for me. The rating of each user is availible on the codeforces website, so I just go to 'Rating' tab download all the pages and parse them.

The picture is actual for 21.08.2018

May be this is interesting not only for me.

Read more »

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

By GreenGrape, 47 hours ago, In English,

Author: GreenGrape

Tutorial is loading...

Author: GreenGrape

Tutorial is loading...

Author: GreenGrape

Tutorial is loading...

Author: GreenGrape

Tutorial is loading...

Author: ashmelev

Tutorial is loading...

Author: Errichto

Tutorial is loading...

Author: lewin

Tutorial is loading...

Read more »

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

By im0qianqian, 10 hours ago, In English,

I am sorry to bother you, my account has recently had some problems. It was stolen by someone else I didn't know and changed my password and email address. I don't know if I leaked my password, or just hacked by someone else. In short, I can't change my password and email address. I can use it temporarily because my account has not been logged out. I am afraid that he will take my account to do something unethical, such as stealing data from the gym, or deliberately deleting something I have now. I know that if this article is seen by him, it may bring more tragic things, but I can only pray that such things will not happen. I know his email, and I also contacted him through QQ, but I have never received a reply.

I also tried to contact MikeMirzayanov and asked him to change the email address and password for me. I have not received a reply yet. In addition, I want Codeforces to send email confirmations when modifying email addresses, which is more secure.

Finally, if you have recently seen me posting some weird comments, please let me know, my email address is: im0qianqian@gmail.com, thank you!

Read more »

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

By PikMike, history, 4 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: hello@harbour.space

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 MikeMirzayanov, 21 hour(s) ago, In English,
Tutorial is loading...

Problem idea: MikeMirzayanov, PikMike; prepared by: Vovuh.

Tutorial is loading...

Problem idea: MikeMirzayanov, prepared by: MikeMirzayanov.

Tutorial is loading...

Problem idea: MikeMirzayanov, prepared by: PikMike.

Tutorial is loading...

Problem idea: Vovuh, MikeMirzayanov; prepared by: PikMike.

Tutorial is loading...

Problem idea: Errichto, prepared by: Errichto.

Tutorial is loading...

Problem idea: lewin, prepared by: lewin.

Tutorial is loading...

Problem idea: Endagorion, prepared by: Endagorion.

Read more »

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

By PikMike, history, 2 days ago, In English,

1027A - Palindromic Twist

Tutorial
Solution (PikMike)

1027B - Numbers on the Chessboard

Tutorial
Solution (Vovuh)

1027C - Minimum Value Rectangle

Tutorial
Solution (PikMike)

1027D - Mouse Hunt

Tutorial
Solution (adedalic)

1027E - Inverse Coloring

Tutorial
Solution (PikMike) O(n^3)
Solution (BledDest) O(n^2)

1027F - Session in BSU

Tutorial
Solution (Vovuh)
Solution (Vovuh) Kuhn's Algorithm

1027G - X-mouse in the Campus

Tutorial
Solution (adedalic)

Read more »

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