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.
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.
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 (mk)xn+kxn rectangle for some k
or it is a mx(nk)+mxk rectangle for some k.
and i got AC
I would like to know the mathematics behind this?
abi
i.e if it is a mxn rectangle, then it is a (mk)xn+kxn rectangle for some k
or it is a mx(nk)+mxk rectangle for some k.
and i got AC
I would like to know the mathematics behind this?
abi
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(l11,w2)f(l2,w11)+f(l11,w11)
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
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(l11,w2)f(l2,w11)+f(l11,w11)
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
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.
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.
you need not try to find out all possiblitystechnobug 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?
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
...

 Experienced poster
 Posts: 147
 Joined: Fri Jun 13, 2003 10:46 pm
Re: 10644  Floor Tiles
Umm...ranjit wrote:My ac code gives the op :Code: Select all
5348 5348 0 553448
Input:
Code: Select all
4
1 100 1 100
100 1 100 1
100 100 100 100
1 1000 1 1000
Code: Select all
5348
5348
0
553841
Re: 10644  Floor Tiles
My AC code gives:
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.
Code: Select all
5348
5348
0
553448
Re: 10644  Floor Tiles
Thank you, jurajz.
What's the output for the input:
My output:
Thanks in advance.
What's the output for the input:
Code: Select all
2
2 900 2 900
2 999 2 999
Code: Select all
448503
552782
Re: 10644  Floor Tiles
My AC code gives the same output
Re: 10644  Floor Tiles
Thank you, jurajz.