Overview

We need to find the number of ingredient types that are commonly available to all chefs who remain in the top \(K\) of a cooking contest.

Analysis

In this problem, we first need to determine the top \(K\) chefs. Note that when scores are tied, the chef with the smaller number ranks higher.

Next, we need to find the intersection of the sets of ingredients that each of these chefs specializes in.

A naive approach would be to check, for each ingredient, whether all top \(K\) chefs have that ingredient. However, this requires up to \(M \times K\) comparisons, which is too slow when the constraints are large (e.g., \(M = 10^5\), \(K = 10^5\)).

Instead, by managing each chef’s specialty ingredients as a set, we can efficiently compute the intersection. Python’s set type has built-in functionality for computing the intersection of multiple sets (such as the &= operator), which allows for fast computation.

Algorithm

1. Read all chef information and sort in descending order based on score and chef number (if scores are the same, sort by number in ascending order).
2. Extract the top \(K\) chefs and store each chef’s specialty ingredients as a set.
3. Starting with the ingredient set of the first chef as the base, sequentially compute the intersection with the sets of the remaining \(K - 1\) chefs.
4. Output the number of elements in the final intersection set.

Concrete Example

Sample input:

3 5 2
100 3 1 2 3
100 2 2 3
90 2 3 4

• Chef 1: Score 100, Ingredients {1, 2, 3}
• Chef 2: Score 100, Ingredients {2, 3}
• Chef 3: Score 90, Ingredients {3, 4}

Sorting by descending score and then ascending number: Chef 1 → Chef 2 → Chef 3.

The top \(K = 2\) chefs are Chef 1 and Chef 2.

The common ingredients are {1, 2, 3} ∩ {2, 3} = {2, 3} → The answer is 2.

Complexity

• Time complexity: \(O(N \log N + \sum_{i=1}^{K} C_i) \)
  • \(O(N \log N)\) for sorting, \(O(\sum C_i)\) for set operations
• Space complexity: \(O(\sum_{i=1}^{N} C_i) \)

Implementation Notes

• Since each chef’s ingredient list contains no duplicates, using set allows us to efficiently compute the intersection.

• To correctly handle the ordering when scores are tied, set the sort key as (-score, number).

• sys.stdin.read() is used for fast input processing.

  Source Code

import sys
from collections import defaultdict

input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    
    chefs = []
    
    for i in range(N):
        V = int(data[idx])
        idx += 1
        C = int(data[idx])
        idx += 1
        ingredients = []
        for _ in range(C):
            ingredients.append(int(data[idx]))
            idx += 1
        chefs.append((V, i+1, set(ingredients)))
    
    # 得点が高い順、シェフ番号が小さい順にソート
    chefs.sort(key=lambda x: (-x[0], x[1]))
    
    # 上位K人の食材の集合を取得
    top_k_sets = [chef[2] for chef in chefs[:K]]
    
    # 全ての集合の共通部分を求める
    common = top_k_sets[0]
    for s in top_k_sets[1:]:
        common &= s
    
    print(len(common))

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.