Let's start with a poll: what would be a good name for this blog? Vote in my Google+, and suggest other options in comments! Now, back to business:
TopCoder SRM 636 on Tuesday had quite diverse problemset (problems, results, top 5 on the left). The easy was a pretty straightforward implementation involving several nested loops and a standard way to find sums of sub-rectangles of a given grid in O(1) after precomputation. The medium was a very unexpected application of linearity of expectation — such problems never cease to amaze me! The hard was a "professional" problem requiring both an insight and quite careful implementation to get right, which I haven't managed this time.
Even if my solution for the hard didn't fail with both timeout and wrong answer, I would only get second place. The first place is undisputedly Endagorion's — great job Mikhail!
The new season of the Open Cup started on Sunday with the Grand Prix of Saint Petersburg (results, top 5 on the left). I don't think the problemset is available online yet, but one of the problems was a very simply stated mathematical puzzle that I can share here:
Given an undirected graph where the degree of each vertex is at most 5, prove that it's possible to color its vertices using 3 colors in such way that each vertex has at most one adjacent vertex of the same color as itself.
Another problem has introduced a new concept that I don't remember seeing in programming contests before: you were asked to implement a strategy for a game, but instead of beating the optimal play of the opponent, your strategy had to beat random play of the opponent in at least 290 out of 300 rounds. Are you aware of similar programming contest problems?
Overall, this was a nice contest — kudos to the problemsetters!
Codeforces Round 274 (problems, results, top 5 on the left) happened right in the middle of the Open Cup round, so everybody had to pick only one of the two. As evident from the scoreboard, there was still quite fierce competition and Bruce ended up on top with 200+ point margin — congratulations!
Bayan Elimination Round wrapped up the highly competitive Sunday (results, top 5 on the left). I don't think the problems are available online, and I did not participate myself, but quite a few strong algorithmists did. Kazuhiro, one of the problemsetters of TopCoder SRM 636 mentioned above, has topped the scoreboard with a substantial margin — well done! This contest was notable for its highly unusual advancement system: only the top one coder from each of top 20 countries would advance to the onsite finals, essentially splitting the competition into many intra-country micromatches. Now quite a lot of people got to feel like many Moscow State University teams feel each year at the ACM ICPC regionals :)
Thanks for reading, and check back next week!
Even if my solution for the hard didn't fail with both timeout and wrong answer, I would only get second place. The first place is undisputedly Endagorion's — great job Mikhail!
Given an undirected graph where the degree of each vertex is at most 5, prove that it's possible to color its vertices using 3 colors in such way that each vertex has at most one adjacent vertex of the same color as itself.
Another problem has introduced a new concept that I don't remember seeing in programming contests before: you were asked to implement a strategy for a game, but instead of beating the optimal play of the opponent, your strategy had to beat random play of the opponent in at least 290 out of 300 rounds. Are you aware of similar programming contest problems?
Overall, this was a nice contest — kudos to the problemsetters!
Thanks for reading, and check back next week!
0 komentar:
Post a Comment