Overview

For each round, determine whether there is a player who scored overwhelmingly higher than everyone else, and output the number of such rounds.

Analysis

In this problem, for each round, we need to determine whether there exists a player satisfying the following condition:

Their score \(S_{j,i}\) is at least twice the maximum score \(M_{j,i}\) among all other players.

In other words, if the highest score among all players other than themselves is \(M_{j,i}\), then if
$\( S_{j,i} \geq 2 \times M_{j,i} \)$
holds, the player can be considered “outstanding.”

Naive Approach and Its Issues

Naively, for each round, we can process as follows: 1. Look at each player’s score and find the maximum value \(max\). 2. Confirm that exactly one player achieved the maximum. 3. Find the second highest score \(second\_max\). 4. If \(max \geq 2 \times second\_max\), then that player is “outstanding.”

This method itself is correct, but depending on the implementation, it can become inefficient. For example, sorting each time to extract the second largest value worsens the time complexity (discussed below).

Also, when the maximum value appears multiple times (e.g., three players all have 100 points), no one can be considered “outstanding.” Be careful not to overlook this point.

Improvement

By finding the maximum and second maximum in a single pass, we can determine the result efficiently: - Count the number of occurrences of the maximum → if it appears more than once, stop immediately - Record the largest value among the remaining values → this is the second maximum

This allows linear-time determination for each round.

Algorithm

1. For each round, perform the following:
   • Find the maximum value \(max\) from the list of scores.
   • Count the number of occurrences of \(max\).
   • If the count is 2 or more, there is no “outstanding” player, so move to the next round.
   • Otherwise, find the second largest score \(second\_max\).
   • If \(max \geq 2 \times second\_max\), increment the count.
2. Output the total count across all rounds.

Complexity

• Time complexity: \(O(N \times T)\)
  Since we scan all players for each round, the total is \(T\) rounds × \(N\) players = \(O(NT)\).
• Space complexity: \(O(N \times T)\)
  Because all score data is stored in memory.

Implementation Notes

• Use sys.stdin.read for fast input to handle large inputs efficiently.

• Efficiently obtain the maximum and second maximum for each round.

• When the maximum appears multiple times, skip immediately to avoid unnecessary processing.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    T = int(data[1])
    
    # Read all scores into a list of lists
    scores = []
    index = 2
    for _ in range(T):
        round_scores = list(map(int, data[index:index + N]))
        scores.append(round_scores)
        index += N

    count = 0

    for round_scores in scores:
        max_score = max(round_scores)
        # Count how many times the maximum score appears
        max_count = round_scores.count(max_score)
        
        # If the max score appears more than once, no one can be outstanding
        if max_count > 1:
            continue
        
        # Find the second highest score
        second_max_score = 0
        for score in round_scores:
            if score < max_score and score > second_max_score:
                second_max_score = score
        
        # Check if the max score is at least twice the second max
        if max_score >= 2 * second_max_score:
            count += 1

    print(count)

if __name__ == "__main__":
    main()

---

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