2959. Number of Possible Sets of Closing Branches


Problem Description

The problem presents a scenario where a company with n branches is interconnected by a network of roads. The company is looking to reduce travel time by potentially closing down some branches while still maintaining the condition that any remaining branch can be reached from any other branch within a specified maximum distance maxDistance.

The goal is to calculate the number of ways the company can choose which branches to close such that the following criteria are met:

  • All remaining branches are within maxDistance of each other.
  • After closing a branch, it and its connected roads are no longer accessible.

We are given:

  • An integer n representing the number of branches.
  • An integer maxDistance representing the maximum allowable distance between any two branches.
  • An array roads, containing tuples (u, v, w). Each tuple represents a bidirectional road between branches u and v, with w being the length of that road.

Our task is to return the total count of possible sets of branch closures that satisfy the maximum distance requirement.

Intuition

Since the number of branches n is at most 10, a direct approach to enumerating all possible subsets of branches to determine which can be closed is feasible. This is where binary enumeration comes into play.

Binary enumeration uses a binary mask to represent the inclusion (1) or exclusion (0) of each branch in a subset. For each subset represented by the mask, we check the distances between all possible pairs of remaining branches.

To calculate the shortest distances efficiently, we use the Floyd algorithm (also known as Floyd-Warshall algorithm). This algorithm iterates over all combinations of pairs (i, j) of branches as endpoints and employs an intermediate node k to see if the distance between i and j can be shortened by passing through k. If the condition g[i][k] + g[k][j] < g[i][j] holds, we update the distance g[i][j] to the shorter distance found.

This process is repeated for each subset of branches, and after updating the distances, we check if all distances between remaining branches are less than or equal to maxDistance. If they are, we increment our count of valid sets.

By iterating over all subsets and applying the Floyd algorithm to check and tally all that meet the required condition, we can ultimately return the total number of valid branch closure sets.

Learn more about Graph, Shortest Path and Heap (Priority Queue) patterns.

Solution Approach

The solution uses Binary Enumeration and the Floyd Algorithm to tackle the problem of finding all possible subsets of branches that can be closed while ensuring the maximum distance between any two remaining branches does not exceed maxDistance.

Binary Enumeration

Binary Enumeration is a technique that iterates through all subsets of a set, particularly useful when dealing with a small number of elements as we have here (n <= 10). This is implemented by looping from 0 to 2^n - 1, with each value of the loop variable mask representing a unique subset. Bitwise operations are used to determine whether an element (a branch) is part of the current subset.

For example, if n is 3, the subsets represented as binary masks would be 000 (no branches), 001 (just the first branch), 010 (just the second branch), 100 (just the third branch), 011 (first and second branches), and so forth up to 111 (all branches).

Floyd Algorithm

The Floyd Algorithm is used to find the shortest paths between all pairs of nodes in a weighted graph. It is a dynamic programming approach that incrementally improves the answer by considering whether a path from i to j can be made shorter by passing through an intermediate node k. In our solution, g is a 2D list initialized with inf (representing infinity) to store distances between branches. During each iteration, the algorithm updates g with new minimum distances found through intermediate nodes:

1for k in range(n):
2    if mask >> k & 1:
3        g[k][k] = 0
4        for i in range(n):
5            for j in range(n):
6                if g[i][k] + g[k][j] < g[i][j]:
7                    g[i][j] = g[i][k] + g[k][j]

In the snippet above, the condition mask >> k & 1 is checking if the k-th branch is included in the current subset (mask). If it is, the Floyd algorithm runs, continuously updating g[i][j] to reflect the shortest distance between branches i and j.

We follow the standard Floyd Algorithm pattern:

  1. Initialize the distance between all pairs to infinity, except the distance from a branch to itself, which is 0.
  2. Update the distances using the information from the roads array.
  3. Perform relaxation for each pair (i, j) over all possible intermediate nodes k.

After updating all distances with the Floyd algorithm, we check if every pair of remaining branches satisfies the distance requirement:

1if all(
2    g[i][j] <= maxDistance
3    for i in range(n)
4    for j in range(n)
5    if mask >> i & 1 and mask >> j & 1
6):
7    ans += 1

