Friday, February 3, 2017

A Limak week

TopCoder SRM 706 kicked off the activity-packed weekend of the Jan 16 - Jan 22 week (problems, results, top 5 on the left, analysis, my screencast). Our old friend, bear Limak, promised the reliably high quality of Errichto's problems, and the contest did not disappoint. I had other reasons to be disappointed, though, not being able to maintain the first place through the challenge phase. Kudos to ainta for the decisive +50!

The hardest problem had a deceptively easy statement: you need to find any sequence of 500 positive integers up to 1018, such that any two adjacent numbers in this sequence are coprime, and any two non-adjacent numbers in this sequence are not coprime. Can you see the way?

Right after the end of the SRM, Facebook Hacker Cup 2017 Round 2 narrowed the list of contenders for the cup to just 200 algorithmists (problems, results, top 5 on the left, analysismy screencast). Given the extremely harsh judging system and the fact that the 1st and the 200th place were similarly useful, one had to find the right balance between double- and triple-checking the solutions, and moving on to the next problem. Congratulations to all 200 algorithmists who got this right, and to Marek for being the fastest!

On Sunday, AtCoder Grand Contest 009 has gathered roughly the same crowd again (problems, results, top 5 on the left, analysis). w4yneb0t has continued his string of excellent results, winning this round and cementing his second place in the overall AtCoder rating list - well done!

The last problem was a great example of the type where after developing a good understanding of the mechanics described in the problem statement, coming up with the actual solution is very straightforward. You start with n zeros and m ones on a blackboard, and you're also given a number k such that k-1 divides n+m-1. You repeatedly pick any k numbers on the blackboard, erase them, and instead write their arithmetic mean (which is not necessarily an integer). Since k-1 divides n+m-1, you will eventually end up with just one number. How many different values can this last number have? n and m are up to 2000.

And finally, Codeforces 8VC Venture Cup 2017 Final Round gave the contestants a shot at monetary prizes (problems, results, top 5 on the left, parallel round results, analysis). V--o_o--V, previously known as overtroll, was super fast through the first four problems, and has managed to solve the extremely tedious problem E, to win the first prize with a comfortable margin. Congratulations!

Thanks for reading, and check back soon for the last week's summary!

No comments:

Post a Comment