WECREC - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: able_joy_75
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

N candidates participate in a contest, the i-th scores A_i.
All candidates with the same score for a cluster.
Only candidates from the top K clusters are eligible to go through to the next round; and the limit on their count is X.
What’s the maximum number of candidates who can be selected for the next round?

EXPLANATION:

This is more or less an implementation task.

Let \text{count}[y] denote the number of candidates who scored y.
Let y_1, y_2, \ldots, y_m be the distinct values such that \text{count}[y_i] \gt 0.

Then, observe that we’re only interested in the K largest values of y_i (well, more precisely the \min(K, m) largest values since there might be less than K clusters.)

Without loss of generality, let the clusters we’re interested in be y_1, y_2, \ldots, y_K.
Then, the number of candidates eligible for selection equals

S = \text{count}[y_1] + \text{count}[y_2] + \ldots + \text{count}[y_K]

Now,

  • If S \le X, all the candidates can go through. The answer is S.
  • If S \gt X, only X candidates can go through, so the answer is X.

One simple way to implement this is to first compute the \text{count} array, and then simply iterate through values in decreasing order - this way you automatically find the largest-score clusters.
While iterating, track the number of clusters processed so far; and when that number reaches K, break out.

TIME COMPLEXITY:

\mathcal{O}(N + \max(A)) or \mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, x, k = map(int, input().split())
    ct = [0]*1005
    a = list(map(int, input().split()))
    
    for i in range(n): ct[a[i]] += 1
    
    ans = 0
    taken = 0
    for i in reversed(range(1005)):
        if ct[i] == 0: continue
        
        taken += 1
        ans += ct[i]
        if taken == k: break
    print(min(ans, x))