10644 - Floor Tiles

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

Moderator: Board moderators

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

Post by little joey » Fri May 14, 2004 9:04 am

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.

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

doubt

Post by abishek » Fri May 14, 2004 11:35 am

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:

Post by technobug » Thu May 20, 2004 6:51 pm

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

Post by shuniu » Fri Jun 04, 2004 11:08 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

Post by CC » Sun Aug 22, 2004 3:29 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

Post by bugzpodder » Sun Aug 22, 2004 3:54 am

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 :lol:

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

Re: 10644 - Floor Tiles

Post by coze » Wed Nov 19, 2008 5:45 pm

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

Post by jurajz » Mon Nov 24, 2008 7:37 pm

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

Post by coze » Tue Nov 25, 2008 7:10 pm

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
Thanks in advance.

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

Re: 10644 - Floor Tiles

Post by jurajz » Fri Dec 05, 2008 1:11 am

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

Post by coze » Sat Dec 06, 2008 7:09 pm

Thank you, jurajz.

Post Reply

Return to “Volume 106 (10600-10699)”