We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Idea: we can get a library to two cities either by 1.) using 1 library + 1 road or 2.) 2 libraries. We can get a library to a three citites with 1.) 1 library + 2 roads or 2.) three libraries. In this sense, a road is effectively the same as a library, so we want to choose whichever is cheapest. Inductively, from the last observation, if the cost of a library is less than a road, we should just build all libraries.
Alternatively, we want to maximally build roads to connect the towns, as we can minimise the number of libraries. By forming a minimum spanning tree (with a DSU), we can work out 1.) the number of disjoint sets (and hence the number of libraries) and 2.) the number of roads.
In all honesty, I copied the DSU code from GeeksForGeeks and modified it slightly such that I know when I've bothered to make a new connection, or if the connection is redundant.
classDisjSet:// boilerplate from GFGdef__init__(self,n):self.rank=[1]*nself.parent=[iforiinrange(n)]self.n=n// modification - there are initially n islands/disjoint regionsdeffind(self,x):if(self.parent[x]!=x):self.parent[x]=self.find(self.parent[x])returnself.parent[x]defUnion(self,x,y):xset=self.find(x)yset=self.find(y)ifxset==yset:// modification - we made 0 new connectionsreturn0ifself.rank[xset]<self.rank[yset]:self.parent[xset]=ysetelifself.rank[xset]>self.rank[yset]:self.parent[yset]=xsetelse:self.parent[yset]=xsetself.rank[xset]=self.rank[xset]+1self.n-=1// mod. - we unified one more islandreturn1// mod, - we made a new connection (road)defroadsAndLibraries(n,c_lib,c_road,cities):// better to just install all librariesifc_lib<=c_road:returnn*c_lib// minimally connect with roads (no loops)graph=DisjSet(n)roads=0forc1,c2incities:roads+=graph.Union(c1-1,c2-1)returngraph.n*c_lib+roads*c_road
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Roads and Libraries
You are viewing a single comment's thread. Return to all comments →
Idea: we can get a library to two cities either by 1.) using 1 library + 1 road or 2.) 2 libraries. We can get a library to a three citites with 1.) 1 library + 2 roads or 2.) three libraries. In this sense, a road is effectively the same as a library, so we want to choose whichever is cheapest. Inductively, from the last observation, if the cost of a library is less than a road, we should just build all libraries.
Alternatively, we want to maximally build roads to connect the towns, as we can minimise the number of libraries. By forming a minimum spanning tree (with a DSU), we can work out 1.) the number of disjoint sets (and hence the number of libraries) and 2.) the number of roads.
In all honesty, I copied the DSU code from GeeksForGeeks and modified it slightly such that I know when I've bothered to make a new connection, or if the connection is redundant.