aman_naughty's blog

By aman_naughty, history, 4 weeks 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

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

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah, i was wrong, i did some changes.

      • »
        »
        »
        »
        4 weeks 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

        • »
          »
          »
          »
          »
          4 weeks 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.

          • »
            »
            »
            »
            »
            »
            4 weeks 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

            • »
              »
              »
              »
              »
              »
              »
              4 weeks 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

              • »
                »
                »
                »
                »
                »
                »
                »
                4 weeks 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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

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

                  code