New update is available. Click here to update.

Last Updated: 10 Apr, 2021

Hard

```
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.
```

```
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.
```

```
You are not required to print the expected output; it has already been taken care of. Just implement the function.
```

```
1 <= T <= 5
1 <= N <= 10
1 <= M <= 10
0 <= cost[i][j] <= 100
Time limit: 1 sec
```

Approaches

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():

- 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.

- Check if βidβ is equal to -1.
- Initialise a βansβ variable with a very large integer which will store the result of the current function call.
- 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))**

- Return βansβ.

Let us observe the recursion tree for first test case of sample test 1 where

βcostβ = [[ 1, 2], [2, 3], [4, 1]].

After observing the tree, weβll find that there are some redundant function calls which means that there are some overlapping sub-problems. The repetition of such sub-problems suggests that we can use dynamic programming to optimise our approach.

The key idea behind a dynamic programming approach is to use memoisation, i.e. weβll save the result of our sub-problem in a matrix so that it can be used later on.

Create a dynamic programming matrix βdpβ of βNβ * (2 ^ βMβ) dimension which will be used to store the results to avoid redundant function calls. dp[id[mask] will store 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 the Least significant bit) is set if the jth element (0th based indexing) of group 2 is already included in the subset.

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

- 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.

- Check if βidβ is equal to -1.
- Check if the answer for this problem already exists in the βdpβ matrix. If it exists, return the answer right away.
- Initialise a βansβ variable with a very large integer which will store the result of the current function call.
- 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))**

- id-th element is connected to only one point from 2nd group. For this case:
- Store the βansβ in βdp[id][mask]β matrix to avoid redundant function calls and also return it.