Overview

In a tournament where the player with the higher rating always wins, we need to find the maximum number of wins player \(K\) can achieve. The conclusion is that the answer is “the number of players with a rating lower than \(K\)’s.”

Analysis

The key point of this problem is that the tournament bracket “can be freely decided each round.” In a typical fixed-bracket tournament, the number of wins would generally be limited to around \(O(\log N)\), but in this problem, any two players can be chosen to compete in each match, so player \(K\) can be made to compete as many times as desired (as long as they keep winning).

Since all ratings are distinct and the stronger player always wins, the following holds:

• Player \(K\) can only win against opponents with a lower rating.
  • Therefore, the upper bound on the number of wins is “the number of players weaker than \(K\).”
• This upper bound is actually achievable.
  • The organizer can, each round, match \(K\) against a remaining weaker player if one still exists.
  • \(K\) will always win, and weaker players are eliminated one by one.
  • Once all weaker players have been defeated, only \(K\) and players stronger than \(K\) remain, so no more wins are possible (matching against a stronger opponent results in a guaranteed loss).

Therefore, the maximum number of wins equals “the total number of players with a rating lower than \(K\)’s.”

Concrete Example

Suppose \(S = [10, 30, 20, 40]\) and \(K\)’s rating is \(30\). There are 2 players with ratings lower than \(30\): \(10\) and \(20\), so the answer is 2. In practice, we can have \(K\) compete against \(10\) and win → then compete against \(20\) and win, achieving 2 wins. After that, only \(40\) remains, so no more wins are possible.

Algorithm

1. Let player \(K\)’s rating be \(r_K = S_K\).
2. Count the number of players satisfying \(S_i < r_K\) among all players.
3. Output that count.

This simply counts “the number of opponents \(K\) can beat.”

Complexity

• Time complexity: \(O(N)\) (just a single pass to count)
• Space complexity: \(O(1)\) (constant, excluding the input array)

Implementation Notes

• \(K\) is given as 1-indexed, so in Python arrays, be careful to use \(S[K-1]\).

• You simply need to count “the number of elements smaller than \(K\)’s rating”; sorting is not necessary.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    S = list(map(int, input().split()))
    rk = S[K - 1]
    ans = sum(1 for x in S if x < rk)
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.