PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
The key to solving this problem are dynamic trees data structures. The dynamic trees problem involves maintaining a forest of trees, which change through series of edge insertions or deletions. The most known solution are link/cut trees developed by Sleator and Tarjan. However, they are a bit difficult to implement and adapt for different applications. As we are dealing with a small number of trees in our problem, the constraints are low enough and inputs are random, we can make a compromise and choose some easier solution which still works in sub-quadratic time.
A good candidate are splay trees with their amortized logarithmic time complexity. They are a very flexible data structure. To split a tree at some point just splay adjacent node to the root and remove the edge. Merging two trees can be implemented in a similar way. Splay the rightmost node of the first tree to the root and attach the root of the second tree as its child. You will also have to maintain the sizes of subtrees at each node so that you can find and splay the k-th node to the root and detach first k nodes from a tree. Reversing the order of elements in a subtree should be done in a lazy way. Instead of reversing an entire subtree, just mark the root node for reversal. Next time before you access this node, swap its children and mark them for reversal.
We saw a variety of different approaches in the contest so lets list a few:
- You can perform a split on any binary tree by cutting off multiple branches and merging them back together. This solution was the easiest and most popular among contestants.
- Use a Treap instead of a Splay tree.
- Check tester’s implementation for a skip list approach.
- Simulate the shuffling process with ranges of numbers and rebuild the entire structure every sqrt(N) steps for a total time complexity of O(N*sqrt(N)).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.
