# Assign SPOJ Re:dynamic programming with bitmask

A few days ago I asked how to solve the ASSIGN problem of SPOJ through bit masking and got a satisfactory answer here

I am still having difficulty in coding the program so could any one give me an explanation on how to code thus program

1 Like

Hi again :),
I can tell you how I did it. Maybe it’s not that bad if I just show you my AC implementation because it is hard to code something for the first time. I will give you tips though.

//Program: assign
//Author: gary
//Date: 13/08/2014
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
#define SZ(x) ( (int) (x).size() )
#define dbg(x) cerr << #x << " = " << x << endl;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> i2;
const int MAX_N = 20;
#define ison(x, i) (((x) >> (i)) & 1)
int n, T;
ll dp[1 << MAX_N];
int a[MAX_N][MAX_N];

int main(){
ios::sync_with_stdio(0);
cin >> T;
while(T--){
cin >> n;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> a[i][j];
}
}
int i, j, k;
dp[0] = 1;
for(i = 1; i < (1 << n); i++){
j = 0;
dp[i] = 0;
for(k = 0; k < n; k++){
j += ison(i, k);
}
for(k = 0; k < n; k++){
if(a[j - 1][k] && ison(i, k)){
dp[i] += dp[i & ~(1 << k)];
}
}
}
cout << dp[(1 << n) - 1] << endl;
}
return 0;
}

The first few lines aren’t interesting, because it’s just processing the input. I save in the a[i][j] array whether student i likes the subject j.

The bitmask technique goes like this - let’s say we have a number x. And now let’s examine x in the binary form, we get like 10010. We read from right to left, this means, x corresponds to the set {1,4}. If bit i is on in x, then we include i in the set. Now there are few bitmask processing techniques you should know, which I learned from Topcoder. I will highlight those, you will need. (But please read the Topcoder article first)

( (x) >> (i) ) & 1)

Checks whether bit i is on in x. Or in terms of set theory, if i is included in the set x.

x & ~(1 << i)

Sets the bit i in bitmask x to 0. Or in terms of set theory, set x without i.

Now let’s examine my implementation. As I mentioned in the other answer before, the base case is f(0, {}) = 1. This corresponds to the following code line.

dp[0] = 1; // Yeah simple as that :) Zero has 0 bits on, thus it corresponds to the empty set {}

I am doing the whole dynamic programming process iteratively. I will calculate the dp[] array for i = 1…(1<<n)-1. Why up to (1 << n) - 1? Because (1 << n) - 1 is a number, which has the first n bits on and this stands for the {0,1,…,n-1} set. Care that my i variable will correspond to the set s, which I always mentioned in the recurrence.

I am already using the memory saving trick, which I mentioned in the answer before, which reduces the memory by a factor of O(n). In the following code, I am therefore deriving the number of the student.

j = 0;
for(k = 0; k < n; k++){
j += ison(i, k);
} // just counting the number of elements in i

I mentioned the recurrence:

f(n, s) = sum of all f(n - 1, s without e) for each e in s, which the student n likes

Do you see how the following code corresponds to this recurrence above ?

for(k = 0; k < n; k++){
if(a[j - 1][k] && ison(i, k)){
dp[i] += dp[i & ~(1 << k)];
}
}

I won’t explain everything because thinking will strengthen your skills. Hopefully you will get AC soon.

19 Likes

I won’t say I completely got it but yes I got more than the previous time but now I won’t ask more because I think if can now surely code thus program. And gdisastery1 thanks man for so much patience that you explained the whole code, thanks.

No problem I do all the best, such that you can understand it.

2 Likes

Gdisastery your explanation is very good, just I spent 4 hours on this but could’t figure this out

`f(n, s) = sum of all f(n - 1, s
without e) for each e in s, which the
student n likes

Do you see how the following code
corresponds to this recurrence above ?

for(k = 0; k < n; k++){

if(a[j - 1][k] && ison(i, k)){
dp[i] += dp[i & ~(1 << k)];
}

}`

@toppratyush007

Hi, I modified the code a little bit

for(k = 0; k < n; k++){ // We iterate through all subjects k = 0..n-1
if(a[j - 1][k] == 0) continue; // if k is not a subject j - 1 likes, then continue
if(!ison(i, k)) continue;      // if k is not in the set i, then we also continue
// at here you should see, that k is a subject, that student j - 1 likes and is in the set i

dp[i] += dp[i & ~(1 << k)];    // i & ~(1 << k) represents the set i without subject k
}
2 Likes

Hey buddy gdisastery1 i coded the problem and my code is this but getting SIGGEV error can’t ask for more help b’cause you already did a lot but please help me out sorry for disturbing you again

Thanks again.

What does the dp[] array store?
I am assuming that it stores the number of ways of allotting k=0…n-1 subjects to the subset i that is the outermost loop, but then every single element can have more than way,(why are we even checking for kth subject in subset i of students), but here dp[1],dp[2],d[4],… all are 1.
I will appreciate if you could help me clear this concept.

Thanks again gdisastery1 for your comment. I did it but now as i wrote above i am getting TLE and i am using your only logic please see my code …

Thanks again thats why i love codechef…

1 Like

Don’t use map! It’s very slow

Just use a array like you did before.

1 Like

Thanks buddy AC at last ! Phew !!
Thanks again.

Sorry to quote myself , but I think mate you did not happen to look at my query

What does the dp[] array store? I am assuming that it stores the number of ways of allotting k=0…n-1 subjects to the subset i that is the outermost loop, then every single element can have more than way(exactly k subjects that he likes), but here dp[1],dp[2],d[4],dp[8]… all are 1.

I will appreciate if you could help me clear this concept.

No problem Glad you got AC

1 Like

dp[s] = f(s) in my other answer. Check it out!

Hey
Can someone please help in debugging this code for the SPOJ problem ASSIGN?