### slow.coder's blog

By slow.coder, history, 4 years ago, ,

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???

• -2

 » 4 years ago, # |   0 Auto comment: topic has been updated by slow.coder (previous revision, new revision, compare).
 » 4 years ago, # | ← Rev. 3 →   0 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. 4 →   0 Ok. But why f(n) = f(n-2) + g(n-1) + g(n-1) is the recurrence??? Suppose, I know nothing about the given recurrence in the soln, then how can I feel the idea of recurrence??? Let it is 4xN(, 5xN, 6xN,....., MxN) then what would be the recurrence relation? How can I develop it step by step?
•  » » » 17 months ago, # ^ |   0
 » 4 years ago, # | ← Rev. 2 →   +1 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, # ^ |   0 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, # ^ |   0 Can you give me this article, please? I solved this problem several years ago but almost forgot solution.
•  » » » » 4 years ago, # ^ |   0 Ok, I can search it in the evening later... Don't promise that really have this article now, I'm not sure.
•  » » 4 years ago, # ^ |   0 time is O((n+m)^3), not O((n*m)^3)
 » 4 years ago, # |   0 As for your question, you can find some clues in this tutorial.
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 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, # ^ |   0 Thanks for your link, It's very helpful and fun also =))
 » 4 years ago, # |   0 I found this useful when I was first learning how to solve these types of problems.
•  » » 4 years ago, # ^ | ← Rev. 13 →   0 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?)"