## 10644 - Floor Tiles

Moderator: Board moderators

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
tep:

Make a table where the element in the nth row and mth column represents the status of what you know of an n x m rectangle. Use '+' if you're sure a rectangle can be formed, '-' if you're sure it can't be formed and '?' if you don't know yet.
The first row is easy: 1 x m rectangles are impossible, so it consists of all '-'.
The second row is also easy, we know we can form 2x3, 2x6, 2x9, etc. and we also know we can't form 2 x m if m is not divisible by 3. So the second row is: -,-,+,-,-,+,-,-,+, etc. In fact all even rows where n is not divisible by 3 have this pattern.
For the third row we know that a 3 x m can be formed for m is even, but we don't know the status for m is odd yet, so we get: -,+,?,+,?,+,?, etc.

If you continue in this way, you'll start to see patterns. Try to 'reason away' the '?'s. It's quite easy to see that a 3x3 is impossible. Also use the symmetry of the table.

This getting too much of a spoiler already, so if you need more help, send me a PM.

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

### doubt

I assume that any rectangle other than 2x3 and 5x9 to be divisible into smaller rectangles.
i.e if it is a mxn rectangle, then it is a (m-k)xn+kxn rectangle for some k
or it is a mx(n-k)+mxk rectangle for some k.
and i got AC
I would like to know the mathematics behind this?
abi

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:
Hmm.... i have draw a 18x20 grid on a sheet of paper and filled with with all possible mappings. Then its easy to see which pattern is in there..

Once discovered, the pattern can be traduced in a simple function which takes L and W and gives back the total number of possibilities for 1x1 up to LxW.

Then the following brings the solution in 0.00.002 secs:

x = f(l2,w2)-f(l1-1,w2)-f(l2,w1-1)+f(l1-1,w1-1)

Although I finally got it AC I still dont know how did anyone find out that a 5x9 rectangle was possible. (please dont tell me you have tried all possibilities . Anyone can help me out here?

I would never solve it during the contest, but I really liked this one...

Thanks...

Guilherme Silveira

shuniu
New poster
Posts: 34
Joined: Thu Oct 16, 2003 6:15 pm
A faster way than drawing it on paper is to write a program to draw it.
First set 2x3, 3x2, 5x9, 9x5 to be the possible tiled rectangles.
Then use dynamic programming to determine the rest (eg a rectangle can be tiled iff it can be cut into 2 tilable rectangles).
Unfortunately, this method takes more than 10s, so it can not be submited as a solution. But you can output the grid to recognize the pattern.
I must say that the pattern is alot simpler than I expected.

CC
New poster
Posts: 8
Joined: Tue Oct 14, 2003 5:02 am
technobug wrote: Although I finally got it AC I still dont know how did anyone find out that a 5x9 rectangle was possible. (please dont tell me you have tried all possibilities . Anyone can help me out here?
you need not try to find out all possiblitys
if you use backtrack algorithm and run it in your brain
it will cost you a short time to find a way to tile a 9*5 rectangle
(may be the way of tiling is many)

All rectangle that can be tiled, it's area is a multiple of 3

if the rectangle's area is a even number and can be divided by 3
then it can be tiled(you can prove this by prove into a 6*x or 3*(even))

and if the rectangle's area is a odd number and can be divided by 3
one edge must be a multiple of 3(and it must be a odd number)

3*x(x is a odd number) can't be tiled

9*x when x!=3 the smallest is 9*5
and if 9*5 can be tiled, 9*x(x>=5 && x%2==1) can be tiled

so you try to prove 9*5 can be tiled

...

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm
shuniu wrote:A faster way than drawing it on paper is to write a program to draw it.
this was the intent of the problem, to write code for something, and then not include it in the final solution

coze
New poster
Posts: 26
Joined: Tue Nov 27, 2007 7:56 am
Location: Japan

### Re: 10644 - Floor Tiles

ranjit wrote:My ac code gives the op :

Code: Select all

``````5348
5348
0
553448
``````
Umm...

Input:

Code: Select all

``````4
1 100 1 100
100 1 100 1
100 100 100 100
1 1000 1 1000``````
My AC output:

Code: Select all

``````5348
5348
0
553841``````
Is this incorrect?

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

### Re: 10644 - Floor Tiles

My AC code gives:

Code: Select all

``````5348
5348
0
553448
``````
It is hard to say, if it is incorrect. Your input for 1 1000 1 1000 is probably incorrect, but from the other side, problem description says, that L1 L2 W1 W2 are positive integers less than 1000. So, input 1 1000 1 1000 can not be in the input file. Because of that you have AC and ranjit have AC too.

coze
New poster
Posts: 26
Joined: Tue Nov 27, 2007 7:56 am
Location: Japan

### Re: 10644 - Floor Tiles

Thank you, jurajz.

What's the output for the input:

Code: Select all

``````2
2 900 2 900
2 999 2 999``````
My output:

Code: Select all

``````448503
552782``````

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

### Re: 10644 - Floor Tiles

My AC code gives the same output

coze
New poster
Posts: 26
Joined: Tue Nov 27, 2007 7:56 am
Location: Japan

### Re: 10644 - Floor Tiles

Thank you, jurajz.