PROBLEM LINK:
Author: Hanlin Ren
Tester: Jingbo Shang
Editorialist: Hanlin Ren
DIFFICULTY:
Hard
PREREQUISITES:
shortest path tree, divide and conquer, heavy-light decomposition
PROBLEM:
You are given an M\times N undirected grid graph. Every edge has a weight that’s fixed and used to calculate shortest paths. Every vertex has a weight that’s initially 0. The problem asks you to support two types of operations:
- Add c to the weights of all vertices in the shortest path between (i_1,j_1) and (i_2,j_2)
- Query about the weight of (i,j)
It’s guaranteed that for any operation of the first type, the shortest path is unique.
QUICK EXPLANATION:
We find K=O(M\log N) spanning trees: first we find all shortest-path trees rooted at (i,\frac{N}{2}), and recursively find K'=K-M trees TL_1,\dots,TL_{K'} for the left grid, and K' trees TR_1,\dots,TR_{K'} for the right grid. Then we combine the K' left trees and K' right trees into K' spanning trees of the whole grid. These trees have a property that every shortest path is described(see below) by some of them. The rest is very easy: for each modification find which tree describes its shortest path, and use heavy-light decomposition to maintain these trees.
EXPLANATION:
subtask 1
For any query of the first type, we can use Dijkstra’s Algorithm to compute the shortest path, and iterate all vertices on it to update vertex weights. If we use heap to optimize the algorithm, its complexity becomes O(|E|\log |V|). The time complexity is O(MNQ\log MN).
subtask 2
In this subtask M=1, so the graph becomes a path. This problem becomes the classical data-structure exercise: add c on one interval or output the value of one vertex. Segment Trees or Fenwick Trees can do the job on O(N+Q\log N).
subtask 3-5
The crucial idea for this problem is that, there exists K=O(M\log N) spanning trees T_1,T_2,\dots,T_K of the graph such that, for any two vertices u,v, their shortest path is the path between them in T_i for some i\le K. In other words, we can use K spanning trees to describe all shortest paths.
Note that in this editorial, we say tree T describes the shortest path from (i_1,j_1) to (i_2,j_2), if that shortest path coincides with the simple path from (i_1,j_1) to (i_2,j_2) in T.
Finding the spanning trees
We use solve(l,r) to denote the procedure that, only consider vertices whose column number is in [l,r], and finds M\lceil\log_2(r-l+1)\rceil spanning trees that satisfies the above condition.
Let’s consider an easier case: for every modification, j_1\le mid and j_2\ge mid, where mid=\lfloor\frac{l+r}{2}\rfloor. The shortest path between such (i_1,j_1) and (i_2,j_2) must pass some vertex at (u,mid) where 1\le u\le M. We let T_i be the shortest-path tree rooted at (i,mid). Suppose the shortest path between (i_1,j_1) and (i_2,j_2) passes vertex (u,mid), then this shortest path is described by T_u.
How about the case that both j_1,j_2 are less(greater) than mid? Note that in this case, it’s still possible that the shortest path passes through some vertex at (i_0,mid). See example below.
In this example, blue edges have weight 1 and all other edges have weight 10^{10}.
However, if the shortest path passes through (u,mid), then we can still use T_u to describe this path. So we can assume that this path doesn’t pass through (*,mid).
Then we can do things recursively! Let’s call solve(l,mid-1) and solve(mid+1,r). Suppose solve(l,mid-1) returns K'=M\lceil\log_2(mid-l)\rceil trees TL_1,TL_2,\dots,TL_{K'}; solve(mid+1,r) returns K' trees TR_1,TR_2,\dots,TR_{K'}. For any pair of vertices (i_1,j_1) and (i_2,j_2), if both j_1,j_2 are less than mid, then some tree TL_i will contain their shortest path; if both j_1,j_2 are greater than mid, then some tree TR_i will contain their shortest path. We can combine these trees together: for TL_i and TR_i, we find some path in the original grid graph to connect them together, such that they become one tree. We number this tree T_{i+M}(note that we already had M trees above), then T_{i+M} can describe all shortest paths that TL_i or TR_i can describe.
Since all TL_i's and all TR_i's together can describe all shortest paths that doesn’t pass through (*,mid), all T_i(i>M)'s also can. And the paths that pass through (*,mid) are described by T_i(i\le M). Our method solve(l,r) just returns all T_i's.
The number of trees is the recursion depth multiply M, i.e., O(M\log N). To find a shortest-path tree, we can use Dijkstra’s Algorithm(use a heap to optimize) and it works on O(M(r-l)\log(M(r-l))). The complexity for solve(1,N) is
Performing all queries
Once we find the trees T_1,T_2,\dots,T_K(K=O(M\log N)), the queries become very easy. We can use heavy-light decomposition to maintain these trees. We need to perform path-add operation(add c to all weights of vertices on some path of some tree) and vertex-query operation(output the weight of some vertex on some tree). Also we need HLD to help us querying distances on these trees.
For a modification 1\ i_1\ j_1\ i_2\ j_2\ c, we iterate all trees T_1,\dots,T_K to find which tree describes the shortest path, and perform a path add operation on that tree.
For a query 2\ i\ j, we output the sum of the weights of (i,j) over all trees.
The complexity for this part is O(QM\log^2 N).
ALTERNATIVE SOLUTION:
If your solution is different with ours, feel free to leave a comment.
Also, solutions for subtask 3(M=2) and subtask 4(random data) are welcome!
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
RELATED PROBLEMS:
- SUMDIS: A similar problem of mine;
- Distance on Triangulation: One of the problems that inspired SUMDIS and this problem.
A bonus problem
Originally this problem was: you’re given a grid graph, and support two operations:
- Add weights of all vertices in some shortest path;
- Query the sum of weights of all vertices in some shortest path.
However I couldn’t get a satisfactory solution. My solution requires O(\sqrt{N}\log^2 N) time per operation, and I’m not sure if it’s faster than an optimized brute force, so I made a simpler version. This problem is left as a bouns.