Sunday, May 13, 2018

An alma mater week

The Sächsilüüte week started with Codeforces Round 475 (problems, results, top 5 on the left, analysis). Three contestants managed to solve all problems, but some were faster than the others :) In particular, V--o_o--V has finished after just 81 minutes, and thus won with a 500-point margin. Well done!

One of the main competitive programming events of the year, ACM ICPC 2018 World Finals took place on Thursday (problems, results, top 13 on the left, our screencast with commentary, official broadcast, analysis). The deciding events of the competition happened in the last few minutes, when the Moscow State University team managed to squeeze in a solution to roblem E with an extra log factor by changing the number of iterations in binary search and getting something like TLE-TLE-TLE-OK-WA-WA-WA from seven attempts with different values of the magic constant.

That OK might well turn out to be TLE or WA as well, but fortune favors the bold, and what essentially happened was that the Moscow State University team did great in using all their resources and creativity up to the last minute and got a well-deserved victory. Really happy for the team and for my alma mater to finally get the cup that I and many others could not deliver in the past :)

Big congratulations to all other medalists on the great result, too!

Problem D brought the most excitement for me in this problemset. There are n people, each starting with 1 gem. The following operation is repeated d times: take one of the gems uniformly at random, and split it into two gems (so the person holding it will have one more gem). After doing all that we order all people by the number of gems they have in decreasing order, and add up the number of gems of the first r people in that order. What is the expected value of that sum? n and d are at most 500.

I'm also really interested in hearing what do you think about our stream and about the official broadcasts, if you had a chance to check them out, and I'm sure the ICPCLive team is very interested as well. Please share your observations or ideas!

Finally, TopCoder Open 2018 Round 1A took place on Saturday (problems, results, top 5 on the left, analysis). With the problems quite a bit on the easy side, the challenge phase was instrumental in determining the winner — congratulations to Dembel on finding the +125 and the victory!

Thanks for reading, and check back for more!

No comments:

Post a Comment