MINDIS6 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

Sorting

PROBLEM:

You’re given an array A of length N.
You can modify it as follows:

  • Choose indices i and j (1 \le i \lt j \le N), and set A_j to be equal to A_i

Minimize the number of distinct elements in A using at most K operations.

EXPLANATION:

Each operation allows us to overwrite a single element of A.
To ensure that some element x doesn’t appear in A at all, we thus need one operation for each index containing x.

Thus, if \text{freq}[x] denotes the frequency of x, we need at least \text{freq}[x] operations to ensure that x gets deleted entirely from A.

However, not every element can be deleted.
Note that the operation allows us to choose (i, j) with i \lt j, and overwrite A_j.
Thus, in particular we can never overwrite A_1.

So, no matter what we do, element A_1 will always be present in A - and so overwriting other occurrences of A_1 is pointless.
On the other hand, for any x \ne A_1, we can always overwrite all other appearances of x using exactly \text{freq}[x] operations; since we can simply choose i = 1 always and use element A_1 to do the overwriting for each index.

We want to minimize the number of distinct elements; meaning we want to completely overwrite as many different elements x as possible.
Clearly, it’s optimal to overwrite whichever elements have the smallest frequency, as long as we’re able to.

That is, we have the following algorithm:

  • Let \text{freq}[x] denote the frequency of x.
    This can be built in linear time simultaneously for all x.
  • Next, consider only those x such that x \neq A_1.
    Among these, we want to repeatedly choose the ones with smallest frequency and overwrite them entirely, if we have enough operations to do so.
  • This can be done easily by, for example, sorting the frequency array (after removing \text{freq}[A_1]).
    After sorting it, simply iterate through the values, and if the number of operations remaining is enough, eliminate the current element entirely and reduce the answer by 1.

The complexity is dominated by sorting, for \mathcal{O}(N\log N).
Since the values being sorted are \le N, counting sort can be used to attain a solution in \mathcal{O}(N) if you so wish.

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    freq = [0]*(n+1)
    for x in a: freq[x] += 1
    
    available = []
    ans = 0
    for i in range(1, n+1):
        if freq[i] > 0 and a[0] != i: available.append(freq[i])
        if freq[i] > 0: ans += 1
    available.sort()
    
    for x in available:
        if x <= k:
            ans -= 1
            k -= x
    print(ans)