366 - Cutting Up

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

Moderator: Board moderators

Post Reply
sadoc
New poster
Posts: 3
Joined: Mon Nov 05, 2001 2:00 am

366 - Cutting Up

Post by 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
New poster
Posts: 3
Joined: Mon Nov 05, 2001 2:00 am

Post by 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
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

My solution

Post by 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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann »

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

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

The correct URL

Post by jpfarias »


Fresh
New poster
Posts: 46
Joined: Mon Apr 15, 2002 10:42 am
Contact:

URL

Post by Fresh »

It's still not working...

-novice :(

Cubist
New poster
Posts: 17
Joined: Sun May 26, 2002 7:56 am
Location: San Diego, CA

On 366

Post by 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
New poster
Posts: 17
Joined: Sun May 26, 2002 7:56 am
Location: San Diego, CA

Closed Form!

Post by 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.

Post Reply

Return to “Volume 3 (300-399)”