This week in competitive programming

Last week had two international programming contests. The first one was Codeforces Round 263 on Tuesday (problems, results, top 5 on the left), won by WJMZBMR who was the only one able to solve all problems without mistakes. Great job!

Then, TopCoder SRM 631 took place on Saturday night (problems, results, top 5 on the left). The hardest problem was a data structure problem: you were given a rooted tree, and had to handle two types of requests: pick any subtree of the tree, detach it from the tree and attach it somewhere else in the tree; given two nodes in the tree such that one node is an ancestor of the other, find the maximum number of a vertex on the path between them.

Such problems usually have several working approaches:

• implement all operations in a straightforward O(n) manner, so that the entire problem needs O(n²). This is too slow, but we can then optimize the constant hidden in the O-notation a lot and squeeze it under the time limit.
• implement all operations using a complex data structure so that they take O(log(n)), so that the entire problem needs O(n*log(n)). This is usually the fastest approach, but it might require a very complex data structure - in this case, one could use a link/cut tree.
• use sqrt-decomposition so that each operation takes O(sqrt(n)), for the total running time of O(n*sqrt(n)). In this particular problem sqrt-decomposition means splitting all queries into blocks of sqrt(n), and shrinking the tree to only contain interesting vertices for each block of queries.

I like sqrt-decomposition more for this problem since it's really easy to implement.

Thanks for reading, and check back next week!

Tweet