## Problem 366 "Cutting up" - help!

Moderator: Board moderators

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.
Daniel
New poster

Posts: 3
Joined: Mon Nov 05, 2001 2:00 am

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.

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.
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>
New poster

Posts: 3
Joined: Mon Nov 05, 2001 2:00 am

### My solution

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
jpfarias
Learning poster

Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil

Please check that URL, it's not working...
Stefan Pochmann
A great helper

Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany

### The correct URL

jpfarias
Learning poster

Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil

### URL

It's still not working...

-novice
Fresh
New poster

Posts: 46
Joined: Mon Apr 15, 2002 10:42 am

### On 366

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!

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.
Cubist
New poster

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