prathams's blog

How to solve this kind of problems
By prathams, history, 9 years ago, In English

In how many ways can you tile a 2 * n rectangle with triominoes? A triomino is a geometric shape made from three squares joined along complete edges. There are only two possible triominoes:

For example, you can tile a 2 * 3 rectangle only in 3 different ways. As the answer can be quite big, you just need to find the number of ways modulo 106.

Constraints : Number of test cases t (1≤t≤100). Each of the following t lines contains the value of n(0 < n < 109).

Output : Answer modulo 106.

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

Comments Comments (11)
| Write comment?
»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Matrix exponentiation.

Let's consider all the states we can reach from a state x where x can equal (00, 01, 10) first bit stands for the up cell and the second bit for the bottom cell.

Now for example for state 00 and column i

F(i, 00) -  > F(i + 1, 01)||F(i + 1, 10)||F(i + 3, 00)

Now we can make a transition matrix and raise it to power n.

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

    Not getting the idea what exactly this states 00, 01, and 10 means with respect to problem?

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

      It's a bitmask means that in the i-th column the first row was occupied or not (first bit) and the second bit for the second row likewise.

      → Reply
»
9 years ago, # |
  Vote: I like it -22 Vote: I do not like it

3^(n/3) if 3 divides n, 0 otherwise.

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

    I'm assuming you got this from treating each group of 3 columns independently, since each such group can be filled in any of the following ways:

    111
    222

    112
    122

    122
    112

    However, this misses tilings such as this one:
    122233
    114443

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

First you need to get a recurrence relation for the answer. There are several ways, like the one described by RetiredAmrMahmoud, here is a bit different approach:

Let the answer be an, and the number of tilings of 2 × n rectangle without a single corner cell is bn. Notice, that on the left side of 2 × n rectangle can be either two horizontal I-triominoes, or one L-triomino with its corner up or down (i.e. L or Г). It gives the following relation: an = an - 3 + 2bn - 1. Similarly, bn = an - 2 + bn - 3. It's enough for getting a solution, but substituting one into another we can get a simpler relation: an = 4an - 3 - an - 6.

Now, the usual way is to use matrix exponentiation, but this problem can be solved even if you don't know about it. The recurrence above modulo 106 has a small period (I think less than 107), so you just need to precalculate answers in that period.

AFAIR the problem was used in the ACM ICPC Quarterfinal in Ukraine in 2009, and several teams used the latter approach.

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

    Can you explain a bit how come this recurrence formed bn  =  an  -  2  +  bn  -  3 I think, it should be bn  =  an  -  2  +  bn  -  1. I got this difference while generating recurrence by myself.

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

      On the side of 2 × n rectangle without a corner cell there is either L-triomino (an - 2), or two I-triominoes (bn - 3).

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

        Looking at the first recurrence an = an - 3 + 2bn - 1, Say n = 3, we have

        a3 = a0 + 2b2

        a3 = 1 + 2 * 0 ..... since a0 = 1&b2 = 0

        a3 = 1

        But there are 3 different ways.

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

          b2 = 1, containing a single L-triomino. Here are a few first values:

          an: 1, 0, 0, 3, 0, 0, 11, 0, 0, 41, 0, 0, 153, 0, 0, 571, 0, 0, 2131, 0, 0
          bn: 0, 0, 1, 0, 0, 4, 0, 0, 15, 0, 0, 56, 0, 0, 209, 0, 0, 780, 0, 0, 2911
          → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice one. I have seen recurrence problems solved this way.

    What can be a generalized approach to solve this kind of problems?

    → Reply