slow.coder's blog

Tiling With Dominoes(DP solution)
By slow.coder, history, 9 years ago, In English

UVa 10918 — Tri Tiling.

In short, You are given the value of N, now determine in how many ways you can completely tiled a 3xN rectangle with 2x1 dominoes. Here is a possible soln: Algorithmist — UVa 10918. My question is, how is the recurrence defined? Here,

********   AA*******   AA******   A*******
******** = BB******* + B******* + A*******
********   CC*******   B*******   BB******
  f(n)   =  f(n-2)   +  g(n-1)  +  g(n-1)

Isn't it possible as:

********   AA*******   AA******   AA******
******** = BB******* + BA****** + AA******
********   CC*******   BA******   BB******
  f(n)   =  f(n-2)   +  f(n-2)  +  f(n-2)

or like others....(actually I want to know it). How can I define such type of recurrence?

Actually I want to know, what type of thinking should I keep in mind while defining recurrence for Tiling Block problem???

Thanks in advanced. :)

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

Comments Comments (8)
| Write comment?
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

You don't have to do it in O(N) time...

You can continue to put dominoes and do it in O(N^2)... (I wish I'm not wrong)

For example:

A***          AC**
A***  ---->   AC**   f(n-2)
BB**          BB**

 |
 |
 v

ACC*          ACCF
ADD*  ---->   ADDF  f(n-4)
BBEE          BBEE

 |
 |
 v

ACCFF*
ADDGG*
BBEEHH

And...

NOTE : I want to sleep now and don't have time but I think maybe you can do this in O(N) too...by saving sum of all f(2i) and f(2i+1) in two integers

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Searching for good tutorials about dynamic programming approach for this problem, I have accidentally found this presentation. The guys claim they can find the number of domino tilings of the m × n rectangle in polynomial time (it seems like O((nm)3) algorithm). I haven't had time to understand the full presentation yet, but this fact was quite unexpected to me. Have you guys heard about it before? :)

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

    Yes, for example, see acm.timus.ru problem "Aztec treasure" ("Сокровища ацтеков"), here is such problem for 100x100 grid =))

    This interesting method firstly was presented to ACM in Petrozavodsk winter camp 2009. Team of Yekaterinburg try to tell us solution, which was described in some big article (40-50 pages in size).

    If you want, I can see for some hint or link for you.

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

    time is O((n+m)^3), not O((n*m)^3)

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

As for your question, you can find some clues in this tutorial.

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

    Thanks for your link, It's very helpful and fun also =))

    → Reply