This piece of code iterates over all possible pairs of branches (i, j) in the current subset. If the condition g[i][j] <= maxDistance is true for every pair, it implies that the branches in this subset satisfy the problem conditions. Thus, we increment ans, the counter variable keeping track of the number of valid subsets.

In conclusion, the combination of Binary Enumeration to generate branch subsets, along with the Floyd Algorithm for shortest path calculation, effectively enables us to find the number of valid branch closures that satisfy the maximal inter-branch distance constraint.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a simplified example to illustrate the solution approach. Assume we have n = 3 branches and maxDistance = 4. The roads between the branches are provided in the array roads as [(0, 1, 2), (1, 2, 5)]. This means we have three branches: branch 0, branch 1, and branch 2. Branch 0 is connected to branch 1 by a road of length 2, and branch 1 is connected to branch 2 by a road of length 5.

Our task is to find all possible subsets of branches to close, so that the remaining branches are all within maxDistance of each other.

Binary Enumeration

For binary enumeration, we will consider all subsets of the three branches:

  1. Subset 000 (mask = 0): No branches are open.
  2. Subset 001 (mask = 1): Only branch 0 is open.
  3. Subset 010 (mask = 2): Only branch 1 is open.
  4. Subset 011 (mask = 3): Branches 0 and 1 are open.
  5. Subset 100 (mask = 4): Only branch 2 is open.
  6. Subset 101 (mask = 5): Branches 0 and 2 are open.
  7. Subset 110 (mask = 6): Branches 1 and 2 are open.
  8. Subset 111 (mask = 7): All branches are open.

Floyd Algorithm and Validation

For each mask, we apply the Floyd Algorithm. Let's consider the subset 011 (mask = 3) as an example:

  1. Initialize the 2D list g with distances from each branch to every other branch as infinity except for the distances to itself as 0.

  2. Update g based on the roads: since we have roads [(0, 1, 2), (1, 2, 5)], we update g to reflect these distances:

    • g[0][1] = 2
    • g[1][0] = 2 (since the road is bidirectional)
    • g[1][2] = 5
    • g[2][1] = 5
  3. Apply the Floyd Algorithm considering only branches present in the subset 011 (branches 0 and 1 are open):

    • Initially, g[0][1] is 2 and g[1][0] is also 2.
  4. The shortest distance between all open branches in this subset has been calculated. We check if all distances are within maxDistance:

    • g[0][1] <= 4 holds true, so this subset is one valid closure set.

We repeat this for all subsets and validate if they meet the maxDistance requirement. In this example, subset 110 (branches 1 and 2 open) does not meet the requirement because the distance between branches 1 and 2 is 5, which is greater than maxDistance.

Counting Valid Sets

After applying the binary enumeration and the Floyd Algorithm, we find that the subset 011 is the only valid set that meets the criteria among the non-empty sets (subset 111 is always valid since no branches are closed). Thus, for this example, there are 2 valid sets (including the all-open case). Therefore, the count of possible ways the company can choose which branches to close while maintaining the maximum distance requirement is 2.

Solution Implementation

