I came across this problem and could not think of a good solution. The problem is as follows
There are N CS courses and N EEE courses, both numbered 1, 2, ... , N.
For each i, j (1 ≤ i, j ≤ N), the compatibility of CS course i and EEE course j is given as an integer Aij. If Aij = 1, CS course i and EEE course j do not clash; if Aij = 0, they clash.
Ravan is trying to make N pairs, each containing a CS course and a EEE course that do not clash. Here, each CS course and each EEE course must belong to exactly one pair.
Find the number of ways in which Ravan can make N pairs, modulo 10^9 + 7.
Ex.
0 1 1
1 0 1
1 1 1
res : 3
Explanation
Here there are 3 ways to make pairs:
(1,2),(2,1),(3,3)
(1,2),(2,3),(3,1)
(1,3),(2,1),(3,2)
Where (i,j) is pair of CS i course and EEE j course
To solve the above problem I worte a simple dfs function but it it isn't correct is seems. Also It is a very slow implementation. My approach was as follows:
int counter=0;
void dfs(vector<vector<int>>&nums, int n, vector<bool>&visit, int c){
if(c == n-1){
counter++;
return;
}
for(int i=0; i<n; i++){
if(nums[i][c]==0 || visit[i])continue;
visit[i] = true;
dfs(nums, n, visit, c+1);
visit[i] = false;
}
}
void solve(vector<vector<int>>&nums, int n){
vector<bool>visit(n, false);
dfs(nums, n, visit, 0);
cout << counter%1000000007;
}
Am I thinking in the right direction for this problem? What else can be done to solve this problem and that too efficiently? Any help would be valuable. Thanks!
This is just an expansion of @amit's comment that this looks like Inclusion-Exclusion.
First we take the number of ways to make N pairs. Which is simply N!. In your example, this is 6.
all sets of pairs
(1, 1), (2, 2), (3, 3)
(1, 1), (2, 3), (3, 2)
(1, 2), (2, 1), (3, 3)
(1, 2), (2, 3), (3, 1)
(1, 3), (2, 1), (3, 2)
(1, 3), (2, 2), (3, 1)
Then for each pair we don't want, we subtract off the number of ways to make N pairs including that forbidden pair. Which is the number of such pairs times (N-1)!. In your example this is 4. (2 pairs, each of which is in 2 sets of N pairs.)
Contains forbidden pair (1, 1)
(1, 1), (2, 2), (3, 3)
(1, 1), (2, 3), (3, 2)
Contains forbidden pair (2, 2)
(1, 1), (2, 2), (3, 3)
(1, 3), (2, 2), (3, 1)
But ways of making N pairs including 2 forbidden pairs have now been subtracted off twice. (That is, we added (1, 1), (2, 2), (3, 3) once, subtracted it twice, and now it is counted with a -1.) So we need to add them back in. Add 1 back in:
Contains both forbidden pairs (1, 1), (2, 2)
(1, 1), (2, 2), (3, 3)
If there was a set of 3 forbidden pairs, we'd have to add those back in. But there aren't. So our final calculation is:
6 - (2 + 2) + 1
Which gives 3, as desired.
So what about doing this calculation for a much larger N? Well we know know how to calculate N!, (N-1)!, (N-2)! and so on. The tricky bit is how many forbidden pairs, 2 pairs, 3 pairs and so on are there.
And for that we can use dynamic programming. Build a dp such that dp[k][l] is the number of sets of l forbidden pairs (i, j) there are that can appear together in an assignment for which i <= k. We start with dp[0] = [1, 0, 0, ...]. And dp[N] will give you all of the counts of how many forbidden sets of pairs there are of each size that can be assigned together.
In your example, that structure should wind up:
dp = [
[1, 0, 0, 0],
[1, 1, 0, 0],
[1, 2, 1, 0],
[1, 2, 1, 0],
]
From which we get the calculation
3! * dp[3][0] - 2! * dp[3][1] + 1! * dp[3][2] + 0! * dp[3][3]
= 6 * 1 - 2 * 2 + 1 * 1 - 1 * 0
= 3
That should be enough to get you going.