DRAGONST - Editorial

editorial
, , , , , ,
1

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:

  1. Run a shortest path algorithm like [spfa][150] 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

[133]:Topcoder
[150]:Shortest path faster algorithm - Wikipedia

2 Likes
2

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.

3

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 ?

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

2 Likes
4

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.