Overview

Given the scores of N participants, this problem asks us to find the number of participants who should be awarded — specifically, all participants who have the same score as or higher than the K-th place participant.

Analysis

It is important to understand the problem conditions precisely. When scores are sorted in descending order, all participants whose score is greater than or equal to the K-th score (\(B_K\)) are eligible for the award. In other words, if multiple participants share the same score as the K-th place participant, all of them are awarded, so the total number of awardees can exceed K.

A straightforward approach is to sort all scores, determine the K-th score (the threshold), and then count the number of participants whose score is at or above this threshold. Since the constraint is \(N \leq 2 \times 10^5\), using an efficient sorting algorithm (\(O(N \log N)\)) is fast enough.

Algorithm

1. Sort the participants’ scores in descending order (largest first)
2. Obtain the K-th score (index K-1) as the threshold
3. Scan the sorted score list from the beginning and count the number of participants with scores at or above the threshold
   • Since the list is sorted in descending order, once a score below the threshold is encountered, there is no need to check further

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting the scores takes the most time
  • The subsequent scan is \(O(N)\) in the worst case
• Space complexity: \(O(N)\)
  • An array is needed to store the scores

Implementation Notes

• Sorting must be done in descending order (reverse=True)

• The K-th score can be accessed at index K-1 (due to 0-indexing)

• The loop can be terminated early when a score below the threshold is encountered (optimization)

• Reading input can be sped up by using sys.stdin.read() to read everything at once

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    k = int(data[1])
    scores = list(map(int, data[2:2+n]))
    scores.sort(reverse=True)
    threshold = scores[k-1]
    count = 0
    for score in scores:
        if score >= threshold:
            count += 1
        else:
            break
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.