CODEWITHSUNDEEP
calgorithmdynamic-programming
Utkarsh Srivastav
Utkarsh Srivastav

Reputation: 3227

Dynamic Programming Tiles

http://www.spoj.pl/problems/GNY07H/ In this question we have to find number of ways to arrange 2X1 tiles in 4Xw (w >=1) rectangle ? I have tried this question and has given much time to it but was not able to come up with any solution . how to approach for these kinds of problem. meaning how to make dp recurrence for them. ?

Upvotes: 3

Views: 6026

Answers (4)

ravi ranjan
ravi ranjan

Reputation: 6119

Just se the pattern if by removing any 2*1 block a pattern(gemoetry ) arises such that it is againthe intermediate result, then it gives the recursive function. From that just create DP from it.

For your problem just see the link. It will explain everything

https://math.stackexchange.com/questions/664113/count-the-ways-to-fill-a-4-times-n-board-with-dominoes

For further refernecr juist see the link of IOI training

http://www.iarcs.org.in/inoi/online-study-material/topics/dp-tiling.php

Upvotes: 0

Karoly Horvath
Karoly Horvath

Reputation: 96258

You can build the 4xW rectangle row-by-row. When you build the next row the previous row can be in 6 different states:

XXXX (1 - filled)
XX-- (2)
-XX- (3)
--XX (4)
X--X (5)
---- (6 - empty)

For example if the previous row is (5), you have to put two vertical dominos, and then the next row is going to be (3):

XXXX
XABX
-AB-

Let X(W,q) denote the possible combinations of a 4xW rectangle where the last row is in state q and the rest is completely filled.

If you know X(W-1,q) for all the 6 q states you can easily calculate X(W,q).

You know the initial states X(1,q) (q=1..6 -> 1, 1, 1, 1, 1, invalid). So you can increase W and get these numbers for each W.

The final result is X(W,1) (last row filled).

Upvotes: 10

Abhijeet Kashnia
Abhijeet Kashnia

Reputation: 12890

I too am a beginner at this variation of Dynamic programming, but this link mentions http://apps.topcoder.com/forums/;jsessionid=A5053396424C9F9BBB9337ECAC9C6C17?module=Thread&threadID=770579&start=0&mc=2#1643035 that you need to apply "Dynamic programming with profiles", and that link also points to a tutorial http://apps.topcoder.com/forums/?module=Thread&threadID=697369&start=0&mc=19 specifically, "layer count+ layer profile".

From the above link: "This is the toughest type of DP state domain. It is usually used in tiling or covering problems on special graphs. The classic examples are: calculate number of ways to tile the rectangular board with dominoes (certain cells cannot be used); or put as many chess figures on the chessboard as you can so that they do not hit each other (again, some cells may be restricted)."

Other more approachable tutorials on this technique are available at:

http://sk765.blogspot.in/2012/02/dynamic-programming-with-profile.html

http://sk765.blogspot.in/2012/02/dynamic-programming-with-profile_13.html

http://sk765.blogspot.in/2012/02/dynamic-programming-with-profile_7469.html

http://sk765.blogspot.in/2012/02/dynamic-programming-with-profile_6894.html

I'm working my way through them as well.

This isn't an answer to the particular question you asked, but more of a general technique that people follow when solving this class of problems.

Upvotes: 8

Attila
Attila

Reputation: 28762

I would try a backtracking algorithm: lay all tiles horizontally first, then backtrack until you can lay a vertical tile (then forward with horizontal layering) -- eventually you will enumerate all possible solutions and each only once (a square in the last backtraking phase will either contain a horizontal or a vertical tile, which will give unique solutions, when exists).

I do not know, however if this is an optimal algorithm for solving the problem.

Upvotes: 0

Related Questions