×

# DRAGONST - Editorial

Difficulty : Medium Hard

Pre-requisites : Tree, Graph, LCA, Dynamic Programming, MST

Problem : There are N chambers. You can travel from any chamber A(x1, y1) to any chamber B(x2, y2) though the passage connecting them: It takes |x1 - x2| + |y1 - y2| minutes. There are Q queries of the form S_i, F_i. You have to print the minimal C such that for the path taken to reach from S to F, doesn't have any edge greater than capacity C.

## Explanation

One way is: do a single source shortest path algorithm from S_i(considering all N*N edges) and store the maximal number while doing the algorithm. This is not at all efficient.

It’s quite obvious, that if we will have a MST of the given graph, and then our problem will be reduced to just finding the maximal number written on an edge between S_i and F_i.

We have N*N edges, if we build the MST using all these edges, it won't be efficient. We can do better.

We build the graph such that each point only connects to the nearest point from 8 directions. You can learn it in detail in Manhattan minimum spanning tree section on this page.

Now, how to handle queries? We can do a BFS/shortest path from S_i until we reach F_i and on the way we store the maximal number written on the edge. Still not efficient.

### Efficient and final solution

Let’s make our tree rooted with the root equal to 1. Then, let’s calculate F[i][j] that denotes 2j-th ancestor of vertex i(just like we do, when we want to calculate LCA, link: Another easy solution in [O(N logN, O(logN)]). Then, we can calculate G[i][j] - the maximal edge between i and F[i][j]. So, we can calculate LCA of some pair (u, v), and at the same time calculate the maximal edge between those vertices. Read the tutorial on topcoder to get it more clear.

### Scoring

Here are the solutions that tester/setter had considered:
1. Run a shortest path algorithm like spfa or Dijkstra at each query (15 points, subtask 1)
2. Build the MST among all the N^2 edges and BFS at each query (15 points, subtask 1)
3. Build the MST among all the N^2 edges and use the LCA algorithm to answer quries (30 points, subtask 1&2)
4. Build the graph that each point only connects to the nearest point from 8 directions like the Manhattan minimum spanning tree algorithm do, and run a shortest path algorithm at each query(50 points, subtask1&3)
5. Build the MST using the Manhattan minimum spanning tree algorithm, and BFS at each query(50 points, subtasks1&3)
6. Build the MST using the Manhattan minimum spanning tree algorithm, and use the LCA algorithm to answer queries (100 points)

Solutions : setter tester

This question is marked "community wiki".

3.0k91161186
accept rate: 12%

2461312

 0 I saw some coders getting 15 points for binary search onto the solution, and having floodfill/bfs as check method, but my code got TLE with it. Can you answer what's the difference between those codes. Accepted one: http://pastie.org/9516675 TLE'd one: http://pastie.org/9516671 Thanks in advance. answered 31 Aug '14, 14:34 385●2●5●7 accept rate: 5% There are several reasons why the TLE one runs slower. The most important two are: 1. floodfill should be ended as soon as (mark[b] == true); 2. floodfill should be implemented using BFS in stead of DFS for this problem. (31 Aug '14, 16:53) stzgd6★
 0 Can someone explain this parts particularly please 1) When we are given an octent , why we have to take account the max(x-y) to calculate the nearest point , what is the relation, and given with respect to point P when we are determining Q , does this x-y means , (Q.x-P.x)-(Q.y-P.y) ? 2)What is the reason of using Fenwick Tree in setter and testers solution ? 3) Actually the main question is , How do I find the closest 8 points? , I couldn't understand the topcoder tutorial. If someone could explain it would be a great reference for future coders too , as there is too little in the web about rectilinear MST , and more little about how to find the closest 8 points. answered 02 Sep '14, 19:24 366●2●6●11 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×11,984
×952
×828
×512
×176
×51
×9

question asked: 31 Aug '14, 14:15

question was seen: 4,593 times

last updated: 16 Jun '15, 10:56