Overview

This is a problem where you calculate each student’s total score and determine their rank as “the number of students with a strictly higher score \(+ 1\)”.

Analysis

Problem Breakdown

For each student, sum up the points of the problems they solved correctly, and determine their rank based on that total score. Since the rank is “the number of students with a strictly higher total score \(+ 1\)”, students with the same score receive the same rank.

For example, if the total scores are \([100, 80, 80, 60]\), the ranks are \([1, 2, 2, 4]\) (both students with 80 points are ranked 2nd, and the student with 60 points is ranked 4th).

Issues with the Naive Approach

If we compare each student against all other students to count “the number of people with a higher score,” this takes \(O(N^2)\). Since \(N\) can be up to \(2 \times 10^5\), this might still be feasible, but we can do it more efficiently.

Efficient Method

By aggregating the number of students per total score (Counter) and sorting the scores in descending order while maintaining a cumulative count, we can compute the rank for each score in \(O(N \log N)\) overall.

Specifically, iterating through scores in descending order: - The rank of the current score = the cumulative count so far (number of people with higher scores) \(+ 1\) - Then, add the count of the current score to the cumulative total

This way, we store the rank for each score in a dictionary (hash map), and finally look up each student’s rank from their score in \(O(1)\).

Algorithm

1. Read input: Obtain \(N\), \(M\), point values \(P\), and each student’s answer string \(S_i\).
2. Calculate total scores: For each student \(i\), if the \(j\)-th character of \(S_i\) is o, add \(P_j\) to compute the total score \(\text{scores}[i]\). (\(O(N \times M)\))
3. Count students per score: Use Counter to count the occurrences of each score. (\(O(N)\))
4. Calculate ranks: Sort the unique scores in descending order and use a cumulative count to determine the rank for each score.
   • Start with cumulative count \(= 0\)
   • For score \(sc\): \(\text{rank}[sc] = \text{cumulative count} + 1\)
   • cumulative count \(+= \text{cnt}[sc]\)
5. Output: Output the rank corresponding to each student’s score.

Complexity

• Time complexity: \(O(N \times M + N \log N)\)
  • Computing total scores takes \(O(N \times M)\) (from constraints, \(N \times M \leq 5 \times 10^6\))
  • Sorting unique scores takes \(O(N \log N)\) (at most \(N\) unique scores in the worst case)
• Space complexity: \(O(N + M)\)
  • \(O(N)\) for the score array, \(O(M)\) for the point value array, \(O(N)\) for the rank dictionary

Implementation Notes

• Fast input: By reading all input at once with sys.stdin.buffer.read() and splitting into tokens with split(), we ensure that input does not become a bottleneck even in Python.

• Rank calculation using Counter + descending sort: Instead of sorting all students by score, it suffices to sort only the unique scores. This is especially efficient when many students share the same score.

• Batch output: By outputting all at once with '\n'.join(out), this is faster than calling print \(N\) times.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    idx = 0
    N = int(tokens[idx]); idx += 1
    M = int(tokens[idx]); idx += 1
    P = [int(tokens[idx + j]) for j in range(M)]
    idx += M
    
    scores = []
    for i in range(N):
        s = tokens[idx]; idx += 1
        total = 0
        for j in range(M):
            if s[j] == 'o':
                total += P[j]
        scores.append(total)
    
    # Count how many students have each score
    from collections import Counter
    cnt = Counter(scores)
    
    # For each unique score, rank = number of students with strictly higher score + 1
    # Sort unique scores in descending order and compute cumulative counts
    sorted_scores = sorted(cnt.keys(), reverse=True)
    rank_map = {}
    cumulative = 0
    for sc in sorted_scores:
        rank_map[sc] = cumulative + 1
        cumulative += cnt[sc]
    
    out = []
    for i in range(N):
        out.append(str(rank_map[scores[i]]))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

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