TopCoder problem "ThirtyRocks" used in TCHS SRM 64 (Division I Level Two)

Problem Statement


You have 30 rocks and n boxes in which you wish to place them. Each box can hold some minimum and maximum number of rocks. The i-th element of boxMinimum is the minimum number of rocks you can place in box i, and the i-th element of boxMaximum is the maximum number of rocks you can place in box i.

If you can put all 30 rocks into the boxes, return a int[] containing exactly n elements, where the i-th element is the number of rocks in box i. If there are multiple ways to do this, return the one that comes first lexicographically. If it is not possible to put all 30 rocks into boxes, return an empty int[] instead.



Parameters:int[], int[]
Method signature:int[] assign(int[] boxMinimum, int[] boxMaximum)
(be sure your method is public)


-int[] A comes before int[] B lexicographically if A contains the lesser number in the first position in which A and B differ.


-boxMinimum will contain between 1 and 50 elements, inclusive.
-boxMaximum will contain the same number of elements as boxMinimum.
-Each element of boxMinimum will be between 0 and 30, inclusive.
-Each element i of boxMaximum will be between boxMinimum[i] and 30, inclusive.


Returns: {20, 10 }
The only possible way to distribute the 30 rocks is by placing 20 rocks in the first box and the remaining 10 in the second box. If we moved any of the rocks to another box we would be breaking the specified limits.
Returns: { }
This time, there are three boxes but each of them requires a minimum of 15 rocks, which is impossible to achieve since we only have 30.
Returns: {19, 11 }
This is similar to the first example. However, we are now allowed to place 11 rocks in the second box. This allows two possible answers: {20,10} and {19,11} . We pick the second one since it comes first lexicographically.
Returns: { }
The first box requires 10 rocks, but you cannot place the remaining rocks in the other boxes since they allow a maximum of 17 rocks. It is not possible to comply with all the rules.
Returns: {0, 0, 0, 0, 30 }
Of all the many possible solutions for this case, {0,0,0,0,30} comes first lexicographically.

Problem url:

Problem stats url:




PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Greedy, Math, Simple Search, Iteration