Problem link : contest practice
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)]][133]). 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:
- Run a shortest path algorithm like [spfa][150] or Dijkstra at each query (15 points, subtask 1)
- Build the MST among all the N^2 edges and BFS at each query (15 points, subtask 1)
- Build the MST among all the N^2 edges and use the LCA algorithm to answer quries (30 points, subtask 1&2)
- 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)
- Build the MST using the Manhattan minimum spanning tree algorithm, and BFS at each query(50 points, subtasks1&3)
- Build the MST using the Manhattan minimum spanning tree algorithm, and use the LCA algorithm to answer queries (100 points)
[133]:Topcoder
[150]:Shortest path faster algorithm - Wikipedia