Connection Status:
Competition Arena > MislabeledWeights

MislabeledWeights

TC China 08 - 1A · 2008-11-23 · by dplass

TC China 08 - 1A · 2008-11-23 · by dplass · Brute Force, Dynamic Programming, Greedy, Math, Simple Search, Iteration
Class Name: MislabeledWeights
Return Type: int
Method Name: fewest
Arg Types: (vector<int>, int)
Problem Statement

Problem Statement

You are given a balance scale to weigh some items. Unfortunately the weights you use as counterbalances are not accurate. Some of them may be marked incorrectly - either 1 gram too heavy or one gram too light. (Some may be marked correctly.)

You are given a int[] weights representing the set of weights you have. The i-th of your weights is marked by weights[i] grams. The subset of your weights is called good if it's possible that all the real weights in it sum exactly to testWeight. Find the good subset with the minimum possible number of weights and return the number of weights in it. If there is no good subset of weights, your method should return -1.

Notes

  • A weight labeled '1 gram' (represented as the integer 1 in the int[] of weights) can only be 1 or 2 grams. All other weights can be plus or minus 1 gram of their actual labeled weight.
  • There may be duplicates in the weights but you may only use each element at most once.

Constraints

  • weights will contain between 1 and 10 elements, inclusive.
  • Each element of weights will be between 1 and 1000, inclusive.
  • testWeight will be between 1 and 10000, inclusive.
Examples
0)
{1,1,1}
6
Returns: 3

The subset of all weights is the only good one. If all the real weights are 2 grams, then they sum up to 6 grams.

1)
{1,1,1}
7
Returns: -1

Even if each weight was actually 2 grams, there would still be no way for them to sum to 7 grams.

2)
{1,2,3,4,5}
7
Returns: 2

There are many good subsets. For example, {1, 5} (1 + 6 = 7 or 2 + 5 = 7), or {3, 4} (3 + 4 = 7 or 4 + 3 = 7), or {3, 5} (3 + 4 = 7 or 2 + 5 = 7), or other variants. In any case, the fewest number of weights in a good subset is 2.

3)
{1,2,4,8,16,32,64,128}
47
Returns: 2
4)
{999,1000,1000,999,1000}
3000
Returns: 3
20)
{1, 243, 81, 683}
841
Returns: -1

682 + 242 - 1 - 82 = 841 can't put 1 or 82 on the "other" side.

Submissions are judged against all 126 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MislabeledWeights with a public method int fewest(vector<int> weights, int testWeight) · 126 test cases · 2 s / 256 MB per case

Submitting as anonymous