Author: | Pavle Martinović |
Solved by: | |
First to solve: | VVV |
Without loss of generality, we may assume that R[1] < L[N], by mirroring everything if that is not the case. We will solve this problem using dynamic programming, where we calculate the minimum number of moves for person to obtain the paper in a language he understands. It never makes sense to go to a language with a smaller index, and we can trim all left ends less than and right ends greater than .
To calculate we need to find the minimum of dp[v]+dist(u,v)+1 for all such that [L[u], R[u]] and [L[v], R[v]] intersect. Additionally, we can reduce the scope to only those where is contained in [L[v], R[v]], since for other cases where we get to this person using someone with L[v]>L[u] the person who first surpassed the index could just have translated it to and sent it directly to , which would take less turns.
Now, to solve the problem, sort the left and right interval ends into events - should be used to find the active node with the smallest value of dp[v]+dist(u,v)+1 and then activate , while should deactivate . We’re interested in this minimum among all active nodes. This can be done by centroid decomposition - the best path either passes through the centroid or not! In each node of the centroid tree we maintain a set containing the values of dp[u]+dist(c,u)+1 for all in its (centroid) subtree. Then finding the best path just requires traversing up the centroid tree and taking the value dist(v,c) plus the minimum value of its set. Activating and deactivating is just set insertions/deletions. Calculating distances can be done by precalculating the distances from every node to everything in its centroid subtree, or precalculating LCA and depths. All in all this solves the problem in O(N\log^2N).