To strengthen the concept of DP+bitmasks

SPOJ(6072. Chocolate)

Chocolate is a problem from the world final ACM-ICPC 2010. You can see the text here My solution:                     Well first we can see that the n <= 15 and x,y <= 100, There is 2^n way of get a subset of the all pieces.                                           For example:                          n =  4;                          pieces:6,3,2,1; In the binary representation of the mark a 0 meant that don't take this piece and a 1 that take this piece.                                                   mask (from 0 to 2^4)  binary representation  Piece  Sum of piece  0  0000  {}  0  1  0001  {1}  1  2  0010  {2}  2  3  0011  {2,1}  3  4  0100  {3}  3  5  0101  {3,1}  4  6  0110  {3,2}  5  7  0111  {3,2,1}  6  8  1000  {6}  6  9  1001  {6,1}  7  10  1010  {6,2}  8  11  1011  {6,2,1}  9  12  1100  {6,3}  9  13  1101  {6,3,1}  10  14  1110  {6,3,2}  11  15  1111  {6,3,2,1}  12  We can do a function that take a mask ,x ,y and return true or false if with the piece of this mask we can get a rectangle of (x,y) bool Solve(int mask , int x , int y) {        if(Sum[mask]!= x*y) return false;                 if(ActivePieces(mask)==1) return true;               foreach(sub)//that sub is a subset of mask mean that all bit that is 1 in sub have to be 1 in mask and mask > sub        {            sub1 = mask - sub;            //now we can to break the chocolate of (x,y), for can break it parallel to X, y have to divide to Sum[sub] and Sum[sub1].           if(Sum[sub]%y == 0  and  Sum[sub1]%y == 0)             {                     if(Solve(sub,Sum[sub]/y,y) and Solve(sub1,Sum[sub1]/y,y))                          return true;             }           // now the same parallel to Y            if(Sum[sub]%x == 0  and  Sum[sub1]%x == 0)             {                     if(Solve(sub,Sum[sub]/x,x) and Solve(sub1,Sum[sub1]/x,x))                          return true;             }        }      return false; } Now see that we can to have 2^n*x*y state. for the max number of that can be 327680000 so it is big but we can notice that x or y are linked.If I have the mask and x I can calculate the y so we have only 3276800. so my idea for save is (mask,max(x,y)) and I can use memorization for do it faster. The other problem is:       How can I do the cycle of sub ??       if you have this problem you have to see this tutorial from topcoder.       My Code:                  bool DP(int mask, int x , int y) { if(x > y) x^=y^=x^=y;   if(S[mask]!=x*y) return false;   if((mask & (mask-1)) == 0) return true;   if(Y[mask][y]) return M[mask][y];   Y[mask][y] = 1;     for(int mask1 =((mask-1)& mask);mask1;mask1 = ((mask1-1) & mask)){ if((S[mask1] % x == 0) && DP(mask1,x,S[mask1]/x) && DP(mask-mask1,x,S[mask-mask1]/x)) { M[mask][y] = 1; return 1; } if((S[mask1] % y == 0) && DP(mask1,y,S[mask1]/y) && DP(mask-mask1,y,S[mask-mask1]/y)) { M[mask][y] = 1; return 1; } } M[mask][y] = 0; return 0; }