Overview

This problem asks you to calculate each player’s final score according to the scoring rules, and count the number of players whose score is below the threshold (eliminated in preliminaries).

Analysis

In this problem, the method for calculating the final score changes depending on the number of judges \(M\).

Understanding the Scoring Rules

• When \(M \geq 3\): Remove one highest and one lowest score before calculating the average. This is a method also used in actual figure skating, designed to reduce the impact of extreme scoring (favoritism/undervaluation).
• When \(M \leq 2\): If we remove scores, either no scores remain or only one remains, so we calculate the average of all scores as-is.

Concrete Example

For example, if a player receives scores of \([60, 70, 80, 90, 100]\) from 5 judges: - Remove the highest score \(100\) and lowest score \(60\) - Remaining scores are \([70, 80, 90]\) - Average is \((70 + 80 + 90) / 3 = 80\) points

Why a Naive Approach Works

With constraints of \(N \leq 10^5\) and \(M \leq 100\) in this problem, performing \(O(M \log M)\) processing (sorting) for each player is sufficiently fast. No special optimization is needed—simply implement the solution straightforwardly as described in the problem statement.

Algorithm

1. For each player, read \(M\) scores
2. If \(M \geq 3\):
   • Sort the scores
   • Extract the portion excluding the minimum (first element) and maximum (last element)
   • Calculate the average (truncate decimal places)
3. If \(M \leq 2\):
   • Calculate the average of all scores (truncate decimal places)
4. If the final score is less than the threshold \(K\), increment the elimination counter
5. After processing all players, output the number of eliminated players

Reason for Using Sort

After sorting, the array is arranged in ascending order, so scores_sorted[0] is the minimum and scores_sorted[-1] is the maximum. Using Python’s slice scores_sorted[1:-1], we can easily extract the portion excluding the minimum and maximum.

Complexity

• Time Complexity: \(O(N \cdot M \log M)\)
  • Sorting scores for each player takes \(O(M \log M)\)
  • Repeating for \(N\) players gives \(O(N \cdot M \log M)\) overall
• Space Complexity: \(O(M)\)
  • \(O(M)\) to temporarily store each player’s scores

Implementation Notes

• Truncating decimal places: In Python, using the // operator for integer division automatically truncates the result.
• Using slices: scores_sorted[1:-1] retrieves the subarray excluding the first and last elements. This is a concise way to implement “excluding the highest and lowest scores”.
• Conditional branching: Don’t forget to separate the processing for \(M \geq 3\) and \(M \leq 2\). Make sure the solution works correctly even for cases where \(M = 1\) or \(M = 2\).

Source Code

def solve():
    N, M, K = map(int, input().split())
    
    eliminated = 0
    
    for _ in range(N):
        scores = list(map(int, input().split()))
        
        if M >= 3:
            # Average of remaining scores after removing one highest and one lowest
            scores_sorted = sorted(scores)
            remaining = scores_sorted[1:-1]  # Exclude minimum and maximum
            final_score = sum(remaining) // len(remaining)
        else:
            # When M <= 2: average of all scores
            final_score = sum(scores) // len(scores)
        
        if final_score < K:
            eliminated += 1
    
    print(eliminated)

solve()

---

This editorial was generated by claude4.5opus.