Overview

This is a problem where we count how many rounds have the property that the highest scorer’s score is at least twice the second highest score.

Analysis

The condition stated in the problem — “a player’s score is at least twice the maximum score of all other players” — can naturally only be satisfied by the player with the highest score in that round.

Therefore, a naive approach that searches for “the maximum among all others” for every player (with \(O(N^2)\) computation per round) would result in an overall complexity of \(O(T N^2)\), which would exceed the time limit (TLE) under the constraints (\(N \times T \le 10^6\)).

The key insight to solve this efficiently is that we only need to know the largest and second largest scores in each round. If we denote the largest score as \(m_1\) and the second largest as \(m_2\), then if \(m_1 \ge 2 \times m_2\) holds, there exists an “outstanding” player in that round.

Let’s consider some concrete examples: - For scores [10, 3, 4]: the largest is \(10\), the second largest is \(4\). Since \(10 \ge 2 \times 4\) holds, the condition is satisfied. - For scores [10, 6, 10]: the largest is \(10\), the second largest is also \(10\). Since \(10 \ge 2 \times 10\) does not hold, the condition is not satisfied.

Algorithm

For each round, perform the following steps:

1. Receive the list of scores for all players in that round.
2. Find the maximum value \(m_1\) in the list.
3. Remove only one occurrence of \(m_1\) from the list.
4. Find the maximum value in the remaining list. This becomes the second largest value \(m_2\) in the original list.
5. Check whether \(m_1 \ge 2 \times m_2\) holds; if so, increment the answer count by \(1\).
6. Repeat the above for all rounds and output the final count.

Complexity

• Time complexity: \(O(N \times T)\) In each round, finding the maximum with max() and removing an element with remove() are both \(O(N)\) operations. Since this is repeated for \(T\) rounds, the overall complexity is \(O(N \times T)\). This runs sufficiently fast for the constraint \(N \times T \le 10^6\).
• Space complexity: \(O(N \times T)\) Since the input is read all at once using sys.stdin.read().split() and stored in a list, it uses \(O(N \times T)\) memory to hold the entire input data.

Implementation Notes

• Speeding up input: In Python, calling input() many times can cause delays when the input data is large. By reading the input all at once using sys.stdin.read().split() as done here, we can significantly reduce I/O overhead.

• Behavior of the remove() method: scores.remove(m1) removes only the first occurrence of m1 found in the list. Therefore, even if multiple players are tied for the highest score (e.g., [10, 6, 10]), only the first 10 is removed, and the second maximum \(m_2\) correctly picks up the other 10.

• Alternative approach (sorting): Another method is to sort the score list in descending order (scores.sort(reverse=True)) and then retrieve m1 = scores[0], m2 = scores[1]. The computation per round in this case is \(O(N \log N)\), but it is still fast enough for the given constraints. However, the approach presented here, which finds the maximum twice in \(O(N)\), is faster.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    N = int(data[0])
    T = int(data[1])
    
    ans = 0
    idx = 2
    for _ in range(T):
        scores = [int(x) for x in data[idx:idx+N]]
        idx += N
        
        m1 = max(scores)
        scores.remove(m1)
        m2 = max(scores)
        
        if m1 >= m2 * 2:
            ans += 1
            
    print(ans)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.