Problem : link

Code : code

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

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[3][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.

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.

codeThanks a lot for sharing your solution ! I've been looking for the solution to this problem for quite a few months now !