### aman_naughty's blog

By aman_naughty, history, 10 months ago, , Code : code

My approach is : For any {i,j} I maintain 4 colors dp[i][j],dp[i][j],dp[i][j] and dp[i][j];

dp[i][j][k] denotes the number of ways to fill the board[0..i][0..j] using the color k at position i,j.

To fill dp[i][j][k] we need only summation of (dp[i-1][j][l]+dp[i][j-1][l]) where l varies from 0 to 3 and l is not equal to k.

In simple words to fill i,j with color k number of ways would be we can fill i-1,j with color other than k and i,j-1 with color other than k.

In the end my answer would be summation of dp[n][k] where 0<=k && k<=3;

Why is this approach wrong as I am getting wrong answer for n=2 test case?

Any help is appreciated.  Comments (10)
 » 10 months ago, # | ← Rev. 3 →   There is at most $4^3$ configurations for a column, so you can model the problem as a $dp[i][j][k][l]$, that means the number of configurations ending at column $i$ with colors $j$ $k$ $l$ for this column.$dp[i][j][k][l] = 0;$ if $j = k$ or $k = l$.$dp[i][j][k][l]$ = $SUM(dp[i - 1][t][f][g])$ where $t \neq f$ and $f \neq g$ and $t \neq j$ and $k \neq f$ and $l \neq g$.This is $O(N*4^6)$, dont use $mod$(%) operator, just substract the number if he becomes greater than $10^9 + 7$, i think this is enough to fit in the time.EDIT: The answer is $SUM(dp[n][i][j][k])$.
•  » » I believe your approach is wrong as ABA in a column is still a vaild coloring.
•  » » » yeah, i was wrong, i did some changes.
•  » » » » Your approach seems good but can you tell what is the flaw in my approach
•  » » » » » I dont know if i will can explain, but you are not counting all combinations, because if you sum $dp[i][j - 1][l]$ + $dp[i - 1][j][l]$, is all combinations for fixed values for column $j$ in positions 1..i-1 plus all combinations for fixed values for line $i$ in positions 1..j-1.
•  » » » » » » your approach will not fit in time limit as n can be 1e5
•  » » » » » » » I think if you do a interative dp and dont use mod operador, it fit in time cause are 409600000 operations in the worst case, i think it is less than 1s
•  » » » » » » » » Thanks for the reply. I implemented what you suggested but it is giving wrong answer for n=2 case.code
•  » » » » » » » » » The lines 18-20 isnt right, check my ac solution. codeint dp; int Solution::solve(int A) { const int mod = int(1e9) + 7; const int D = 4; memset(dp, 0, sizeof dp); for(int j = 0 ; j < D ; j++){ for(int k = 0 ; k < D ; k++){ if(k == j){ continue; } for(int l = 0 ; l < D ; l++){ if(l == k){ continue; } dp[j][k][l] = 1; } } } for(int i = 1 ; i < A ; i++){ for(int k = 0 ; k < D ; k++){ for(int l = 0 ; l < D ; l++){ if(l == k) continue; for(int d = 0 ; d < D ; d++){ if(l == d) continue; for(int e = 0 ; e < D ; e++){ if(e == k) continue; for(int f = 0 ; f < D ; f++){ if(f == e || f == l) continue; for(int g = 0 ; g < D ; g++){ if(g == f || g == d) continue; dp[i][k][l][d] += dp[i - 1][e][f][g]; if(dp[i][k][l][d] >= mod){ dp[i][k][l][d] -= mod; } } } } } } } } int sum = 0; for(int j = 0 ; j < D ; j++){ for(int k = 0 ; k < D ; k++){ if(k == j){ continue; } for(int l = 0 ; l < D ; l++){ if(l == k){ continue; } sum += dp[A - 1][j][k][l]; if(sum >= mod){ sum -= mod; } } } } return sum; } 
•  » » Thanks a lot for sharing your solution ! I've been looking for the solution to this problem for quite a few months now !