TopCoder problem "StackingBoxes" used in SRM 261 (Division I Level Three)



Problem Statement

    

Yesterday I was cleaning my house and I made a startling discovery. In the corner of the living room stood a nice decorated Christmas tree. The next Christmas is still too far away, thus I decided to remove all the decorations, put them into cardboard boxes and store them in the garage. However, the garage is almost full of other stuff. Therefore I'd like to arrange the boxes to form a tall stack, one atop another.

This may not be possible. Christmas tree decorations are fragile and the boxes that contain them aren't exactly made of steel. I weighed each of the boxes and for each of them I estimated the maximum weight that can be placed on the top of the box without it collapsing. In the following text we will use the term carrying capacity of a box when referring to this maximum weight.

You will be given this information in two String[]s: weight and canCarry. Each element of weight will contain the weights of some of the boxes. Similarly, each element of canCarry will contain the carrying capacities of some of the boxes. The carrying capacities of the boxes will be given in the same order as their weights.

Your task is to find and return the largest N such that N of the boxes can be selected and placed one atop another in some order such that none of the boxes collapse.

 

Definition

    
Class:StackingBoxes
Method:highestStack
Parameters:String[], String[]
Returns:int
Method signature:int highestStack(String[] weight, String[] canCarry)
(be sure your method is public)
    
 

Constraints

-weight contains between 1 and 50 elements, inclusive.
-canCarry contains between 1 and 50 elements, inclusive.
-Each element of weight and canCarry contains between 1 and 50 characters, inclusive.
-Each element of weight is of the form "NUMBER NUMBER ... NUMBER".
-Each element of canCarry is of the form "NUMBER NUMBER ... NUMBER".
-Each NUMBER in weight is an integer between 1 and 100,000, inclusive
-Each NUMBER in canCarry is an integer between 1 and 1,000,000,000, inclusive.
-All NUMBERs in weight and canCarry will contain no leading zeroes.
-weight and canCarry contain the same total count of NUMBERs.
 

Examples

0)
    
{"10 20 30"}
{"11", "100 10"}
Returns: 3
Here we are given 3 boxes. The first one has weight 10 and can carry 11, the second one has weight 20 and can carry 100, the third one has weight 30 and can carry 10. It is possible to create a stack using all three of them: the first box goes on the top, the third one below and the second one on the bottom.
1)
    
{"11 20 30"}
{"11", "100 10"}
Returns: 2
The first box is now too heavy, so the previous arrangement doesn't work anymore.
2)
    
{"10", "20", "91"}
{"11", "100 10"}
Returns: 2
Again, the original arrangement doesn't work anymore. This time boxes 1 and 3 together are too heavy -- box 2 won't be able to carry both of them.
3)
    
{"100000"}
{"1000000000"}
Returns: 1
You can always use at least one box, as it doesn't have to carry anything.
4)
    
{"100 100", "1000 100"}
{"90", "91 92 93"}
Returns: 1
Each of the boxes is too heavy to be placed on any other box.
5)
    
{"200 200 600 700 400"}
{"1000 20 150 700 10"}
Returns: 3

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4660

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7995&pm=4660

Writer:

misof

Testers:

PabloGilberto , lbackstrom , brett1479 , Olexiy

Problem categories:

Dynamic Programming, Greedy