You are not logged in. Please login at www.codechef.com to post your questions!

×

DRAGONST - Editorial

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)]). 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".

asked 31 Aug '14, 14:15

darkshadows's gravatar image

5★darkshadows ♦♦
3.0k90161185
accept rate: 12%

edited 16 Jun '15, 10:56

vicky002's gravatar image

1★vicky002 ♦♦
2361311


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.

link

answered 31 Aug '14, 14:34

vladamg98's gravatar image

5★vladamg98
385257
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★

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.

link

answered 02 Sep '14, 19:24

tamimcsedu19's gravatar image

3★tamimcsedu19
3662611
accept rate: 0%

edited 02 Sep '14, 19:25

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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

Tags:

×10,459
×857
×735
×421
×139
×43
×9

Asked: 31 Aug '14, 14:15

Seen: 4,317 times

Last updated: 16 Jun '15, 10:56