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 branchesu
andv
, withw
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:
- Initialize the distance between all pairs to infinity, except the distance from a branch to itself, which is 0.
- Update the distances using the information from the
roads
array. - Perform relaxation for each pair
(i, j)
over all possible intermediate nodesk
.
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 EvaluatorExample 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:
- Subset
000
(mask = 0): No branches are open. - Subset
001
(mask = 1): Only branch 0 is open. - Subset
010
(mask = 2): Only branch 1 is open. - Subset
011
(mask = 3): Branches 0 and 1 are open. - Subset
100
(mask = 4): Only branch 2 is open. - Subset
101
(mask = 5): Branches 0 and 2 are open. - Subset
110
(mask = 6): Branches 1 and 2 are open. - 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:
-
Initialize the 2D list
g
with distances from each branch to every other branch as infinity except for the distances to itself as 0. -
Update
g
based on theroads
: since we have roads[(0, 1, 2), (1, 2, 5)]
, we updateg
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
-
Apply the Floyd Algorithm considering only branches present in the subset
011
(branches 0 and 1 are open):- Initially,
g[0][1]
is 2 andg[1][0]
is also 2.
- Initially,
-
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 in2^n
iterations. - Inside this loop, the code initializes a graph with
n*n
entries all set to infinity, which takesO(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 ofO(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 nodek
. - Finally, a final check is performed to count how many sets have all distances within the
maxDistance
. This check isO(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.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Shortest Path Between A and B Prereq BFS on Graph problems graph_bfs Given an unweighted connected graph return the length of the shortest path between two nodes A and B in terms of the number of edges Assume there always exists a path between nodes A and B Input graph
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue