TopCoder problem "TransformArray" used in TCHS SRM 43 (Division I Level One)



Problem Statement

    We have an array of positive integers. We will transform this array by repeating the following operation until there are less than two elements left:
  1. Choose the two elements that have the minimal absolute difference. If there are multiple such pairs, choose the one among them with the minimal sum. If there are still multiple pairs, choose any one of them.
  2. Decrease both elements in the pair by 1.
  3. Remove all zeros from the array.
It's easy to see that this process always ends in a finite number of steps.



For example, suppose we have an array of four integers {3, 2, 3, 2}. The transformation process goes like this:

Step 1: (3, 2, 3, 2) --> (3, 1, 3, 1) (decreasing values 2 and 2)

Step 2: (3, 1, 3, 1) --> (3, 3) (decreased elements became zeros, so we removed them)

Step 3: (3, 3) --> (2, 2)

Step 4: (2, 2) --> (1, 1)

Step 5: (1, 1) --> ()

Thus, we have an empty array at the end of the process.



You are given a int[] elements which represents the array to transform. Return the number of steps in the transformation process.

 

Definition

    
Class:TransformArray
Method:doTransform
Parameters:int[]
Returns:int
Method signature:int doTransform(int[] elements)
(be sure your method is public)
    
 

Constraints

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

Examples

0)
    
{3,2,3,2}
Returns: 5
The example from the problem statement.
1)
    
{3}
Returns: 0
There is already just one element in the array, so we do not have to perform the transformation at all.
2)
    
{1,2,3,4}
Returns: 4
The transformation process goes like this:

{1, 2, 3, 4} --> {1, 3, 4} --> {1, 2, 3} --> {1, 3} --> {2}
3)
    
{10,6,3,7,7,9,5,1,8,4}
Returns: 27

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10792&pm=6692

Writer:

it4.kp

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Simple Math