Minimum Cost To Connect Two Groups Of Points

Hard
0/120
Average time to solve is 15m
profile
Contributed by
27 upvotes
Asked in company
Snapdeal Ltd.

Problem statement

You are given two groups of points where the first group has ‘N’ points, the second group has ‘M’ points, and ‘N’ >= ‘M’.

You are also given a “cost” matrix of ‘N’ * ‘M’ dimensions whose (i, j)th element denotes the cost of the connection between ith point of group 1 and jth point of group 2. The groups are connected if each point in both groups is connected to one or more points in the opposite group. In other words, each point in the first group must be connected to at least one point in the second group, and each point in the second group must be connected to at least one point in the first group.

Now you are supposed to find the minimum cost it takes to connect the two groups.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first input line of each test case contains two integers ‘N’ and ‘M’, denoting the number of rows and columns of the “cost” matrix.

Each of the next ‘N’ lines contains ‘M’ space-separated integers denoting the elements of the “cost” matrix.
Output Format : 
For each test case, print an integer denoting the minimum cost it takes to connect the two groups.

Print the output of each test case in a separate line.
Note : 
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 5
1 <= N <= 10
1 <= M <= 10
0 <= cost[i][j] <= 100


Time limit: 1 sec
Sample Input 1 :
2
3 2
1 2
2 3
4 1
2 2
2 5
3 4
Sample Output 1 :
4
6
Explanation of Sample Output 1 :
For the first test case, the optimal way of connecting the group is as following:

TestCase1

The minimum cost will be 4.

For the second test case, the optimal way of connecting the group is as following:

TestCase2

The minimum cost will be 6.
Sample Input 2 :
2
1 1
5
1 3
1 2 3
Sample Output 2 :
5
6
Explanation of Sample Output 2 :
For the first test case, there is only one possible way of connection and its cost is 5.

For the second test case, the minimum cost will be 6.
Hint

Pick each id's group from group1 and try to connect all the subset of group2 and choose minimum. Use BitMasking to handle the subset.

Approaches (2)
Brute Force

Let us try to break down the problem into sub-problems. Consider a function    

getMinCost(int id, int mask)

which returns the minimum cost to connect the first “id” elements of group 1 to a subset of group 2 which is denoted by “mask”. Here, the “mask” is an integer whose jth bit (from Least significant bit) is set if the jth element (0th based indexing) of group 2 is already included in the subset.  


 

Now, let us see what happens when we try to connect the id-th element of group 1 with some (one or more) elements of group 2. We’ll have to add the cost associated with the new connection and also we’ll have to update the “mask” if a new element from group 2 is included. 


 

Now, consider the following steps for implementing the function getMinCost():

  1. Base Case:
    • Check if “id” is equal to -1.
      • If “mask” is equal to (1 << M) - 1, which means every point of the second group is included in the connection. So, return 0.
      • Otherwise, return a very large integer.
  2. Initialise a “ans” variable with a very large integer which will store the result of the current function call.
  3. Now, iterate through the points of the second group using the variable ‘j’. These are the following two options possible.
    • id-th element is connected to only one point from 2nd group. For this case: ans = min(ans,cost[id][j] + getMinCost(id - 1, mask | (1 << j))
    • Id-th element is connected to more than one points from group 2 and j-th point is one of them. For this case, if jth bit is not set: ans = min(ans, cost[id][j] + getMinCost(id, mask | (1 << j))
  4. Return “ans”.
Time Complexity

O(N ^ M), Where ‘N’ and ‘M’ denotes the number of rows and number of columns, respectively.


Since we are considering every possibility of connecting the points and there are N^M ways of connecting them. So, the overall time complexity will be O(N^M).

Space Complexity

O(N), Where ‘N is the number of rows.

 

Since we are using a recursive function and in the worst case, there may be ‘N’ state in the call stack. So the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Minimum Cost To Connect Two Groups Of Points
Full screen
Console