TopCoder problem "HeatDeath" used in TCO04 Round 4 (Division I Level Two)



Problem Statement

    

The heat death of the universe occurs when all available energy has moved from "hot" (high energy) locations to "cold" (low energy) locations. Hot and cold are relative concepts--energy can flow from one location to another if and only if the energy level of the first location is at least 2 units greater than the energy level of the second location. Heat death occurs when there are no more locations between which energy can flow. Naturally, we would like to put off heat death for as long as possible.

You will be given a int[] energy that contains the energy levels of all locations in a closed system at time 0. Every microsecond, a random pair of locations whose energy levels differ by at least two units will be chosen, and a single unit of energy will flow from the hotter location to the colder location. Notice that the locations do not have to be adjacent. Depending on the order in which pairs of locations are chosen, heat death could arrive in different amounts of time. Calculate and return the maximum number of microseconds until the system reaches heat death.

 

Definition

    
Class:HeatDeath
Method:maxTime
Parameters:int[]
Returns:int
Method signature:int maxTime(int[] energy)
(be sure your method is public)
    
 

Constraints

-energy contains between 2 and 50 elements, inclusive.
-Each element of energy is between 1 and 999, inclusive.
 

Examples

0)
    
{ 5, 7, 9 }
Returns: 3
Heat death could arrive in as little as 2 microseconds, if energy flows twice from the third location to the first location. On the other hand, if energy first flows from the third location to the second location, then from the third location to the first location, and finally from the second location to the first location, heat death can be put off for a total of 3 microseconds. (Other sequences may also achieve the maximum.)
1)
    
{ 5, 6, 5, 6 }
Returns: 0
No heat can flow. This system has already reached heat death.
2)
    
{ 1, 1, 1, 1, 1, 999, 999, 999, 999, 999 }
Returns: 12435
3)
    
{ 354, 903, 100, 951, 669, 311, 339, 500, 942, 72, 712, 54, 64,
  572, 7, 977, 74, 524, 314, 160, 526, 729, 114, 691, 771, 704,
  288, 47, 735, 85, 694, 124, 349, 905, 611, 371, 885, 738, 165,
  442, 138, 348, 605, 239, 535, 33, 142, 946, 4, 231 }

Returns: 214090

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5881&pm=2982

Writer:

vorthys

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Greedy