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.
Roads and Libraries
Roads and Libraries
Sort by
recency
|
885 Discussions
|
Please Login in order to post a comment
I spent quite some time to figure out why my solution didnt pass the 7 heavy input test cases. It turned out that since i tried to convert the edge list to adjacency matrix, the test ran out of memory. So instead of adjacency matrix, i use std::map as adjacency list. map> toAdjList(int n, vector> cities) { map> result = {}; for (const auto &ct : cities) { int a = ct[0]; int b = ct[1]; if (result.find(a) == result.end()) { result[a] = vector(); } result[a].push_back(b); if (result.find(b) == result.end()) { result[b] = vector(); } result[b].push_back(a); }
}
long roadsAndLibraries(int n, int c_lib, int c_road, vector> cities) { if (n == 0) return 0; if (n == 1) return c_lib;
} `
After thinking about it here is my solution in pseudocode then python:
My Intuition: Cities that can be connected by roads make up an island or a sub graph. Each island only needs 1 library + the cost of the roads between the cities. So you can count the number of islands + the number of roads on each island. However the cost of a road can be so high that it's cheaper to build a library in each city. I had to think about this for a bit, I thought it might be some kind of greedy problem so I tried to break it down. I thought about when 1 road cost < 1 lib cost, 1 road cost == 1 lib cost and 1 road cost > 1 lib cost. Turns out if the cost of building a road is >= the cost of building a library, it makes more sense to put a library in each city (I did the math with the 2 cities 1 road case). So at the end of the day you just have to compare building roads + libraries (one each island) or just building libraries in each city. Also another key point is each road is bi-directional so if you build an adjacency list you have to add edges in both directions.
Psuedocode:
Greetings! I wonder if anyone could help me figure out why I get failed tests, my approach is simply to count subgraphs, which should be enough to calculate least possible cost. Thanks!
I will share some intuition i used: - We need to look at every sub graph of the cities such that each sub graph is a (potential) connected component. - For each connected component, you can either buill one library per city and build no roads, or build one libaray and connect the rest of citis with mininum roads. There can be no in between that is optimum. - For n citis, you alway only need n - 1 roads.
my code with python. i dont know it fail in test case 7 how to debug def roadsAndLibraries(n, c_lib, c_road, cities): if c_road > c_lib: return c_lib * n