Sort by

recency

|

884 Discussions

|

  • + 0 comments

    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:

        1. Build adjacency list (with bi-directional edges).
        2. For each city:
            if not visited city add 1 library and start a Breadth First Search starting from this city (new island).
        bfs:
            each city visited = 1 new road, skip cities already visited, add each city visited to list of visited cities.
        3. return min(num_cities * lib_cost, cities_and_roads_cost)
    
    # BFS - O(V + E) - Time | O(2 * E) - Space
    def get_roads_from_city(graph, city, visited):
        num_roads = 0
        neighbor_q = []
        visited.add(city)
        for neighbor in graph[city]:
            neighbor_q.append(neighbor)
        while len(neighbor_q) > 0:
            node = neighbor_q.pop(0)
            if node not in visited:
                num_roads += 1
                visited.add(node)
                if node in graph:
                    for neighbor in graph[node]:
                        if neighbor not in visited:
                            neighbor_q.append(neighbor)
        return num_roads, visited
    
    
    def roadsAndLibraries(n, c_lib, c_road, cities):
        # Write your code here
        if n == 1:
            return c_lib
        
        graph = {}
        # Build Adjacency List
        for city in cities:
            neighbors = graph.get(city[0], [])
            neighbors.append(city[1])
            graph[city[0]] = neighbors
            
            neighbors = graph.get(city[1], [])
            neighbors.append(city[0])
            graph[city[1]] = neighbors
        
        for city in range(1, n + 1):
            if city not in graph:
                graph[city] = []
        
        # BFS
        def libraries_and_roads_cost(graph):
            num_roads = 0
            num_libraries = 0
            visited = set()
            for city in graph.keys():
                if city not in visited:
                    roads, visited = get_roads_from_city(graph, city, visited)
                    num_roads += roads
                    num_libraries += 1
            return num_libraries * c_lib + num_roads * c_road
        
        libs_only = n * c_lib
        libs_roads = libraries_and_roads_cost(graph)
        return min(libs_only, libs_roads)
    
  • + 7 comments

    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!

    public static long roadsAndLibraries(int n, int c_lib, int c_road, List<List<Integer>> cities) {
            if(c_lib <= c_road || cities == null || cities.size() == 0)
                return c_lib * n;
            
            List<List<Integer>> adj = new ArrayList<>(n);
            for(int i = 0; i < n; i++){
                adj.add(new ArrayList<>());
            }
            for(int i = 0; i < cities.size(); i++){
                int u = cities.get(i).get(0) - 1;
                int v = cities.get(i).get(1) - 1;
                adj.get(u).add(v);
                adj.get(v).add(u);
            }
            boolean[] visited = new boolean[n];
            long clusters = 0;
            for(int i = 0; i < n; i++){
                if(visited[i]) continue;
                clusters++;
                Queue<Integer> subGraph = new LinkedList<>();
                subGraph.offer(i);
                while(!subGraph.isEmpty()){
                    int curr = subGraph.poll();
                    if(visited[curr]) continue;
                    visited[curr] = true;
                    //subGraph.addAll(adj.get(curr));
                    for(Integer next : adj.get(curr)) {
                        if(!visited[next]) subGraph.add(next);
                    }
                }
            }
    
            return (long)(clusters * c_lib) + (long)(n - clusters) * c_road;
        }
    
  • + 0 comments

    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.

  • + 0 comments

    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

    list_cities = set(range(1, n + 1))
    visited_cities = set()
    city_groups = []
    
    for city_pair in cities:
        set_cities = set(city_pair)
        visited_cities.update(set_cities)
        merged = False
    
        for i, group in enumerate(city_groups):
            if group & set_cities:
                city_groups[i] = group | set_cities
                merged = True
                break
    
        if not merged:
            city_groups.append(set_cities)
    
    total_cost = 0
    
    for group in city_groups:
        total_cost += (len(group) - 1) * c_road + c_lib
    
    unvisited_cities = list_cities.difference(visited_cities)
    total_cost += len(unvisited_cities) * c_lib
    
    return total_cost
    
  • + 0 comments

    Branded lanyards can serve as a useful tool while exploring the concept of Roads and Libraries. As both are integral to connectivity, roads symbolize physical infrastructure, while libraries represent hubs of knowledge. Using lanyards, you can keep your IDs, keys, or event passes handy while navigating these essential spaces. Whether for educational trips or professional events, these lanyards are practical and serve as subtle promotional items to showcase your brand.