We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Possible Sets of Closing Branches

Difficulty: Hard

Problem Description

There is a company with n branches across the country, some of which are connected by roads. Initially, all branches are reachable from each other by traveling some roads. The company has realized that they are spending an excessive amount of time traveling between their branches. As a result, they have decided to close down some of these branches (possibly none). However, they want to ensure that the remaining branches have a distance of at most maxDistance from each other. You are given integers n, maxDistance, and a 0-indexed 2D array roads, where roads[i] = [u_i, v_i, w_i] represents the undirected road between branches u_i and v_i with length w_i. Return the number of possible sets of closing branches, so that any branch has a distance of at most maxDistance from any other.

Key Insights

  • The problem can be modeled as a graph where branches are nodes and roads are edges with weights representing the distances.
  • We need to identify all possible subsets of branches and check if the remaining branches can be connected within the given maxDistance.
  • The number of subsets of branches can be calculated using bit manipulation, given that n is small (maximum of 10).
  • For each subset, we can use Dijkstra's algorithm or Floyd-Warshall algorithm to determine the minimum distances between the remaining branches.

Space and Time Complexity

Time Complexity: O(2^n * (n^3)), where 2^n is the number of subsets and n^3 is the time complexity of the Floyd-Warshall algorithm for distance calculations.

Space Complexity: O(n^2), for storing the distance matrix.

Solution

To solve the problem, we can follow these steps:

  1. Construct a distance matrix from the given roads using the Floyd-Warshall algorithm to calculate the shortest paths between all branches.
  2. Generate all possible subsets of branches using bit manipulation.
  3. For each subset, check if the remaining branches are all within the maxDistance from each other using the precomputed distance matrix.
  4. Count all valid subsets that satisfy the distance requirement.

Code Solutions

def countPossibleSets(n, maxDistance, roads):
    from itertools import combinations
    import sys
    
    # Initialize the distance matrix
    dist = [[sys.maxsize] * n for _ in range(n)]
    
    # Populate the distance matrix with given roads
    for u, v, w in roads:
        if w < dist[u][v]:  # Handle multiple edges
            dist[u][v] = w
            dist[v][u] = w
    
    # Set distance to self as 0
    for i in range(n):
        dist[i][i] = 0
    
    # Floyd-Warshall algorithm to find the shortest paths between all pairs
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    count = 0
    
    # Check all possible subsets of branches
    for mask in range(1 << n):  # 2^n subsets
        valid = True
        
        # Check if the remaining branches are within maxDistance
        remaining = [i for i in range(n) if (mask & (1 << i)) == 0]
        for i in remaining:
            for j in remaining:
                if i != j and dist[i][j] > maxDistance:
                    valid = False
                    break
            if not valid:
                break
        
        if valid:
            count += 1  # Count this valid subset
    
    return count

# Example usage:
print(countPossibleSets(3, 5, [[0, 1, 2], [1, 2, 10], [0, 2, 10]]))  # Output: 5
← Back to All Questions