Codeforces Round #411 (Div. 1)

A. Find Amir

1 -> n -> 2 -> (n-1) -> 3 -> (n-2) ->…

B. Minimum number of steps

Consider a substring
$$ a\underbrace { {bbb \cdots b} }_{K*b} $$
to move the ‘a’ to the end, we should use the substitution method K times, and then the ‘b’s will be doubled.
We move the last ‘a’ to the end and repeat the procedure until there is no ‘a’ before ‘b’.

C. Ice cream coloring

All nodes containing the same type of ice cream form a connected component, therefore we can find that if a node’s father contains a type of ice cream but this node doesn’t, its descendants definitely do not contain that.
So we have a greedy strategy:

  1. Randomly choose a root.
  2. Apply dfs on the tree starting at the root.
  3. Traverse all types of ice creams contained by the current node x, if it has not been colored, color it with the smallest number which hasn’t been used in node x.

D. Expected diameter of a tree

For each node we calculate the longest distance it can reach, marked as d_i. Let’s calculate the expected diameter of the tree after adding an edge between tree V and U. There comes two cases:

  1. d_u + d_v + 1 \leq max(diameter(U), diameter(V)), then the answer should be max(diameter(U), diameter(V)).
  2. The answer should be d_u + d_v + 1 otherwise.

So we can traverse the nodes in U and apply binery search in V to calculate the answer. The complexity is O(N*logM), in which N denotes the size of U and M denotes the size of V, then the global complexity is O(Q*N*logN), which is unsatisfactory.
To prevent the TLE, there are two tricks: the first is that if U is larger than V, we swap U and V, so a single query’s complexity becomes O(sizeof(smaller tree)*log(sizeof(larger tree))). The second is that if a query (A, B) has been asked before we don’t need to recalculate the answer.