TopCoder problem "SetMetric" used in SRM 264 (Division II Level Three)



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.
 

Definition

    
Class:SetMetric
Method:nearness
Parameters:int[], int[]
Returns:int
Method signature:int nearness(int[] target, int[] candidate)
(be sure your method is public)
    
 

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

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7998&pm=4442

Writer:

Enogipe

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Dynamic Programming