SetMetric
SRM 264 · 2005-09-20 · by Enogipe
SRM 264 · 2005-09-20 · by Enogipe · Dynamic Programming
Problem Statement
Problem Statement
Suppose the solution to some problem is a set of integers, several of which you do not know. You wish to evaluate the nearness of some candidate set of known integers to the solution. For example, the candidate solution might be {9, 1, 2, 3, 5, 6}, while the target is {4, 9, 2, 1}: actually six integers, but two are unknown. We define the distance between a target and a candidate to be the minimum sum of absolute differences in known values, disregarding extraneous candidate values. Here the distance would be |4-3| + |9-9| + |2-2| + |1-1| = 1: we have ignored the 5 and 6. Given a int[] target and a int[] candidate, return the distance between them.
Constraints
- candidate will contain between 1 and 20 elements, inclusive.
- target will contain between 1 and 20 elements, inclusive.
- target will not contain more elements than candidate.
- Each element of target and candidate will be between -1000 and 1000, inclusive.
Examples
0)
{4,9,2,1}
{9,1,2,3,5,6}
Returns: 1
The example from the problem statement.
1)
{0}
{1000,-1000,0}
Returns: 0
Only one of the numbers is relevant; the extreme cases do not affect this answer.
2)
{1000,-1000,0,5,289,-40}
{30,821,-777,-52,91,444,-134,85}
Returns: 679
3)
{572,555}
{877,173,-394}
Returns: 687
4)
{291}
{-619,-303,860}
Returns: 569
Submissions are judged against all 78 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SetMetric with a public method int nearness(vector<int> target, vector<int> candidate) · 78 test cases · 2 s / 256 MB per case