Overview

Select the top \(K\) chefs in order of score (breaking ties by smaller index first), and find the number of ingredient types that all \(K\) of them commonly excel at (i.e., the size of the intersection of their sets).

Analysis

First, the “finalists” are uniquely determined as the first \(K\) chefs when sorted in descending order of score \(V_i\), with ties broken by ascending chef index. Therefore, the first task is to identify the top \(K\) chefs.

Next, what we want to find is the intersection of the sets \(S_{i_1}, S_{i_2}, \dots, S_{i_K}\) of the \(K\) finalists: [ |S_{i1} \cap S{i2} \cap \cdots \cap S{i_K}| ]

A naive approach of “for each ingredient \(t\), check whether all top \(K\) chefs have it” would require checking \(K\) chefs per ingredient, resulting in \(O(MK)\), which can be up to \(10^5 \times 10^5\) and is too slow.

The key observation here is that the total number of specialty ingredients across all input is small: [ \sum C_i \le 2\times 10^5 ] In other words, the ingredient information is sparse, so we can process things efficiently by “only counting ingredients that actually appear.”

Specifically, we count the number of occurrences of each ingredient \(t\) among the top \(K\) chefs, and if the count is exactly \(K\), we can determine that “all of them have it.”

Algorithm

1. For each chef \(i\), read their score \(V_i\) and specialty ingredient list \(S_i\).
2. Sort chefs by the key (-V[i], i) (descending score, ascending index) and extract the first \(K\) as finalists.
3. Prepare an array cnt[t], and for each ingredient \(t\) of the finalists, increment cnt[t] += 1 to count occurrences.
4. Scan from \(t=1\) to \(M\), and output the number of ingredients satisfying cnt[t] == K as the answer.

(Example) - If there are \(K=3\) finalists and ingredient 1 appears 3 times, then all 3 chefs excel at ingredient 1 ⇒ count it as a usable ingredient.

Complexity

• Time complexity: Sorting is \(O(N\log N)\), counting is \(O\!\left(\sum_{i\in\text{finalists}} C_i\right)\), and the final scan is \(O(M)\), so the overall complexity is [ O(N\log N + M + \sum_{i\in\text{finalists}} C_i) ]
• Space complexity: The ingredient count array is \(O(M)\), and storing the input totals \(O\!\left(\sum C_i\right)\), so [ O(M + \sum C_i) ]

Implementation Notes

• For tie-breaking, “smaller index ranks higher,” so using the sort key (-V[i], i) handles this correctly.

• Since ingredient indices range from \(1\) to \(M\), using an array of length M+1 makes indexing convenient.

• Since \(\sum C_i\) can be fairly large, in Python using sys.stdin.buffer.readline enables faster input reading.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N, M, K = map(int, input().split())

    V = [0] * N
    ing = [None] * N

    for i in range(N):
        a = list(map(int, input().split()))
        V[i] = a[0]
        C = a[1]
        ing[i] = a[2:] if C else []

    order = list(range(N))
    order.sort(key=lambda i: (-V[i], i))
    finalists = order[:K]

    cnt = [0] * (M + 1)
    for i in finalists:
        for t in ing[i]:
            cnt[t] += 1

    ans = 0
    for t in range(1, M + 1):
        if cnt[t] == K:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.