1from typing import List
2
3class Solution:
4    def numberOfSets(self, num_vertices: int, max_distance: int, edges: List[List[int]]) -> int:
5        # Initialize a counter for the number of sets meeting the conditions
6        num_sets = 0
7      
8        # Iterate through each subset of vertices represented as a bitmask
9        for bitmask in range(1 << num_vertices):
10            # Create the graph with initially infinite distances between vertices
11            graph = [[float('inf')] * num_vertices for _ in range(num_vertices)]
12          
13            # Fill in the graph with the actual distances from the roads given
14            for u, v, weight in edges:
15                if bitmask >> u & 1 and bitmask >> v & 1:
16                    # Update the distance between connected vertices if it's less than the existing one
17                    graph[u][v] = min(graph[u][v], weight)
18                    graph[v][u] = min(graph[v][u], weight)
19          
20            # Apply the Floyd-Warshall algorithm to find all pairs shortest paths
21            for k in range(num_vertices):
22                if bitmask >> k & 1:
23                    graph[k][k] = 0  # Distance to itself is always 0
24                    # Compare and update distances for each pair using the intermediate vertex k
25                    for i in range(num_vertices):
26                        for j in range(num_vertices):
27                            if graph[i][k] + graph[k][j] < graph[i][j]:
28                                graph[i][j] = graph[i][k] + graph[k][j]
29          
30            # Check if all pairs of vertices in the subset have a path no longer than max_distance
31            valid_subset = all(
32                graph[i][j] <= max_distance
33                for i in range(num_vertices)
34                for j in range(num_vertices)
35                if bitmask >> i & 1 and bitmask >> j & 1
36            )
37          
38            # If all pairs satisfy the condition, increment the counter
39            if valid_subset:
40                num_sets += 1
41      
42        # Return the total number of valid subsets
43        return num_sets
44
1class Solution {
2    public int numberOfSets(int n, int maxDistance, int[][] roads) {
3        int answer = 0; // Initialize the answer variable to store the count of subsets.
4        // Iterate over each possible subset of nodes by examining each bitmask from 0 to 2^n - 1.
5        for (int mask = 0; mask < (1 << n); ++mask) {
6            int[][] graph = new int[n][n]; // Initialize the adjacency matrix for the graph based on the number of nodes.
7            // Loop over all nodes in the graph and set distances to a very high value, since we are looking for the minimum.
8            for (int[] row : graph) {
9                Arrays.fill(row, (1 << 29)); // Use 1 << 29 as the representation of infinity.
10            }
11            // Fill in the adjacency matrix with actual road distances where applicable.
12            for (var road : roads) {
13                int u = road[0]; // Start node
14                int v = road[1]; // End node
15                int w = road[2]; // Distance
16                // If both nodes are included in the current subset,
17                // update the graph with the minimum distance between u and v.
18                if (((mask >> u) & 1) == 1 && ((mask >> v) & 1) == 1) {
19                    graph[u][v] = Math.min(graph[u][v], w);
20                    graph[v][u] = Math.min(graph[v][u], w);
21                }
22            }
23            // Perform the Floyd-Warshall algorithm to find all shortest paths in the subset graph.
24            for (int k = 0; k < n; ++k) {
25                if (((mask >> k) & 1) == 1) {
26                    // Distance from a node to itself is always 0.
27                    graph[k][k] = 0;
28                    // Compute the shortest paths through the current node.
29                    for (int i = 0; i < n; ++i) {
30                        for (int j = 0; j < n; ++j) {
31                            graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
32                        }
33                    }
34                }
35            }
36            int isValidSubset = 1; // A flag to check if the subset satisfies the maxDistance constraint.
37            // Check if all pairs of nodes in the subset have a distance less than or equal to maxDistance.
38            for (int i = 0; i < n && isValidSubset == 1; ++i) {
39                for (int j = 0; j < n && isValidSubset == 1; ++j) {
40                    if (((mask >> i) & 1) == 1 && ((mask >> j) & 1) == 1) {
41                        if (graph[i][j] > maxDistance) {
42                            isValidSubset = 0; // The subset violates the maxDistance constraint, so it's not valid.
43                        }
44                    }
45                }
46            }
47            answer += isValidSubset; // Add the valid subset to the count.
48        }
49        return answer; // Return the total count of valid subsets.
50    }
51}
52
1#include <vector>
2#include <cstring>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9    int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) {
10        int answer = 0; // Initialize the answer to zero
11        // Loop through each subset of cities
12        for (int mask = 0; mask < (1 << n); ++mask) {
13            int graph[n][n];
14            memset(graph, 0x3f, sizeof(graph)); // Initialize the graph with high values
15
16            // Go through each road and check if both cities are in the subset represented by the mask
17            for (auto& edge : roads) {
18                int u = edge[0], v = edge[1], w = edge[2];
19                if ((mask >> u & 1) && (mask >> v & 1)) {
20                    graph[u][v] = min(graph[u][v], w); // Update graph with the smaller weight
21                    graph[v][u] = min(graph[v][u], w);
22                }
23            }
24
25            // Apply Floyd-Warshall to calculate shortest paths for the selected subset
26            for (int k = 0; k < n; ++k) {
27                if (mask >> k & 1) {
28                    graph[k][k] = 0; // Distance to self is zero
29                    for (int i = 0; i < n; ++i) {
30                        for (int j = 0; j < n; ++j) {
31                            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
32                        }
33                    }
34                }
35            }
36
37            int isSetValid = 1; // A flag to check if the subset forms a valid set of cities
38            // Validate that all distances between selected cities are within maxDistance
39            for (int i = 0; i < n && isSetValid == 1; ++i) {
40                for (int j = 0; j < n && isSetValid == 1; ++j) {
41                    if ((mask >> i & 1) && (mask >> j & 1) && graph[i][j] > maxDistance) {
42                        isSetValid = 0; // Set is not valid if any distance exceeds maxDistance
43                    }
44                }
45            }
46
47            answer += isSetValid; // Add to the count if the subset is a valid set
48        }
49        return answer; // Return the final count of valid sets
50    }
51};
52
1// Define the function that calculates the number of sets of cities where the maximum distance between any two cities in the set does not exceed maxDistance.
2function numberOfSets(n: number, maxDistance: number, roads: number[][]): number {
3    let count = 0; // Initialize the number of valid sets to zero
4
5    // Iterate over all the possible sets of cities represented by a bitmask
6    for (let mask = 0; mask < 1 << n; ++mask) {
7        // Initialize the adjacency matrix with Infinity, indicating no direct path between the cities
8        const graph: number[][] = Array.from({ length: n }, () => Array(n).fill(Infinity));
9      
10        // Update the graph with the distances of the roads where both cities are included in the current set (bitmask)
11        for (const [city1, city2, distance] of roads) {
12            if ((mask >> city1) & 1 && (mask >> city2) & 1) {
13                graph[city1][city2] = Math.min(graph[city1][city2], distance);
14                graph[city2][city1] = Math.min(graph[city2][city1], distance);
15            }
16        }
17      
18        // Perform Floyd-Warshall to find the shortest paths between all pairs of cities in the current set
19        for (let k = 0; k < n; ++k) {
20            if ((mask >> k) & 1) {
21                graph[k][k] = 0;
22                for (let i = 0; i < n; ++i) {
23                    for (let j = 0; j < n; ++j) {
24                        graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
25                    }
26                }
27            }
28        }
29      
30        // Check if all distances between the cities in the current set are within the maxDistance
31        let validSet = true;
32        for (let i = 0; i < n && validSet; ++i) {
33            for (let j = 0; j < n && validSet; ++j) {
34                if ((mask >> i) & 1 && (mask >> j) & 1 && graph[i][j] > maxDistance) {
35                    // If any distance exceeds maxDistance, the set is invalid
36                    validSet = false;
37                }
38            }
39        }
40      
41        // If the set is valid, increment the count
42        if(validSet) {
43            count++;
44        }
45    }
46  
47    // Return the total count of valid sets
48    return count;
49}
50

Time and Space Complexity

The time complexity of the provided code is O(2^n * (n^3 + m)). This complexity comes from several factors:

  • There is an outer loop that iterates over all possible subsets of n departments, which results in 2^n iterations.
  • Inside this loop, the code initializes a graph with n*n entries all set to infinity, which takes O(n^2) time; however, this is not the dominating factor.
  • For every subset, the code then updates a matrix g based on the roads. Updating the graph entries for each road (m roads total) has a complexity of O(m) for each subset.
  • The Floyd-Warshall algorithm is used to compute the shortest paths between all pairs of nodes in the graph. This algorithm has a time complexity of O(n^3) since it contains a triple nested loop that iterates over all pairs (i, j) for each intermediate node k.
  • Finally, a final check is performed to count how many sets have all distances within the maxDistance. This check is O(n^2) for every subset as it iterates over all pairs (i, j).

Therefore, considering both the Floyd-Warshall algorithm and the updates for each subset, the total time complexity within the outer loop is O(n^3 + m), and this is then multiplied by the number of subsets, which is 2^n.

The space complexity of the code is O(n^2). This is because the code maintains a two-dimensional array g which has n rows and n columns, with n being the number of departments.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)


Recommended Readings