The working week was free of programming contests - but come Friday evening, the competition was in full swing with TopCoder SRM 613 (
problems,
results,
my screencast, top 5 on the left). The screencast is full of frustration with not being able to squeeze the 500 inside the time limit (my solution was about 2-3x too slow, although I believe the asymptotic complexity was similar to the correct solutions), and then the excitement of getting the 900 working with just 1 minute to go in the coding phase.
The 500 problem went like this: how many ordered n-tuples of numbers exist with each number between a and b, and all numbers in the n-tuple relatively prime as a set? a, b and n are up to 10
9, b-a is up to 10
5. There is, in some sense, only one possible approach: we have to use the inclusion-exclusion principle: first count all n-tuples, then subtract those where all numbers are divisible by 2, and so on. But there are several possible implementations of this approach, some faster than others :)
Codeforces carried the competitive spirit on with Codeforces Round 238 on Saturday evening (
problems,
results, top 5 on the left). al13n has won after a long break - in fact, his last win was one year minus one day ago :) As a result, he has jumped back into the top 10 by rating - congratulations! Komaki, on the other hand, showed some great consistency by getting into the top 5 both on TopCoder and on Codeforces.
And finally, the Open Cup returned on Sunday with the 11th round of this season (
results, top 5 on the left). With about 3 months left before the World Finals in Ekaterinburg, it's most natural to view the OpenCup as the best available show of teams' strength. Not much has changed on this front, though: among the teams qualified for the World Finals, SPb SU 4 holds the lead, followed by Moscow SU Tapirs.
The Open Cup also gave rise to a nice strategy tip from my teammate Pavel Mavrin:
https://twitter.com/pmavrin/status/447706027534721024
Thanks for reading, and see you next week!
No comments:
Post a Comment