Connection Status:
Competition Arena > Distincter

Distincter

SRM 285 · 2006-01-24 · by Andrew_Lazarev

SRM 285 · 2006-01-24 · by Andrew_Lazarev · Graph Theory
Class Name: Distincter
Return Type: int
Method Name: disperse
Arg Types: (vector<int>, int)
Problem Statement

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.

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.

Submissions are judged against all 71 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Distincter with a public method int disperse(vector<int> sequence, int K) · 71 test cases · 2 s / 256 MB per case

Submitting as anonymous