QGRID - Editorial

PROBLEM LINK:

Practice

Contest

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.

An example

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.

Combination of two trees  and

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

T(N)=O(M^2N\log(MN))+2T(\frac{N}{2})\implies T(N)=O(M^2N\log^2 N).

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:

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.

2 Likes

Nice approach!

I was wondering why my code is so slow before seeing this editorial.
It seems that I even did not realize that one should find only O(m log n) spanning trees.

I built about 4mn trees, more precisely, I built a segment tree with each node associated with 2m trees, where each tree is rooted at some boundary vertex (totally 2m such vertices for every interval), and only contains all vertices in the interval. Totally about O(m^2 n \log^2 n) operations.

For each query, I maintain a 2m \times 2m 2d-array d[][], where d[i][j] means the minimal distance between some boundary vertex i to some boundary vertex j.
When updating two interval’s information, I choose two intermediate vertex x and y, and try such path i \to x \to y \to j. Thus we can get information of an interval in O(m^4 \log n) per query.

When we get the d[i][j] of an interval, we’ll use d[i][j] to backtrace the shortest path, which goes through at most O(\log n) my trees. In each tree, we should play an operation that adds c from some vertex to the root. So we can use tree’s DFS order to simplify the problem, and then use a BIT to maintain it. As a result, this step needs O(m^2 \log^2 n) per query.

To sum it up, my solution is totally O(m^2 n \log^2 n + q(m^4 \log n + m^2 \log^2 n)).

Here is my code.

However, I think it is the most stupid AC solution to this problem. QAQ…

1 Like

I have an (N + Q)\log(N)M^3 online solution which worked pretty fast (About 1.4 seconds)

First i build a segtree where i store a 2M \ \mathbb{X} \ 2M grid which stores the shortest path between each pair of indices (l , i) to (r , j) for 1 \leq i,j \leq m in the segment (l,r) of the segment tree.

This can be built in NM^3 time.

Now for a query , find those segtree ranges corresponding to (1 , l-1) , (l , r) , (r + 1 , n) and calculate the shortest path from (l , row1) to (r , row2) , this is just a dijkstra on M^2logN nodes.

Now in this shortest path , add lazy updates to each segment of the segment tree denoting in the segment (l , r) , add c to the shortest path between (l , i) and (r , j).

This can be lazily propogated easily.

Query is trivial in this , its just a point query on the segment tree.


[1]


  [1]: https://www.codechef.com/viewsolution/15314898
3 Likes

We don’t actually need heavy light decomposition to maintain the trees. The queries we have are:

  1. Add x to all nodes on a path from root to a node

  2. Find the value of a node.

We can convert it to point updates and range queries. We keep a binary indexed tree, and we increase the value at node by x in a query of type 1. Then, in a query of type 2, we find sum in subtree.

1 Like

It seems that I’m only one who got ‘m = 2’ and ‘random m = 3’, but didn’t get full problem.

My solution for ‘m = 2’ was based on decomposition of field on blocks of size M(N /K). For each block I had 2M side vertices, for each pair I calculate distances in block with Dijkstra. This part was done in O(NM^2log(MN/K)).

Let’s call minimal path between two side vertices in block ‘atomic’ if it doesn’t contain another side vertex from this block. So we can divide any minimal path between two vertices as set of ‘atomic’ paths plus paths from start and end to some side vertex in their block. For each pair of side vertices in the same block I stored if path between them is atomic. And for each ‘not side’ vertex in block I stored which atomic paths contain it.

After that I built graph with 2MK vertices, where edges were between

  • two adjacent side vertices from different blocks
  • two side vertices from the same block (weight is length of atomic path between them)

and calculated full distance matrix d[i][j] with Dijkstra runs for each vertex in O(M^3Klog(M^2K)).

Now update on the path needs next actions:

  1. Dijkstra inside block from start and from end - O(MN/Klog(MN/K))
  2. Iterate over all pairs of side vertices in start/end blocks and find length of minimal path as dist[start][startSide]+d[startSide][endSide]+d[endSide][end]
  3. Iterate over all atomic paths in graph and if path contains this atomic path - increment value associated with that - O(M^2K).
  4. Update values for all vertices on paths from start to startSide and end to endSide - O(MN/K).
  5. If start and end are in the same block - additionally check if the path between them without any atomic paths is minimal.

Query of value for vertex can be done in O(M^2) - just need to sum up values, associated with all atomic paths that contain vertex.

Total complexity is about O(NM^2log(MN/K)+M^3Klog(M^2K)+Q_1(MN/Klog(MN/K)+M^2K) + Q_2(M^2). I tried several values of K, good balance was found with K = 250 (I coded on Java if it is important).

There is link to my ‘block’ solution (I removed huge template): Code on pastebin

And for any ’m = 3’ test my block solution was TL, so for ’random m = 3’ I created next solution.

Let’s call path from (1, 1) to (m, n) as ’main path’. My idea was that with random weights all paths between ’far’ vertices will be divided in

  • path from start to ‘main path’
  • some part of ‘main path’
  • path from ‘main path’ to end

So we could run dijkstras from start and end to the ’nearest’ vertices and

  1. Check if start and end actually connected through some common ‘nearest’ vertex (it could be even start or end itself) - so we simply update all vertices on path.
  2. Check all pairs of ‘nearest’ vertices from main path and find length of minimal path as dist[start][startMain]+mainPathDistance[startMain][endMain]+dist[endMain][end] (mainPathDistance can be calculated in O(1) with prefix sums).
  3. Update vertices on paths from start to startMain and from end to endMain.
  4. Update part of mainPath as increment on array segment in O(logMN) with some segment or fenwick tree (same way as for M = 1).

Query of value in vertex can be done in O(logMN) as query to index in tree (same as for M = 1 too).

One more querstion - when is vertex ‘nearest’? My dijkstra processed only vertices that were not far than K edges from initial. I got AC with K = 40 (30 was not enough).

So total complexity of solution is O(NMlog(NM)+Q_1(MKlog(MK)+(MK)^2 + log(MN)) + Q_2log(MN))

There is link to my ‘main path’ solution (I removed huge template): Code on pastebin

Can anyone tell me why do we are doing the recursion in this case ?? I am unable to find out… Why we need to recur while we will get the required result from the first tree only…??? why do we need to divided and conquer ??