Page 1 of 1
10359 - Tiling
Posted: Wed Mar 26, 2003 1:58 am
by ditrix
Can anyone tell me why the right answer for input "0" is "1" and not "0"?
Does it mean, that exists exactly one way to tile nothing by anything?
And if the answer is positf, what is this way?
Posted: Wed Mar 26, 2003 6:11 am
by kmhasan
The answer for 0 is 1. There is exactly one way to tile a 2x0 board -- that is to tile it with 0 tiles. The reasoning is analogous to choosing 0 items from n items. I hope you'd agree that it's valid.
10359
Posted: Wed May 18, 2005 7:37 am
by bsd_lover
I am compeletly stumped. Can't figure out the recurrence relation. Any hints anyone ?
Posted: Wed May 18, 2005 10:25 am
by mf
Here's the solution:
f(0) = 1
f(1) = 1
f(n) = f(n - 1) + 2 * f(n - 2)
The recurrence follows from the fact that in general 2xn rectangle there are just three possible tiling schemes:
1. Use a vertical 2x1 piece, and recursively tile the remaining 2x(n-1) rectangle.
2. Use a 2x2 piece and tile 2x(n-2) rectangle.
3. Use two horizontal 1x2 pieces and tile 2x(n-2) rectangle.
Graphically they look like (`#' and `*' stand for pieces, dots - the remaining part of the rectangle):
Code: Select all
#.... ##... ##...
#.... ##... **...
1 2 3
Posted: Wed May 18, 2005 2:22 pm
by bsd_lover
Thanks mf , I actually figured it out before that after I googled for it
Its a nice problem. But quite easy once the relation is found. Mind you , you also need a BigInt library handy.
10359 - Tiling - CE
Posted: Tue Jan 24, 2006 2:09 pm
by Ashganek
Could anyone take a look and tell me why I got CE? (it works on my computer)
// cut...
Re: 10359 - Tiling - CE
Posted: Tue Jan 24, 2006 6:30 pm
by Solaris
I have found at least two lines where u can get CE
Code: Select all
1. c->len = max(a->len, b->len)+1; //'max' : undeclared identifier
2. if( n == 1 or n == 0 ) { return int_to_bint(1); } //'or' : undeclared identifier
And by the way, I dont know about any C/C++ compiler where u can pass the latter case. Which compiler did u use ?
Posted: Tue Jan 24, 2006 7:04 pm
by Ashganek
dev-cpp.
since when or is undeclered ?
which header i have to include to get max in gcc then?
Posted: Tue Jan 24, 2006 7:25 pm
by Ashganek
Ok, I defined my own max and switched to cstdio and I got it
Posted: Tue Jun 27, 2006 6:52 pm
by sunny
i cant understand why the relation isnt this:
f(n)=f(n-1)+f(2)*f(n-2)
or, f(n)=f(n-1)+3*f(n-2)
isn't there another way to use two vertical 1x2 pieces
& tile 2*(n-2) rectangle.
Posted: Tue Jun 27, 2006 9:42 pm
by mf
In the derivation I've posted above, the case with two vertical pieces is included in the case #1.
Draw all the tiling of 2x3 rectangle by hand. It will help you understand the problem better.
Posted: Thu Oct 04, 2007 2:30 pm
by rossi kamal
mf
i got ac with DP..
With recursion i m stuck at bigger inputs
I have used the big integer libraray...
May you tell some more recurrence of 2*1
2*2 0r 2*3 dominoes in 2*n or 3*n 0r n*n
rectangle
wish to learn about them...
Thanks in advance
Rossi
Re: 10359 - Tiling
Posted: Mon Oct 26, 2009 2:11 pm
by Angeh
Another Easy recursion is
for f(n=even) 2*f(n-1)+1
for f(n=odd) 2*f(n-1)-1
convince yourself ........