Overview

This problem asks us to find the number of rounds in which some player’s score is at least twice the maximum score among all other players.

Analysis

Key Insight: Only the highest-scoring player can be “outstanding”

A player \(i\) is outstanding in round \(j\) if \(S_{j,i} \geq 2 \times M_{j,i}\) (where \(M_{j,i}\) is the maximum score among all players other than \(i\)).

Here, if player \(i\) does not have the highest score in that round, then \(M_{j,i} \geq S_{j,i}\), making it impossible to satisfy \(S_{j,i} \geq 2 \times M_{j,i}\) (since scores are at least \(1\)).

In other words, the only player who can possibly be outstanding is the one with the highest score in that round.

What is \(M_{j,i}\) for the highest-scoring player?

For the highest-scoring player, “the maximum score among all other players” equals the second-largest score in that round.

Therefore, we can determine the answer for each round by knowing only the 1st-place and 2nd-place scores.

Concrete Examples

Suppose the scores in some round are \([30, 10, 15, 5]\). - 1st-place score: \(30\), 2nd-place score: \(15\) - \(30 \geq 2 \times 15 = 30\) → The condition is satisfied, so the player is “outstanding”

If the scores are \([20, 10, 15, 5]\): - 1st-place score: \(20\), 2nd-place score: \(15\) - \(20 \geq 2 \times 15 = 30\) → The condition is not satisfied, so no player is “outstanding”

Algorithm

1. For each round, read the scores of \(N\) players.
2. In a single scan, find the maximum value (max1) and the second-largest value (max2).
   • If the current value is greater than or equal to max1, update max2 to the old max1, then update max1 to the current value.
   • Otherwise, if it is greater than max2, update max2.
3. If \(\text{max1} \geq 2 \times \text{max2}\) holds, then an “outstanding player” exists in that round.
4. Count the number of rounds satisfying the condition and output the result.

Sorting all players’ scores (\(O(N \log N)\)) also works, but since we only need the top two values, \(O(N)\) is sufficient.

Complexity

• Time complexity: \(O(N \times T)\)
  • We only scan the \(N\) players’ scores once per round, so the total is \(O(N \times T)\). Given the constraints \(N \times T \leq 10^6\), this is fast enough.
• Space complexity: \(O(N)\)
  • We only need to temporarily store the scores for each round.

Implementation Notes

• Fast input: In Python, reading all input at once with sys.stdin.buffer.read() and splitting with split() is fast. Since \(N \times T\) can be up to \(10^6\), repeatedly calling input() may be too slow.

• Finding the top two values: Manage max1 and max2 with initial value \(0\), comparing and updating with each element. Since scores are guaranteed to be at least \(1\), an initial value of \(0\) causes no issues.

• Handling ties: When multiple players share the highest score, max1 and max2 will have the same value. In this case, \(\text{max1} \geq 2 \times \text{max2}\) does not hold, so it is correctly determined as “not outstanding” (which is also consistent with the condition that at most one player can be outstanding in a single round).

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1
    
    count = 0
    for _ in range(T):
        scores = input_data[idx:idx+N]
        idx += N
        
        # Find the top two values
        max1 = 0
        max2 = 0
        for k in range(N):
            v = int(scores[k])
            if v >= max1:
                max2 = max1
                max1 = v
            elif v > max2:
                max2 = v
        
        # The best player's score is max1, the second best is max2
        # For the best player, M = max2
        # They are "outstanding" if max1 >= 2 * max2
        if max1 >= 2 * max2:
            count += 1
    
    print(count)

main()

---

This editorial was generated by claude4.6opus-thinking.