TopCoder problem "Distincter" used in SRM 285 (Division I Level Three)



Problem Statement

    

We are given a int[] sequence containing a sequence of numbers. In a single operation, we can either increment or decrement the value of a single element by 1. Determine the minimum number of operations we must perform before the sequence contains at least K distinct elements.

 

Definition

    
Class:Distincter
Method:disperse
Parameters:int[], int
Returns:int
Method signature:int disperse(int[] sequence, int K)
(be sure your method is public)
    
 

Notes

-Note that we can create negative elements during the process.
 

Constraints

-sequence will contain between 1 and 50 elements, inclusive.
-Each element in sequence will be between 1 and 1000, inclusive.
-K will be between 1 and the number of elements in sequence, inclusive.
 

Examples

0)
    
{5, 1, 3}
2
Returns: 0
The sequence already has two distinct elements.
1)
    
{1, 1, 1, 1, 1, 1, 1}
5
Returns: 6
Some elements can become negative.
2)
    
{1, 1, 1, 1, 1, 2, 3}
6
Returns: 6
3)
    
{8, 9, 7, 8, 7, 9, 7}
7
Returns: 7
4)
    
{1, 2, 3, 4, 4, 5, 7, 7, 8}
9
Returns: 4
The optimal way to make 9 distinct elements is to increase one of the 4s two times and increase one of the 7s two times.
5)
    
{576, 571, 571, 572, 575, 572, 571, 568, 573, 572, 569, 572}
11
Returns: 12

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8082&pm=5951

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Graph Theory