Problem link : contest practice Difficulty : Medium Hard Prerequisites : 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. ExplanationOne 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 solutionLet’s make our tree rooted with the root equal to 1. Then, let’s calculate F[i][j] that denotes 2^{j}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. ScoringHere are the solutions that tester/setter had considered:
This question is marked "community wiki".
asked 31 Aug '14, 14:15

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

Can someone explain this parts particularly please 1) When we are given an octent , why we have to take account the max(xy) to calculate the nearest point , what is the relation, and given with respect to point P when we are determining Q , does this xy means , (Q.xP.x)(Q.yP.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
