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:
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 



Constraints 

  N will be between 1 and 100, inclusive.  
  M will be between 1 and 8, inclusive.  
Examples 

0)  


1)  


2)  


3)  

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 (r1)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[i1];
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 idxth row,
and the previous row has configuration of "mask",
return number of valid configurations.
ith 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
ith bit of config is 0 if it is not colored,
ith 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>>(i1)) & 1) ? 1 : 0);
if(i < C1)
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);
}
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.
ReplyDeleteGood to hear that this post was helpful.
DeleteIn 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 :)
Thank you for your article. But I have some questions.
ReplyDeleteIn 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?
In my above post, I say we use binary because not colored point is point of even degree (degree = 0).
ReplyDeleteThis comment has been removed by the author.
DeleteBoth are different, having no color doesn't have to satisfy that adjacent should be even.
Deletereally awesome, but i so wish u could make it more consistent rather than using braces arbitrarily,makes it tough to understand.
ReplyDelete