366 - Cutting Up

[sadoc]

Please, if someone may give me a tip to solve the problem 366, "Cutting up", it would be very welcome. I don't have any idea in order to solve it.
Thanks in advance,
Daniel

[sadoc]

Hi! I've made a progress. I was able to solve this problem, with the help of Demiurge, using a priority queue that stores the pieces available at a particular time of the simulation ordered by "m" (if "n" > "m" for a particular piece, I exchange "m" and "n"). Using a greedy strategy, of always getting the x first pieces from the queue ("x" = min("k", #of pieces available in the queue)) and cutting them vertically in the middle seems ok. But I've seen that the test cases used in order to verify the correcteness of this problem are too weak. So, please, I would like to get a formal proof of the correcteness of this algorithm. Or, perhaps, a stronger test case.

Thanks in advance,
Daniel Sadoc

On 2001-11-05 01:59, sadoc wrote:
Please, if someone may give me a tip to solve the problem 366, "Cutting up", it would be very welcome. I don't have any idea in order to solve it.
Thanks in advance,
Daniel

<font size=-1>[ This Message was edited by: sadoc on 2001-11-18 03:17 ]</font>

<font size=-1>[ This Message was edited by: sadoc on 2001-11-21 01:55 ]</font>

[jpfarias]

I solved this problem this way:

First, create two lists, to_cut and cutted. Than read the first piece and store it on the list to_cut. Than repeate the following steps:

1 Get the bigger piece from the list to_cut
2 remove it from the list to_cut
3 cut the bigger dimension by 2 and store the resulting two pieces in the list cutted
4 Go back to step 1 while there are pieces in the list to_cut
5 increase the cut count
6 insert all the pieces from the list cutted wich are not of the size 1x1 on the list to_cut
7 clear the list cutted
8 If the list to_cut is not empty go back to step 1
9 print the results!!!!

You can get my answer to this problem on my site:

http://consiste.dimap.ufrn.br/~jpfarias/acm/acmp.php

Jo

[Stefan Pochmann]

Please check that URL, it's not working...

[jpfarias]

http://consiste.dimap.ufrn.br/~jpfarias/acm/acm.php

[Fresh]

It's still not working...

-novice

[Cubist]

I'd have to say I doubt that most of the solutions submitted are actually
correct. There are subtle cases if the number of layers that may be cut
at once is large relative to the area of the fabric. If the area is sufficiently
large relative to k, there's a simple formula that I've proven is correct.

[Cubist]

I've found a simple closed form for the number of cuts required. I believe that
it extends easily to the n-dimensional problem, as well.
--
Chris Long, Mathematics Department, Rutgers University

Mozart needs food. Beethoven now has extra fight power. Bach is about to die.