aman_naughty's blog

Color a 3XN grid using atmost 4 colors DP Problem help needed
By aman_naughty, history, 5 years ago, In English

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.

  • Vote: I like it
  • -12
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I believe your approach is wrong as ABA in a column is still a vaild coloring.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah, i was wrong, i did some changes.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Your approach seems good but can you tell what is the flaw in my approach

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            your approach will not fit in time limit as n can be 1e5

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Thanks for the reply. I implemented what you suggested but it is giving wrong answer for n=2 case.

                code

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  The lines 18-20 isnt right, check my ac solution.

                  code
                  → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply