Блог пользователя aman_naughty

Color a 3XN grid using atmost 4 colors DP Problem help needed
Автор aman_naughty, история, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится

»
7 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +8 Проголосовать: не нравится

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])$$$.

→ Ответить