deep_tricks's blog

By deep_tricks, history, 9 days ago, In English

There is a 3*n grid which is to be filled with 3 different colors.How many ways can we do it if no column or row have all the cells of same color. N<=20000 and mod 1e9+7

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe, you can calculate number of all ways to place three colors, and then calculate number of ways if you fix one row to be one color and then color other two and subtract from answer. You can to all this with dp.

»
9 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Lets assume we have the answer for 3*(n-1) grid. Now its obvious that for 3*n grid we just have to take care for the nth column to be legal.

And the number of ways a column can be legal is 24 ( 3 cells in a column, number of ways to fill is 27 and number of illegal ways would be 3 i.e RRR, GGG, BBB ).

Lets assume we call answer for 3*(n-1) to be dp[n-1] then we can write it as:
dp[n] = dp[n-1]*24 + something
This plus something is because some of the illegal ways for coloring 3*(n-1) can also be made legal.
Now its obvious that these illegal ways for (n-1) would be only illegal in terms of rows and not columns.
Lets see how many illegal ways of rows exists!
Either one of the rows can be illegal or 2 rows can be illegal. Note that all 3 rows cannot be simultaneously be illegal.
And hence number of one row illegal = 3C1*3
Similarly for 2 rows = 3C2*3
And considering the coloring options for these 2 conditions, we get:

dp[n] = dp[n-1]*24 + Σ 3Ci*3*2i for all i ∈ {1,2}


P.S — I'm obviously unsure of the solution and would like to test it. So please provide a link to the problem.

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I no more have access to the problem as it was asked in a coding round by a company and is no more public.

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ohh alright!
      But this solution looks promising!

      • »
        »
        »
        »
        9 days ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

        No. Your solution is not right.

        Calculate the answer for $$$n = 2$$$

        • »
          »
          »
          »
          »
          9 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thats a diplomatic answerXD.
          Please provide a reason.

          • »
            »
            »
            »
            »
            »
            9 days ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            Find the answer for $$$n = 2$$$. Moreover, the addition part in dp is wrong.

            • »
              »
              »
              »
              »
              »
              »
              9 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yes you are right, the plus something part is definetely wrong. I will try to rectify it!

              • »
                »
                »
                »
                »
                »
                »
                »
                8 days ago, # ^ |
                Rev. 3   Vote: I like it +8 Vote: I do not like it

                Edit: Wtf! This is not even right. Why is this upvoted?

                $$$C1_i = C1_{i - 1} \cdot 8$$$
                $$$C2_i = C2_{i - 1} \cdot 7$$$
                $$$dp_i = dp_{i - 1} \cdot 24 + C1_i + C2_i$$$

                dpi — number of ways to color 3 x i grid with three colors such that no row and column have the same color.

                C1i — number of ways to color 3 x i grid with three colors such that one of the rows has the same color in 3 x i — 1 grid.

                C2i — number of ways to color 3 x i grid with three colors such that two of the rows have the same color in 3 x i — 1 grid.

                Base case:
                $$$C1_1 = 3!, C2_1 = 24 - 3! = 18, dp_1 = 0$$$.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Could you explain why multiply by 8 and 7?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Ah, it's wrong. C1, C2 are not right $$$n > 2$$$. They are too difficult to calculate.

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    dp[n]=dp[n-1]*(24)+(3C2)*3*2*(v1) +(24-(3C2)*3*2)*(v2).

    ((3C2)*3*2) invalid ways till (n-1) when two rows have same color.

    ((24-(3C2)*3*2)) invalid ways till (n-1) when no rows have same color.

    v1 and v2 is the ways to fill nth col for those conditions. But not clear how to find v1 and v2.

»
8 days ago, # |
Rev. 3   Vote: I like it -7 Vote: I do not like it

$$$EDIT: $$$ Its wrong the ideia, sorry.

As i_love_cuiaoxiang mentioned, there is 24 choices of column to respect the column restriction.

Lets do a dp of coloring choices that respect the column restriction and not respect the row restriction.

The $$$dp[i][j]$$$ have the number of choices that don't respect the row restriction if we just consider the first $$$i$$$ columns and put $$$j$$$ in the $$$i$$$ column ($$$j$$$ can be the options that we can put in the column (24), can be "RRG", "BBR" or any other combination except "RRR", "GGG" and "BBB").

How the transition works? $$$dp[i][j] = \sum\limits_{k} dp[i-1][k]$$$ if $$$k$$$ have a common value with j in any position("RGB" have a common value with "RRB" but don't have with "GBR", note that position matters).

The answer for the problem will be $$$24^{n} - \sum\limits_{i} dp[n][k]$$$. The complexity will be $$$O(n*24^2)$$$.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh yes!
    This makes sense.
    answer would be equal to the number of coloring that are legal for columns minus the number of coloring that are illegal for rows and legal for columns!
    I also understand the incorrectness of dp[n] = dp[n-1]*24, it being that lets suppose one of the legal ways of coloring for n = 1 would be RRB but then in the very next column we are taking all 24 choices i.e we also take RRB or RGB and many more which are illegal!

  • »
    »
    8 days ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    why so?
    EDIT: Ohh ok! You dont take into consideration that it was already legal but you were still trying to make it legal by placing only the ones which dont intersect with it

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Lets se the sequence: "RRG", "BRB", "BGG", my dp will add this case to dp[3]["BGG"], because "RRG" match "BRB" and "BRB" match "BGG", and is a case that don't disrespect any restriction.

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        And also for :
        RGR
        RBG
        BRR
        Now for dp[4] you wont count all states that are valid
        Basically current state depends on more than one previous state.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I think my solution would work if we already precompute answers for n=1 and n=2!

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't think so, It's impossible for the answer be greater or equal than $$$24^{n}$$$(the maximum possible answer if we don't consider the row restriction), but your solution will give a answer greater or equal $$$24^{n}$$$, so you will get WA.

»
8 days ago, # |
  Vote: I like it +13 Vote: I do not like it
$$$ 24^n - 9 \cdot 8^n + 18 \cdot 3^n + 9 \cdot 2^n - 24 $$$
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I suggest this solution:

Let:

  • $$$sum =$$$ number of ways to create a table that no column have all the cells of same color.
  • $$$sum1 =$$$ number of ways to create a table that no column have all the cells of same color and have one or more rows have all the cells of same color.

-> $$$answer = sum - sum1$$$

$$$sum$$$ & $$$sum1$$$ can be calculated by dp bitmask with Inclusion — Exclusion.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$sum$$$ is always $$$24^n$$$. can you elaborate on calculating $$$sum1$$$?

    • »
      »
      »
      8 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Let $$$f[0/1][0/1][0/1] =$$$ number of ways to create table that row 1, 2, 3 is same or not.

      $$$sum1 = f[1][0][0] + f[0][1][0] + f[0][0][1] - f[1][1][0] - f[1][0][1] - f[0][1][1] + f[1][1][1]. (Inclusion - Exclusion)$$$

      To calculate $$$f$$$, we can use $$$dp[i][mask] =$$$ number of ways to create table 3 * i with the $$$i-th$$$ $$$column's$$$ $$$state = mask$$$ and no column have all the cells of same color.

      Let $$$k =$$$ number of qualified states between 2 adjacent columns for each state of $$$f$$$. In the worst case, $$$k = 9^2$$$.

      The complexity could be $$$O(2^3 * 9^2 * n)$$$

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't see how this is valid.

        Can you validate your approach with these?

        Testcases
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

https://google.com Always works :)