TopCoder problem "BalancingAct" used in Member SRM 482 (Division I Level Three)

Problem Statement

Dave has a balance with which to weigh objects, and a number of reference weights of known value. All weights are integers between 1 and 100000000 (10^8), inclusive. The balance has 2 pans, each of which can hold any number of objects. The balance will indicate which pan contains more total weight, or that the pans contain equal amounts of weight.

Dave has a problem. His arch nemesis, Earl, has removed the labels from some of the weights, in an attempt to prevent Dave from knowing their values. Dave will attempt to recover the values of the unlabeled weights using the balance and the remaining weights. You are asked to figure out if Dave will succeed.

You will be given a int[] labeled giving the values of all of the weights with their labels intact, and int[] unlabeled, the actual values of the unlabeled weights. Return a String[] with the same number of elements as unlabeled, each "yes" if Dave can determine the value of the corresponding unlabeled weight, or "no" otherwise (quotes for clarity only).

Definition

Class:	BalancingAct
Method:	recover
Parameters:	int[], int[]
Returns:	String[]
Method signature:	String[] recover(int[] labeled, int[] unlabeled)
(be sure your method is public)

Notes

Dave knows that the weights are positive integers not exceeding 100000000 (10^8). See example 2.

Constraints

labeled will have between 1 and 20 elements, inclusive.

unlabeled will have between 1 and 4 elements, inclusive.

All elements of labeled will be between 1 and 100000000 (10^8), inclusive.

All elements of unlabeled will be between 1 and 100000000 (10^8), inclusive.

Examples

{9,13,15,16}

{19}

Returns: {"yes" }

Dave places the 9 weight and the unlabeled weight in one pan, and the 13 and 15 weights in the other.

{20}

{10,10}

Returns: {"yes", "yes" }

Dave may make multiple weighings.

{33333332,33333334}

{33333333,73,100000000}

Returns: {"yes", "no", "yes" }

Here, Dave uses the fact that all weights are integers between 1 and 100000000.

{12}

{1,1,2,2}

Returns: {"yes", "yes", "yes", "yes" }

{31415926,5358979,32384626,43383279,50288419,
71693993,75105820,9749445,92307816,40628620,
89986280,34825342,11706798,21480865,13282306}

{64709384,46095505,82231725,35940812}

Returns: {"no", "no", "no", "no" }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14235&pm=10855

Writer:

pieguy

Testers:

ivan_metelsky , boba5551 , it4.kp , abal9002

Problem categories:

Dynamic Programming, Search