I recently learned dp bitmasking and tried my first problem: https://www.codechef.com/problems/TSHIRTS
I initially have mask of n bits of 1, each set bit representing that the elephant is not assigned a t-shirt yet.
Here is what I have done:
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize "trapv"
#define ll long long
ll const mod = 1e9+7;
ll dp[100][1<<10];
unordered_set<int> adj[10]; //people: tshirt
int n;
ll solve(int i,int mask) {
if (mask==0)
return 1;
if (i>99)
return 0;
if (dp[i][mask]!=-1) {
return dp[i][mask];
}
ll ans = 0;
for (int j=0;j<n;j++) {
if ((mask & (1<<j))==1 && adj[j].find(i)!=adj[j].end())
ans= (ans+solve(i+1, mask & (~(1<<j))))%mod;
}
// also possible to not assign any person to this tshirt at all
ans= (ans+ solve(i+1, mask))%mod;
dp[i][mask]=ans;
//cout<<i<<" "<<mask<<" "<<ans<<endl;
return ans;
}
int main() {
int t; cin>>t;
while (t--) {
cin>>n;
for (int i=0;i<100;i++) {
for (int j=0;j<(1<<n);j++)
dp[i][j]=-1;
}
for (int i=0;i<n;i++)
adj[i].clear();
string line;
getline(cin, line);
for(int i = 0;i < n; i++) {
int x;
getline(cin, line);
stringstream s(line);
while(s >> x)
adj[i].insert(x-1);
}
cout<<solve(0,(1<<n)-1)<<"\n";
}
return 0;
}
Why does this code not give expected output ?