PROBLEM LINK
Author: Dmytro Berezin
Tester: Alexey Zayakin
Editorialist: Jakub Safin
DIFFICULTY
MEDIUM
PREREQUISITIES
prefix sums
PROBLEM
You’re given a weighted graph formed by disjoint cycles connected cyclically by N edges. Answer Q queries; in each query, compute the length of the shortest path between two vertices.
QUICK EXPLANATION
Use prefix sums to compute min. distances in cycles. Precompute distances between vertices connected to neighboring cycles and their prefix sums. Compute the distances for each possible direction in the outer cycle using that.
EXPLANATION
Yo dawg, I heard you like cycles so I put cycles in a cycle…
Our graph is formed by taking the “outer” cycle and replacing each of its vertices by one of the “inner” cycles. Any path between two vertices in different inner cycles then corresponds to a path in the outer cycle.
If we forget about moving through edges of the inner cycles, then there are just 2 possible paths in the outer cycle. We can compute the minimum distance (including the inner cycles’ edges, of course) for both of them and take the minimum.
Computing distances in a cycle
Let’s take a cycle with N vertices and edges, where the edge between i and i\%N+1 has length w_i. The fastest way to compute the two distances between vertices v_1,v_2 (when moving clockwise and counter-clockwise) uses prefix sums. Let’s take v_1 \le v_2 and compute the prefix sums W_i=\sum_{j=1}^i w_i (with usual w_0=0); one distance between v_1 and v_2 is d_1=\sum_{j=v_1}^{v_2-1} w_j = W_{v_2-1}-W_{v_1-1} and the other must be d_2=W_N-d_1, since the two paths between v_1 and v_2 together cover all N edges.
The prefix sums can be precomputed in O(N) and then we can compute the distances for any pair of vertices in O(1).
Distances in inner cycles
When we compute the prefix sums of the outer cycle, it’s easy to find the distances between vertices in cycles c_1 and c_2 (since distances don’t depend on vertices’ order, c_1 < c_2) that comes from the outer edges. For the path from (c_1,u_1) to (c_2,u_2) with distance denoted above as d_1, we need to cross inner cycles numbered c_1..c_2, so the path will move from u_1 to vertex v_1 (in the notation used for the outer edges in the input) of cycle c_1, then to vertex v_2 of cycle c_1+1, then to vertex v_1 of c_1+1, etc., until vertex v_2 of c_2 and from there to u_2.
That means we need to add to the distance d_1 from the outer cycle the minimum distances between u_1 and v_1(c_1), between v_2(j) and v_1(j) for every cycle c_1 < j < c_2, and between v_2(c_2) and u_2.
If we do the same thing with prefix sums for each inner cycle, we can compute first and last of these min. distances easily. The other min. distances are a problem, since there’s a lot of them. However, they don’t depend on u_1 or u_2, just c_1 and c_2, so we can use some more precomputation.
Let’s denote by X_i the minimum distance between v_1(i) and v_2(i) in the i-th inner cycle; we can compute these N numbers easily either by brute force or using the same prefix sums we’ve built for inner cycles. Now we need to compute \sum_{i=c_1+1}^{c_2-1} X_i - but that can be done exactly the same way as the distances in cycles! We just need to build the array of prefix sums of X_{1..N}; if the i-th prefix sum is S_i (with S_0=0 again), then our sum is S_{c_2-1}-S_{c_1}.
The other path in the outer cycle (denoted above as d_2) can be computed in a similar way. We’re moving from u_1 through v_2(c_1), v_1(c_1-1), v_2(c_1-1)… v_2(1), v_1(N)… v_1(c_2) to u_2. Again, the paths u_1 to v_2(c_1) and v_1(c_2) to u_2 can be found easily; the rest corresponds to \sum_{i=1}^{c_1-1} X_i + \sum_{i=c_2+1}^N X_i, which can be rewritten using prefix sums as S_N-S_{c_2}+S_{c_1-1}.
The time and memory complexity of this algorithm is linear in input size, since precomputing prefix sums is linear and each query can be processed in O(1).