10644 - Floor Tiles

[little joey]

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]

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]

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]

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]

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]

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]

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]

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]

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]

My AC code gives the same output

[coze]

Thank you, jurajz.