CF 172

A: a geometry problem but difficult to implement nonetheless.

B: For each item a[i], if it serves as the second maximum element in the range, then the only choice for first maximum element would be the first one to the left that is larger, or the first one to the right that is larger. Now this looks very similar to the maximum rectangle problem in which you need the first smaller to the left and the first smaller to the right. For problem B you maintain a stack with decreasing elements and a[i] kills the top of stack until the top of stack is larger than a[i], then you push a[i] into stack. Every time you pop an item, called curr out of stack, update ans with curr xor st.top() and curr xor a[i], the one that caused curr to pop. Time complexity O(n)

C: This one is tricky when you look at the problem. If it is a list instead of a tree, then it is easy, because after removing some element, you get a shorter list. However for trees you can have potentially a larger number of different trees when a subtree gets pruned from the input tree.

Now look at it differently and consider each node individually. What is the chance of a node get selected in a step and hence contribute 1 to the final cost. Things happen in other places do not matter, and the only thing that matters is whether some nodes in the path from this node to the root gets selected or not, and since we select each remaining node with equal probability, the only way a node can get selected is to get selected before any of its ancestor, and the probability is 1/depth[i] for node a[i], and this probability remains the same until one node in the path from a[i] to root a[1] gets selected and then we are done with a[i]. So the expected total number of steps is:
sum over i=1 to n, 1/depth[i]

This is reminiscent of the analysis in randomized quicksort when you need to find the probability that two items get 1 comparison or never compared. You get 1 comparison if one of them gets chosen as pivot before any other item in between becomes a pivot, in which case the two items will enter separate partition and never compared.