Author |
Topic: Largest volume of pieces of cube (Read 621 times) |
|
birbal
Full Member
Gender: 
Posts: 250
|
 |
Largest volume of pieces of cube
« on: Feb 25th, 2011, 9:43am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Largest volume of pieces of cube
« Reply #1 on: Feb 25th, 2011, 2:55pm » |
Quote Modify
|
Are the sides of the cube integers? Or doesn't it really matter they're cubes at all?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Largest volume of pieces of cube
« Reply #2 on: Feb 28th, 2011, 11:07am » |
Quote Modify
|
@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).
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Largest volume of pieces of cube
« Reply #3 on: Feb 28th, 2011, 11:43am » |
Quote Modify
|
At least one of the cubes will be divided in a number of equal pieces.
That gives a simple O(m*n2) approach. It should be possible to vastly improve on that 
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Largest volume of pieces of cube
« Reply #4 on: Feb 28th, 2011, 7:41pm » |
Quote Modify
|
@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?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print