Editorial : Coyote & roads

Problem Link

https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/mr-pompom-and-make-tunnel

Explanation :

If you make a graph such that all points on the 2d plane are connected to all other points and find the minimum spanning tree then you will get a valid answer but you can not store (10^5)^2 edges in adjacency list  so you have to think about reducing the edges. There is a trick in a cost function.You want to find at least one edge for every vertex and it is minimum so we just need to consider  four possibilities. First you have to sort all the points with according to  x coordinate and add the edge between all the consecutive points then sort all the points according to  y coordinate and add the edge between all the consecutive points.Then apply typical minimum spanning tree approach on this graph. In sorting make sure that your compare method have  symmetric relation.

Advertisements

One thought on “Editorial : Coyote & roads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s