Assign SPOJ Re:dynamic programming with bitmask

general
1

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

http://discuss.codechef.com/questions/49559/dynamic-programming-bit-masking

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

1 Like
2

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
3

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)];
 }

}`

Please help me with understanding the transformation of recurrence.

4

@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
5

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 :slight_smile: sorry for disturbing you again

Thanks again.

6

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
7

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

8

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.

9

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

Thanks in advance

10

Keep this in mind, Use map only when extremely necessary as it adds a logn constant factor to your running time.

11

Hi gdisastery1 ! The TopCoder link you have provided is not working. Please help !
The link you gave Topcoder

1 Like
12

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.

13

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

2 Likes
14

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.

15

Don’t use map! It’s very slow :smiley:

Just use a array like you did before.

1 Like
16

No problem :slight_smile: Glad you got AC

1 Like
17

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