TopCoder problem "WeighingBalls" used in MM 3 (Division I Level One)

Problem Statement


You have n steel balls each with a weight of 1001, 1002 or 1003 grams. Your task consists of indentifying the exact weight of each one of them. You can make use of two different types of balances, but you want to minimize the overall cost of all the weighings you make before you finally guess the weight of each ball. You have:

  • A digital balance that gives you the total weight for any set of balls.
  • A plate balance that tells you which of two disjoint sets of balls weighs more (or if the two sets weigh the same amount).

Each use of the plate balance costs 100, while the cost per use of the digital balance will be given by digitalCost. You are to write two methods: init and next. First, init will be called with n and digitalCost. This method should return a int[] representing your first use of a balance or a guess of the balls' weights.

Subsequently, the method next will be called with a single int giving the result of the previous guess. This method should return either a new use of a balance or a guess of the balls' weights. After you make a guess, no extra calls to any of your methods will be made.

The int[] returned from init or next must have exactly n elements, and one of the following forms:

  • If all elements are between 1001 and 1003, inclusive, it will mean a guess of the weights.
  • If all elements are either 0 or 1, it will mean you are using the digital balance with all balls that have a 1 in their position being weighed. The next call to next will be given the exact weight of that set of balls.
  • If all elements are -1, 0 or +1 and there is at least one -1 and one +1, it will mean that you are using the plate balance where -1 indicates a ball on the right plate, while +1 indicates the left plate. The next call to next will be given -1 if the set of balls in the right plate weighs more, 0 if the sets have equal weight and 1 if the set of balls in the left plate weighs more.

The score you will get for each test case is 0 if the final guess is incorrect or in any call the returned int[] does not follow the protocol above. Otherwise, if your final guess is correct, your score will be 10*n*sqrt(digitalCost) / totalCost, where totalCost is your cost of using the balances (or 1 if you don't use the balances at all). Your final score is simply the sum of your scores on the individual test cases.

In 75% of the test cases n will be chosen uniformly between 10 and 100, inclusive, and it will be exactly 100 in the other 25%. digitalCost will be chosen uniformly between 80 and 250, inclusive. The weight of each ball will be chosen independently and uniformly among the three possible weights. If after doing that there is at least one ball that weighs 1000+k for each k between 1 and 3, inclusive, that test case is accepted. If there is not, all weights are chosen again (n and digitalCost are not).

The time limit for each test case is 20 seconds (adding up all the calls of both methods), and the memory limit is 64 megabytes. The maximum number of balance uses is n*n, which means your next method will be called at most n*n times with a result. If the last of those calls does not contain a guess, you will get 0 points for the test case.



Parameters:int, int
Method signature:int[] init(int n, int digitalCost)
Method signature:int[] next(int lastResult)
(be sure your methods are public)


-In the first 5 examples n was not chosen randomly to facilitate testing. In the rest of the examples it was. In all system test cases it will be chosen as explained in the problem statement.
-There are 100 non-example test cases.


"10 1"
"n = 10<br/>
digitalCost = 150<br/>
weights = <br>
This could be one possible and correct sequence of calls and their returns:

init(10,150) returns {0,0,1,1,0,0,0,1,0,0}

Here you put balls 2, 3 and 7 in the digital balance. They all weigh 1001, so the next call to next is given 1001*3=3003.


You can deduce that each of the 3 weighed balls weights 1001, because is the only way to achieve 3003.

returns {1,1,1,1,1,1,1,1,1,1}

Now you put all balls in the digital balance, the total weight given in the next call to next is 10021.

next(10021) returns {1,-1,0,0,0,0,0,0,0,0}

Ball 1 is in the right plate and weighs 1002, ball 0 is in the left plate and weights 1003, so the left plate weighs more and next call to next is given 1.

next(1) returns {1,1,0,0,1,0,1,0,1,0}

Here you weigh balls 0, 1, 4, 6 and 8 in the digital balance.


The only way to achieve 5014 with 5 balls is to have 4 of them with weight 1003 and 1 with weight 1002. Since ball 1 is lighter than ball 0, we can deduce that balls 0, 4, 6 and 8 weigh 1003 and ball 1 weighs 1002.

returns {0,0,0,0,0,1,0,0,0,-1}

Now we ask for the relative weights of the 2 balls we can't deduce yet (5 and 9). Since they weigh the same we are given 0 as result.


By the total weight of 10021 given in an early balance use we can deduce that the sum of weights of balls 5 and 9 is 2004 (since we know the exact weight of all the other balls, we can just substract them from the total weight). If they weigh the same, each one weighs 2004/2 = 1002. Now we have the exact weight for all the balls, so we guess.

returns {1003,1002,1001,1001,1003,1002,1003,1001,1003,1002}

The score in this case is 10*10*sqrt(150)/(3*150+2*100) because we used the digital balance three times, each with a cost of 150 and twice the plate balance, each with a cost of 100.
"10 4135995"
"n = 10<br/>
digitalCost = 138<br/>
weights = <br>
This could be one possible and correct sequence of calls and their returns:

init(10,138) returns {1,0, 0,0,0,0,0,0,0,0}
next(1001)   returns {0,1, 0,0,0,0,0,0,0,0}
next(1003)   returns {0,0, 1,0,0,0,0,0,0,0}
next(1002)   returns {0,0,-1,1,0,0,0,0,0,0}
next(0)      returns {0,0,-1,0,1,0,0,0,0,0}
next(-1)     returns {0,0,-1,0,0,1,0,0,0,0}
next(1)      returns {0,0,-1,0,0,0,1,0,0,0}
next(0)      returns {0,0,-1,0,0,0,0,1,0,0}
next(0)      returns {0,0,-1,0,0,0,0,0,1,0}
next(-1)     returns {0,0,-1,0,0,0,0,0,0,1}
next(-1)     returns {1001,1003,1002,1002,1001,1003,1002,1002,1001,1001}
Here we find out the first 3 weights using the digital balance. As soon as we find a ball with 1002 weight, we can decide each individual weight using the plate balance that is cheaper.

In this case the score is 10*10*sqrt(138)/(3*138+7*100), with 3 uses of the digital balance and 7 uses of the plate balance.
"11 45736"
"n = 11<br/>
digitalCost = 250<br/>
weights = <br>
"14 35463"
"n = 14<br/>
digitalCost = 108<br/>
weights = <br>
"20 534591"
"n = 20<br/>
digitalCost = 226<br/>
weights = <br>
"n = 57<br/>
digitalCost = 187<br/>
weights = <br>
"n = 30<br/>
digitalCost = 197<br/>
weights = <br>
"n = 93<br/>
digitalCost = 87<br/>
weights = <br>
"n = 14<br/>
digitalCost = 119<br/>
weights = <br>
"n = 100<br/>
digitalCost = 201<br/>
weights = <br>

Problem url:

Problem stats url:




lbackstrom , Andrew_Lazarev

Problem categories: