TopCoder problem "MedianProcess" used in TCCC06 Qual 1 (Division I Level One)



Problem Statement

    We wish to assign a score to the given array values. An empty array is assigned the score 0. Otherwise, we have one of the following cases:
  • The array has an odd number of elements: Compute the median m, remove one copy of m from the array, and then compute the score s of the new smaller array. The resulting score is s + m.
  • The array has an even number of elements: Find the maximum element m, remove one copy of m from the array, and then compute the score s of the new smaller array. The resulting score is s - m.
Return the score of values.
 

Definition

    
Class:MedianProcess
Method:getScore
Parameters:int[]
Returns:int
Method signature:int getScore(int[] values)
(be sure your method is public)
    
 

Notes

-Given K numbers, their median is the ((K+1)/2)-th smallest of them, rounding down for even K, and indexing from 1. For example, the median of (1, 2, 2, 3, 5) is 2, and the median of (11, 13, 12, 14, 15) is 13.
 

Constraints

-values will contain between 0 and 50 elements, inclusive.
-Each element of values will be between -1000 and 1000, inclusive.
 

Examples

0)
    
{}
Returns: 0
The array is empty, so we return 0.
1)
    
{2}
Returns: 2
We remove the median 2 and obtain an empty array. Thus the return value is 2.
2)
    
{2,3}
Returns: -1
We first remove the max 3, and later the median 2. Thus the result is -1.
3)
    
{1,1,1,1}
Returns: 0
4)
    
{371,-56,933,519,583,520,938,-398,75,-269,895,-790,982,-941,937,888,-416,-360,714,-594,-783,431,595}
Returns: -12234

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10093&pm=6698

Writer:

AdminBrett

Testers:

PabloGilberto , Cosmin.ro , Olexiy

Problem categories:

Simple Search, Iteration