You are not logged in. Please login at www.codechef.com to post your questions!

×

QGRID - Editorial

2
2

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 $TL_i$ and $TR_i$

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.

This question is marked "community wiki".

asked 22 Aug '17, 19:09

r_64's gravatar image

7★r_64
261924
accept rate: 16%

edited 11 Sep '17, 17:27

admin's gravatar image

0★admin ♦♦
19.8k350498541


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.
Code

link

answered 11 Sep '17, 21:54

rajat1603's gravatar image

7★rajat1603
1.0k113
accept rate: 4%

edited 11 Sep '17, 21:56

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...

link

answered 11 Sep '17, 21:45

liouzhou_101's gravatar image

7★liouzhou_101 ♦♦
6822313
accept rate: 12%

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.

link

answered 12 Sep '17, 05:10

jtnydv25's gravatar image

6★jtnydv25
512
accept rate: 0%

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

link

answered 12 Sep '17, 11:16

muravjev_slava's gravatar image

5★muravjev_slava
563
accept rate: 16%

edited 12 Sep '17, 13:12

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

link

answered 12 Sep '17, 11:40

muravjev_slava's gravatar image

5★muravjev_slava
563
accept rate: 16%

edited 12 Sep '17, 13:14

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 ??

link

answered 24 Sep '17, 10:30

sagar2009kumsr's gravatar image

1★sagar2009kumsr
234
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,359
×286
×138
×127
×2

question asked: 22 Aug '17, 19:09

question was seen: 1,590 times

last updated: 24 Sep '17, 10:30