10359 - Tiling

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris

10359 - Tiling

Post by ditrix » Wed Mar 26, 2003 1:58 am

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?
@+!
DitriX

User avatar
kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan » Wed Mar 26, 2003 6:11 am

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.

bsd_lover
New poster
Posts: 4
Joined: Sun Oct 14, 2001 2:00 am

10359

Post by bsd_lover » Wed May 18, 2005 7:37 am

I am compeletly stumped. Can't figure out the recurrence relation. Any hints anyone ?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Wed May 18, 2005 10:25 am

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

bsd_lover
New poster
Posts: 4
Joined: Sun Oct 14, 2001 2:00 am

Post by bsd_lover » Wed May 18, 2005 2:22 pm

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.

Ashganek
New poster
Posts: 8
Joined: Thu Jan 19, 2006 10:42 pm

10359 - Tiling - CE

Post by Ashganek » Tue Jan 24, 2006 2:09 pm

Could anyone take a look and tell me why I got CE? (it works on my computer)

// cut... :)
Last edited by Ashganek on Tue Jan 24, 2006 7:24 pm, edited 1 time in total.

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Re: 10359 - Tiling - CE

Post by Solaris » Tue Jan 24, 2006 6:30 pm

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 ? :o
Where's the "Any" key?

Ashganek
New poster
Posts: 8
Joined: Thu Jan 19, 2006 10:42 pm

Post by Ashganek » Tue Jan 24, 2006 7:04 pm

dev-cpp.

since when or is undeclered ? :o

which header i have to include to get max in gcc then?

Ashganek
New poster
Posts: 8
Joined: Thu Jan 19, 2006 10:42 pm

Post by Ashganek » Tue Jan 24, 2006 7:25 pm

Ok, I defined my own max and switched to cstdio and I got it :)

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny » Tue Jun 27, 2006 6:52 pm

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.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Jun 27, 2006 9:42 pm

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.

rossi kamal
New poster
Posts: 14
Joined: Mon Sep 03, 2007 10:11 am
Contact:

Post by rossi kamal » Thu Oct 04, 2007 2:30 pm

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

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 10359 - Tiling

Post by Angeh » Mon Oct 26, 2009 2:11 pm

Another Easy recursion is

for f(n=even) 2*f(n-1)+1
for f(n=odd) 2*f(n-1)-1
:D :D :D :D :D :D
convince yourself ........
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Post Reply

Return to “Volume 103 (10300-10399)”