Today was a long day for the Algorithm competitors at the TopCoder Open. It started at 9am with Semifinal 1 (
results with statements accessible by clicking the point value, top 5 on the left). The medium problem was the highlight of the round for me: you were given a single number N up to 10
18, and were asked to come up with any (unrooted) tree that has exactly N automorphisms and at most 200 vertices. First, one has to think how to find the number of authomorphisms of a tree, and discover that it's always a product of several factorials Then, you need to find a way to represent N as a product of several factorials. And finally, one had to construct a tree with the given "degree of freedom". All in all, instead of just coming up with one brilliant idea that solves the problem immediately, here you have to analyze and use your creativity several times to arrive at a working solution.
Another interesting aspect of this semifinal is the strategy battle. Lyrically has followed his usual hard-easy-medium approach, and that gave him an edge over the standard easy-medium-hard strategies of other contestants who didn't manage to solve all three.
Semifinal 2 took place four hours later at 1pm (
results with statements accessible by clicking the point value, top 5 on the left). Once again, going for the hard has turned out to be a good idea as Endagorion has pushed Egor down to the Wildcard round.
The Wildcard Round followed at 6:30pm (
results with statements accessible by clicking the point value, top 5 on the left). This time going after the hard problem didn't work out for qwerty787788, but he only went for it afer unsuccessfully solving the medium for quite some time — so maybe he could've qualified if he had started with the hard?..
Overall, I feel like today's rounds point in the direction of opening the hard problem earlier than usual. The benefits are quite tangible: in case there's no time to solve all three, it's better to have easy+hard than easy+medium. And in case the hard is completely unsolvable, you will probably have guessed that after 30 minutes or so, and by that time you can look at the scoreboard to estimate how much time one needs to solve easy+medium, to avoid fighting with the hard for too long. The risks are slightly increased, too: it might happen that you need a bit more time than average for easy+medium, and will be left with just the easy. Alternatively, you might overestimate your ability and keep pushing the hard hoping to get it in time and fail afterwards.
What is the strategy you think I should use tomorrow in the Finals? Please vote in
my Google+, and present your reasoning in comments if it differs from the above!
Just 8 contestants are left standing in the TCO: bmerry, Egor, Endagorion, lyrically, Petr, tourist, wata, WJMZBMR. The Finals happen tomorrow, November 19, at 1pm Pacific time. There will probably be live coverage in
Misof's blog, which already has awesome commentary on today's semifinals — go check it out! And of course, check my blog tomorrow for the news after the finals end :)
No comments:
Post a Comment