Dynamic Programming with profile - example 1

This is a problem from TopCoder SRM 532 DIV  2 - 1000 point.

Here is a link to the problem statement :  http://community.topcoder.com/stat?c=problem_statement&pm=11765&rd=14725

For those who are not member of TopCoder, here is a full problem statement.

Problem Statement
	Mr. Dengklek lives in the Kingdom of Ducks, where humans and ducks live together in peace and harmony. One day, the queen of the kingdom challenged Mr. Dengklek with a perplexing puzzle: she gave Mr. Dengklek an N × M board made of wood that consists of N*M squares. She then asked Mr. Dengklek to paint the squares according to these rules: Each square must be either colored or empty. Each colored square must have an even number of adjacent colored squares. Two squares are adjacent if they share a side. For example, here is one valid solution for N=4, M=7: In the above image, black squares denote empty squares and brown squares denote colored squares. Of course, finding one solution to the puzzle is easy: we do not color anything. Instead, the queen asked Mr. Dengklek a much harder question: to count all valid solutions of the puzzle. Help Mr. Dengklek count the solutions and return the result modulo 1,000,000,007. Two solutions are different if there is a square that is colored in one solution and not colored in the other solution.
Definition
	Class: DengklekPaintingSquares Method: numSolutions Parameters: int, int Returns: int Method signature: int numSolutions(int N, int M) (be sure your method is public)
Constraints
-	N will be between 1 and 100, inclusive.
-	M will be between 1 and 8, inclusive.
Examples
0)
	1 1 Returns: 2 Either Mr. Dengklek colors the square, or he does not. Both choices produce a valid solution.
1)
	2 2 Returns: 8 Here are the 8 valid solutions:
2)
	1 3 Returns: 5
3)
	47 7 Returns: 944149920

Approach
Constraints tell us that 1 <= N <= 100 , 1<= M <= 8

We can go through each row, and try every possible combination of each row.
Each row has maximum of 2^M possible combinations, and some of them will be valid.
There are N rows.
This will take O(N * 2^M), and at worst, it will take 100 * 2^8 = 100 * 256 = 256,000 operations => Small enough.

Algorithm
As the post title suggests, we will use DP with profile.
Let's define state, recurrence, and profile.

State :
dp[r][profile]
= number of valid configuration for (r)th row when (r-1)th row, or previous row, has configuration of "profile"

Recurrence:
The validity of the current configuration of the current row depends on the previous row.
For example, if previous row is shaped like ("+" => colored," =" => not colored)

+=

Then possible configurations of the current row are

=+   ==

which will look like

+=     +=
=+     ==

Cases where the current row looks like += and ++ are excluded because such configurations will make colored squared of previous rows have odd number of neighbors.


Profile :
Ternary representation (3 - based representation. ex> Binary : 2 - based representation) of the previous row.
(i)th digit of profile will be
0 : If (i)th square is not colored.
1 : If (i)th square is colored, and has odd number of neighbors.
2 : If (i)th square is colored, and has even number of neighbors.

Coding
Now that we figured out an algorithm, we need to actually implement it.
First thing to note is that "profile" is a number based in 3, or a ternary number.
The problem is that most languages can process decimal and binary numbers, but not ternary numbers.
So we need to make some functions to process ternary numbers properly.

1. pow3[i] = 3^i
2. get3[i][j] = gets (j)th digit of number i
3. set3[i][j][k] = replace (j)th digit of number i with k

Above three functions are enough to handle ternary numbers.

I added comments in my source code to help you understand.

Source Code

class DengklekPaintingSquares {

public:

int numSolutions(int, int);

};

//3^8 = 6561

int mod = 1000000007;

int mem[101][6561];

int R;

int C;

int pow3[9];

int get3[6561][9];

int set3[6561][9][3];

void preCompute()

{

    pow3[0] = 1;

    for(int i=1; i <= 8; i++)

        pow3[i] = 3 * pow3[i-1];

    

    for(int i=0; i < pow3[8]; i++)

        for(int j=0; j <= 8; j++)

            get3[i][j] = (i/pow3[j]) % 3;

    

    for(int i=0; i < pow3[8]; i++)

        for(int j=0; j <=8; j++)

            for(int k=0; k <= 2; k++)

                set3[i][j][k] = i + (k - get3[i][j]) * pow3[j];

}

/*

 Given current row is idx-th row,

 and the previous row has configuration of "mask",

 return number of valid configurations.

 i-th digit of "mask" will be 

 0 : if it is not colored.

 1 : if it is colored, and has odd number of neighbors.

 2 : if it is colored, and has even number of neighbors.

 */

int rec(int idx, int mask)

{

    int& res = mem[idx][mask];

    

    if(res != -1) return res;

    

    res = 0;

    

    if(idx == R)

    {

        /*

         Check validity of the "mask"

         Return 1 is if valid. Else return 0.

         */

        bool isValid = true;

        for(int i=0; i < C; i++)

            if(get3[mask][i] == 1) isValid = false;

        if(isValid) 

            res = 1;

        return res;

    }

    

    /* 

     try all configuration for the current row

     i-th bit of config is 0 if it is not colored,

     i-th bit of config is 1 if it is colored.

     */

    for(int config = 0; config < (1<<C); config++)

    {

        bool isValid = true;

        //check if the current configuration is valid

        //by looking at previous row's configuration, or "mask"

        for(int i=0; i < C; i++)

        {

            bool isColored = ((config>>i) & 1);

            if( (get3[mask][i] == 1 && !isColored) || ( get3[mask][i] == 2 && isColored) )

            {

                isValid = false;

                break;

            }

        }

        

        if(isValid)

        {

            int newConfig = 0;

            

            //make new configuration according to config

            for(int i=0; i < C; i++)

            {

                if( (config>>i) & 1)

                {

                    /* Look up, left, and right */

                    int sum = (get3[mask][i] != 0) ? 1 : 0;

                    

                    if(i > 0)

                        sum = sum + (( (config>>(i-1)) & 1) ? 1 : 0);

                    

                    if(i < C-1)

                        sum = sum + (( (config>>(i+1)) & 1) ? 1 : 0);

                    

                    if(sum%2 == 1) newConfig = set3[newConfig][i][1];

                    else newConfig = set3[newConfig][i][2];

                }

                else

                {

                    newConfig = set3[newConfig][i][0];

                }

            }

            res = (res + rec(idx+1, newConfig)) % mod;

        }

    }

  

    return (res % mod);

}

int DengklekPaintingSquares::numSolutions(int N, int M) {

    R = N;

    C = M;

    

    memset(mem, -1, sizeof(mem));

    

    preCompute();

    

return rec(0,0);

}