Monday, February 13, 2012

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.

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

1. Thanks, I've learnt a lot with this post, by the way, Dynamic Programming is a hard topic on algorithms, profiles makes it even harder, and I'm still struggling to understand why use ternary numbers in this problem.

1. Good to hear that this post was helpful.

In this problem, ternanry numbers to represent
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.

I am guessing that why we need 2 states to represent colored square.
You need to notice that a colored square with odd number of neighbors and a colored square with even number of neighbors are different.

Let's say you are currently processing square X.
If there is a colored square with odd number of neighbors above square X, you can color square X.
However, if there is a colored square with even number of neighbors above square X, you can NOT color square X.

If you are still unsure, feel free to ask me again :-)

2. Thank you for your article. But I have some questions.
In above example, I think we don't need to use ternary. We can use binary because we can assign 0 for point of odd degree and 1 for point for even degree. Is that right?
And is this dynamic with profile more efficient than scanning all combinations of rows?

3. In my above post, I say we use binary because not colored point is point of even degree (degree = 0).

4. really awesome, but i so wish u could make it more consistent rather than using braces arbitrarily,makes it tough to understand.