TopCoder problem "VolumeGuess" used in SRM 191 (Division I Level One , Division II Level Two)



Problem Statement

    You are given a certain number of boxes (numberOfBoxes) of different volumes. The boxes are numbered 1 to numberOfBoxes. After this, I then make comparisions between every pair of boxes and, for each pair, tell you the volume of the smaller box. Given this data, you have to tell me the size of the box numbered ithBox. (The box numbered ithBox will not be one of the two largest boxes.)



You are given a String[], queries, each element of which describes a single comparision and is of the form "box1,box2,volume" (quotes for clarity) where box1 and box2 are the numbers of the two boxes being compared and volume is the volume of the smaller box. For instance, if I compare the boxes numbered 5 and 6, which have volumes 10 and 99, respectively, the query will be represented as "5,6,10" (quotes for clarity).
 

Definition

    
Class:VolumeGuess
Method:correctVolume
Parameters:String[], int, int
Returns:int
Method signature:int correctVolume(String[] queries, int numberOfBoxes, int ithBox)
(be sure your method is public)
    
 

Notes

-Keep in mind, the volume of the largest box is irrelevant.
 

Constraints

-numberOfBoxes will be between 3 and 9, inclusive.
-queries will contain exactly numberOfBoxes*(numberOfBoxes-1)/2 elements.
-Every element of queries will be in the given format ("box1,box2,volume", quotes for clarity).
-Each element of queries will contain between 5 and 50 characters, inclusive.
-Each box1 will be an integer between 1 and numberOfBoxes, inclusive, with possible leading zeros.
-Each box2 will be an integer between 1 and numberOfBoxes, inclusive, with possible leading zeros.
-Each volume will be an integer between 1 and 500, inclusive, with possible leading zeros.
-queries will contain no duplicates, that is, no pair of boxes will be compared twice.
-No two boxes will have the same volume.
-ithBox will be between 1 and numberOfBoxes, inclusive.
-The given data will be consistent.
-The box numbered ithBox will not be one of the two largest boxes.
 

Examples

0)
    
{"1,2,10","1,3,10","2,3,20"}
3
1
Returns: 10
If box 1 has volume 10, box 2 has volume 20 and box 3 has volume 30, we get the given data. Another possibility is box 1 has volume 10, box 2 has volume 30 and box 3 has volume 20. Another is box 1 has volume 10, box 2 has volume 45 and box 3 has volume 20. There are many possibilities (infinite in fact). However, in all of them box 1 has to have size 10.
1)
    
{"1,02,10","2,3,010","1,3,20"}
3
2
Returns: 10
If box 1 has volume 20, box 2 has volume 10 and box 3 has volume 30, we get the given data. (Note that leading zeros are allowed.)
2)
    
{"1,2,31","1,3,9","1,4,31","2,4,32","3,4,9","3,2,9"}
4
1
Returns: 31
One possibility is box 1 has volume 31, box 2 has volume 50, box 3 has volume 9 and box 4 has volume 32.
3)
    
{"1,2,31","1,3,9","1,4,31","2,4,32","3,4,9","3,2,9"}
4
3
Returns: 9
Same situation as above, but asks for a different ithbox.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4775&pm=2330

Writer:

Ishan

Testers:

lbackstrom , vorthys

Problem categories:

Brute Force