Overview

In a tournament with \(N\) players where you can freely decide the matchups, the problem asks for the maximum number of wins a specific player \(K\) can achieve. In each match, the player with the higher rating always wins.

Analysis

The key points for solving this problem are thinking about “Who can player \(K\) beat?” and “How should we arrange the matchups with those opponents?”

1. Conditions for Player \(K\) to Win

According to the problem statement, the player with the higher rating always wins a match. Therefore, for player \(K\) to win a match, the opponent’s rating must be less than \(S_K\). Conversely, if player \(K\) faces an opponent with a rating higher than \(S_K\), player \(K\) will inevitably lose and be eliminated at that point.

2. Strategy to Maximize Wins

To maximize the number of wins for player \(K\), the effective strategy is to “have player \(K\) fight all opponents they can beat (those with lower ratings) one by one in sequence.”

For example, suppose there are \(m\) players with ratings lower than player \(K\). 1. First, have player \(K\) face “player A who has a lower rating.” Player \(K\) wins, and the win count becomes 1. 2. Next, have the surviving player \(K\) face “another player B who has a lower rating.” Player \(K\) wins, and the win count becomes 2. 3. By repeating this \(m\) times, player \(K\) can achieve \(m\) victories.

3. What About Stronger Players?

If players with higher ratings than player \(K\) remain, there is a possibility that player \(K\) could lose. However, since we are free to arrange the tournament bracket, we can “have the stronger players fight among themselves first, eliminating all but one of them.” Even if player \(K\) eventually faces the last remaining strongest player and loses, as long as they have already beaten all weaker players before that, the win count is maximized.

From the above analysis, we can see that the maximum number of wins for player \(K\) equals “the number of players among all participants whose rating is lower than player \(K\)’s rating.”

Algorithm

1. Obtain player \(K\)’s rating \(S_K\).
2. For all players \(i = 1, 2, \ldots, N\), check their rating \(S_i\).
3. Count the number of players satisfying \(S_i < S_K\).
4. Output the counted value as the answer.

Complexity

• Time Complexity: \(O(N)\)
  • Since we check each player’s rating exactly once, the computation finishes in time proportional to the number of players \(N\). With \(N=10^5\), this is sufficiently fast.
• Space Complexity: \(O(N)\)
  • When storing all players’ ratings in a list, the memory usage is proportional to \(N\).

Implementation Notes

• Player number \(K\) is often given as 1-indexed (starting from 1), but lists in programming languages (such as Python) are often 0-indexed (starting from 0), so be careful with index handling (player \(K\)’s rating can be obtained with S[K-1]).

• Since the problem states that all \(S_i\) are distinct, there is no need to explicitly exclude the comparison with player \(K\) themselves (since \(S_K < S_K\) is always false).

  Source Code

import sys

# The problem asks for the maximum number of matches player K can win.
# In a tournament where Takahashi can freely decide the pairings,
# player K can win a match against any player with a lower rating.
# Let m be the number of players whose rating is less than player K's rating.
# Each match player K wins must be against one of these m players.
# Since each player is eliminated after losing once, player K can win at most m matches.
# Takahashi can achieve this maximum by having player K face each of these m players
# one by one in the first m matches. Any players with ratings higher than player K
# can be paired with each other until only one remains, whom player K will eventually
# face and lose to (unless player K is already the overall winner).

def solve():
    # Read all input from standard input at once for efficiency.
    input_data = sys.stdin.read().split()
    if len(input_data) < 2:
        return
    
    # N: total number of players
    # K: the index of the player Takahashi supports (1-indexed)
    n = int(input_data[0])
    k = int(input_data[1])
    
    # S: list of ratings of all N players.
    # Ratings are provided as S1, S2, ..., SN.
    # In Python's 0-indexed list, player K's rating is at index K-1.
    s = list(map(int, input_data[2:2+n]))
    
    # Get the rating of player K.
    target_rating = s[k-1]
    
    # Count how many players have a rating strictly less than target_rating.
    # Every such player represents a potential win for player K.
    max_wins = 0
    for rating in s:
        if rating < target_rating:
            max_wins += 1
            
    # Output the result.
    print(max_wins)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.