Monday, August 31, 2015

A week with SSE

TopCoder SRM 666 happened very early on Wednesday (problems, results, top 5 on the left). Zxqfl won this round despite tough competition that included two coders with "target" rating yeputons and Endagorion - congratulations!

The easy problem in this round was a nice graph theory exercise. You're given a tree and one vertex of the tree is selected. What's the maximum number of different vertices a walk of length L starting from the given vertex can visit?

Codeforces Round 318 ("RussianCodeCup Thanks-Round") took place on Saturday (problems, results, top 5 on the left). Marcin_smu has claimed the first place thanks to a solution to problem E that managed to pass the system tests - congratulations! In the post-match discussion it turned out that both passing solutions for problem E were not intended to pass: Marcin's solution gave a wrong answer on some inputs, and the only other passing solution from logicmachine relied on SIMD CPU instructions to speed up a O(n^2) solution, while the intended complexity was O(n*sqrt(n)).

While both issues could probably be avoided by investing more effort into the round preparation, I think they actually highlight one of the main good aspects of competitive algorithmic programming: it's extremely objective. Every solution is judged against the same testcases, under the same time and memory limits, and completely automatically.

Thanks for reading, and check back next week!

No comments:

Post a Comment