Overview

This is a problem where we determine the maximum number of wins player \(K\) can achieve, based on ratings.

Analysis

In this problem, the outcome between any two players is completely determined by the relative order of their ratings. That is, the player with the higher rating always wins, and the player with the lower rating always loses. Therefore, the maximum number of matches player \(K\) can win equals “the number of players with a rating lower than player \(K\)’s rating.”

For example, suppose player \(K\) has a rating of \(100\). If there are \(3\) other players with ratings lower than \(100\), then player \(K\) can win at most \(3\) times. This is because we can arrange the tournament bracket so that player \(K\) faces one of those lower-rated players in each round.

Since the tournament bracket can be arranged freely, we can maximize the number of wins by having player \(K\) encounter unfavorable opponents (those with higher ratings who could potentially defeat player \(K\)) as late as possible.

Therefore, all we need to do is simply count “the number of players with a rating lower than player \(K\)’s rating.”

Algorithm

1. Obtain player \(K\)’s rating \(S_K\).
2. Among all players, count the number of players where \(S_i < S_K\).
3. This count is the maximum number of matches player \(K\) can win, so output it.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Implementation Notes

• Player number \(K\) is given as 1-indexed, so when using it as an array index, you need to use \(K-1\).

• A simple brute-force count is sufficiently fast, so complex operations such as sorting or binary search are unnecessary.

  Source Code

import sys
from bisect import bisect_left

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    S = list(map(int, data[2:]))

    # 選手Kのレーティング
    rating_K = S[K-1]
    
    # 選手Kよりレーティングが低い選手の数を数える
    count_lower = 0
    for s in S:
        if s < rating_K:
            count_lower += 1
    
    # 選手Kが勝てる相手の数が答え
    print(count_lower)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.