 # 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

2 Likes

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