wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Largest volume of pieces of cube
        
(Message started by: birbal on Feb 25^th, 2011, 9:43am)

Title: Largest volume of pieces of cube
Post by birbal on Feb 25^th, 2011, 9:43am

Given n cubes with different volumes, we have to cut exactly m pieces out of them such that all of them have same volume v. How to find the maximum value of v ? wastage is acceptable.

Title: Re: Largest volume of pieces of cube
Post by towr on Feb 25^th, 2011, 2:55pm

Are the sides of the cube integers? Or doesn't it really matter they're cubes at all?

Title: Re: Largest volume of pieces of cube
Post by birbal on Feb 28^th, 2011, 11:07am

@Towr,

yes you got it right. It doesn't really matter that they are cubes. We need to use their volumes only. You can assume that volumes are integers( and so are the sides of the cubes).

Title: Re: Largest volume of pieces of cube
Post by towr on Feb 28^th, 2011, 11:43am

At least one of the cubes will be divided in a number of equal pieces.
That gives a simple O(m*n²) approach. It should be possible to vastly improve on that :P

You could do a binary search on v. Pick some v, see how many times (x) it fits into each cube, noting the wastage divided by x. Take the minimum wastage/x and increase v to use up that cube entirely. Then if you have more than m pieces, try a bigger v in binary search fashion; or if you have less than m, try a smaller v. Pick the largest v so that you have at least m pieces (you may have more with the maximum v).
For the initial minimum v you could take the largest block divided by m, and for maximum v the sum of all cubes divided by m.

Should do rather decently I think.

Title: Re: Largest volume of pieces of cube
Post by birbal on Feb 28^th, 2011, 7:41pm

@towr

Your solution is a good solution i must say. Practically it will work reasonably fast even on large volumes.

Is there any other exact solution other than search. This problem seems a little similar to the problem of finding area under histogram which has some standard techinques. What about this one? any idea?