Overview

Given \(N\) chefs, select the top \(K\) chefs in order of highest score (breaking ties by smallest index), and determine how many ingredients all \(K\) selected chefs are proficient in.

Approach

This problem can be solved in two main steps:

1. Identify the finalists (top \(K\) chefs) Each chef has a “score” and a “chef number.” Sort the chefs according to the problem’s conditions (descending by score, ascending by number for ties), then select the first \(K\) chefs.

2. Count the common ingredients We need to efficiently determine which ingredients “all members are commonly proficient in.” For every ingredient (from \(1\) to \(M\)), count how many of the \(K\) finalists are proficient in that ingredient. If the count for a particular ingredient is exactly \(K\), then it is an ingredient that “all members are commonly proficient in.”

Algorithm

1. Reading and organizing data Store each chef’s information in a list. To simplify sorting, create tuples of the form (score, -chef_number). *Note: When using Python’s sort(reverse=True), placing the negated chef number as the second element allows both conditions — “descending by score, ascending by number” — to be satisfied simultaneously.

2. Sorting and selection Sort the created list in descending order and extract the first \(K\) chefs.

3. Counting ingredients Prepare an array (bucket) of size \(M+1\). For each of the \(K\) selected chefs, check the ingredients \(T_{i,j}\) they are proficient in, and increment the corresponding index in the array by \(+1\).

4. Aggregation Finally, examine the contents of the array and count the number of elements whose value equals \(K\), then output the result.

Complexity

Let \(N\) be the number of chefs, \(M\) be the number of ingredient types, and \(C_{total}\) be the total number of proficient ingredients across all chefs (\(\sum C_i\)).

• Time complexity: \(O(N \log N + C_{total} + M)\)

  • Sorting the chefs takes \(O(N \log N)\).
  • Counting ingredients requires processing proportional to the number of proficient ingredients of the selected chefs, which is at most \(O(C_{total})\).
  • The final aggregation takes \(O(M)\).
  • Given the constraints (\(N, M \le 10^5, C_{total} \le 2 \times 10^5\)), this complexity comfortably fits within the time limit.

• Space complexity: \(O(N + M + C_{total})\)

  • Required to store the chef information, the ingredient count array, and each chef’s ingredient list.

Implementation Notes

• Handling large input: Since \(N\) and \(M\) can be as large as \(10^5\), in Python it is faster to read all input at once using sys.stdin.read().split() rather than calling input() repeatedly.

• Tiebreaking: When there are multiple sort criteria (score and number), using tuples allows for a concise implementation.

• Counting ingredients: When searching for “common ingredients,” one could take the set intersection, but when the condition is “all \(K\) members” and the number of ingredient types \(M\) is fixed as in this problem, counting with an array (bucket) is very fast and memory-efficient.

  Source Code

import sys

def solve():
    # Read all input data at once for efficiency
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # N: number of chefs, M: number of ingredients, K: number of finalists
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    chef_scores = []
    chef_ingredients = [None] * N
    
    ptr = 3
    for i in range(N):
        # V_i: score of chef i, C_i: number of favorite ingredients
        v = int(input_data[ptr])
        c = int(input_data[ptr + 1])
        # chef_scores: (score, -chef_id, original_index)
        # Using -chef_id because we sort in reverse and want smaller chef_id first for ties.
        chef_scores.append((v, -(i + 1), i))
        # Store references to the ingredient strings as a slice
        chef_ingredients[i] = input_data[ptr + 2 : ptr + 2 + c]
        ptr += 2 + c
        
    # Sort chefs based on score (descending) and chef_id (ascending)
    # The tuple (v, -chef_id) sorted descending achieves this.
    chef_scores.sort(key=lambda x: (x[0], x[1]), reverse=True)
    
    # ingredient_counts[ing] will store how many finalists like ingredient 'ing'
    ingredient_counts = [0] * (M + 1)
    for i in range(K):
        # Get the original index of the finalist from the sorted list
        idx = chef_scores[i][2]
        for ing_str in chef_ingredients[idx]:
            ing = int(ing_str)
            # Increment count for this ingredient
            ingredient_counts[ing] += 1
            
    # Count how many ingredients were liked by all K finalists
    ans = 0
    for count in ingredient_counts:
        if count == K:
            ans += 1
    
    # Output the final count
    sys.stdout.write(str(ans) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.