Thursday, September 24, 2015

A week with another 6

TopCoder SRM 668 was the first contest on the week in the early hours of Wednesday (problems, results, top 5 on the left). ACRush was the highest-rated competitor, most probably practicing before the upcoming final TCO elimination round. He has placed 6th, which is exactly the last qualifying spot in the TCO - but would he be able to repeat this performance in the TCO round? Read until the end of this post to find out :)

Enot was the winner of this SRM and the only contestant to solve all 3 problems - very impressive! This is his first SRM victory, maybe the streams have helped him improve?

Codeforces Round 320 (Bayan Thanks-Round) took place a few hours later (problems, results, top 5 on the left). Quite a few contestants have managed to solve 5 problems out of 6, so in order to win one also needed to find a few bugs in solutions of competitors. Um_nik and Egor have excelled on this front with +500 points each, but Um_nik had slightly more points from his solutions and has claimed the victory - congratulations!

Russian Code Cup 2015 Finals was one of the "major" tournaments of the year, with $4500 up for grabs for the first place (problems in Russian, results, top 5 on the left, broadcast with commentary in Russian). The problemsetters seem to have been worried about contestants finishing early, and made the last two problems just a tiny bit too hard - quite a few contestants were close on E, and I've found out after the analysis has been published that my solution on F was not that far from the correct one, but nobody could get either problem accepted.

Problem D was a nice logical puzzle: you are given 200000 points on the coordinate plane, and want to find two points such that their bounding box has a positive area, but does not contain any other points inside or on the border, or report that there's no such pair. After solving the "yes/no" part, don't forget to also think about finding the specific pair :)

And finally, TopCoder Open 2015 Round 3B determined the last 6 participants of one more major tournament (problems, results, top 6 on the left, my screencast, Egor's screencast). Scott_wu has won with comfortable margin, but the most exciting aspect for me as a viewer was Egor's climb into the qualifying zone during the challenge phase - here's the direct link into the critical moment of his screencast.

The medium problem was the nicest in my opinion. You were given 200000 cookies, with two players taking those cookies in turn one by one. Each cookie has some value for the first player, and some possibly different value for the second player. It is known that the second player always takes the cookie with highest value for him, and when there are several, with the highest value for the first player among those. The first player, on the other hand, is more flexible. He can take any cookie, and his goal is to maximize the total value of the cookies he gets in the end to him minus the total value of the cookies the second player gets in the end to the second player. What is the optimal strategy for the first player?

Now we know the 12 finalists of TopCoder Open 2015. There's a very heavy skew towards the ex-USSR this time:
Russian Federation - 7: PetrUdH-WiNGeRqwerty787788, kuniavskiEgorKankuroEndagorion
Belarus - 2: touristsubscriber
United States - 2: scott_wuecnerwal
South Africa - 1: bmerry

Thanks for reading, and check back next week!

No comments:

Post a Comment