slow.coder's blog

By slow.coder, history, 4 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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by slow.coder (previous revision, new revision, compare).

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

»
4 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? :)

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

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

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

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

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

    @Kostroma

    Truth to tell I have already found the tutorials which you have referred.... Please give your idea if any to understand the psychology of the recurrence of Tiling Block problem soln.... :)

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

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I found this useful when I was first learning how to solve these types of problems.

  • »
    »
    4 years ago, # ^ |
    Rev. 13   Vote: I like it 0 Vote: I do not like it

    @Governer

    WoW!!! This is an awesome tutorial. Thanks!!!

    But, In the first answer I have some confusions:(picture is taken for clearance)

    A "type F" 4 × n tiling is always configuration F extended by a "type B" or "type F" 4×(n−2)  tiling that has its center left domino removed. So f F(n) is exactly the number of 4×(n−2) "type B" or "type F" tilings, that is, fF(n)=f{B,F}(n−2). (The type B and F tilings are exactly the ones that have a center left domino to remove.)
    

    >>> Here F extended by itself!!! Ok, fine!!!

    Now it says,

    A "type G" tiling is G extended by a tiling of type A, D, or H, with the upper left domino removed. So fG(n) =f {A, D, H} (n−2). (A, D, and H are the tiling with an upper left domino.)
    

    >>> How G could be extended by A (If so then, why not E?), D (Isn't it C?) and H (Isn't it G itself)?

    A "type H" tiling is H extended by a tiling of type A, C, or G, with the lower left domino removed, so fH(n)=f{A,C,G}(n−2). (A, C, and G are the tiling types with a lower left domino.)
    

    >>> How H could be extended by A (If so then, why not E?), C (Isn't it D?) and G (Isn't it H itself)?

    Ok !!! after changing the following things the main result would be same. But the main confusion is here, ".....could be extended by A (If so then, why not E?)"