Overview

Given a set of research themes for each of \(N\) laboratories, the problem asks to find the number of pairs of laboratories that share \(K\) or more common themes.

Analysis

In this problem, we need to examine all pairs of laboratories (\(i < j\)), count the number of common research themes for each pair, and determine whether that count is at least \(K\).

A naive approach would be to compare each theme of one laboratory against each theme of the other for every pair, but this is inefficient, requiring \(O(M^2)\) comparisons in the worst case (\(M\) being the number of themes). To efficiently determine theme matches, it is important to use sets rather than lists.

By using sets, we can efficiently extract common elements (intersection) and also avoid worrying about duplicates. In Python, the set type is very convenient, and the set operator & makes it easy to compute the intersection of two sets.

Therefore, an effective approach is to store the themes of each laboratory as a set, examine the size of the intersection for all pairs \((i, j)\) (\(i < j\)), and increment a counter whenever the size is at least \(K\).

Algorithm

1. Read the research themes of each laboratory as a set and store them in a list.
2. Enumerate all pairs of laboratories \((i, j)\) (\(i < j\)).
3. For each pair, compute the intersection of the two theme sets, and increment the counter if the number of elements is at least \(K\).
4. Output the final counter value.

For example, consider the following input:

3 2
2
ai ml
2
ml dl
2
ai dl

In this case: - Laboratory 1: {“ai”, “ml”} - Laboratory 2: {“ml”, “dl”} - Laboratory 3: {“ai”, “dl”}

Pair (1,2): Common themes are {“ml”} → 1 theme (×) Pair (1,3): Common themes are {“ai”} → 1 theme (×) Pair (2,3): Common themes are {“dl”} → 1 theme (×)

Therefore, the answer is 0.

Complexity

• Time complexity: \(O(N^2 \cdot (M_{\max}))\)
  (\(M_{\max}\) is the maximum number of themes per laboratory; this accounts for the time to compute set intersections)
• Space complexity: \(O(N \cdot M_{\max})\)

Implementation Notes

• Managing each laboratory’s themes as a set enables efficient computation of common elements.

• Pair enumeration should be done in the range \(i < j\) to avoid counting duplicates.

• Python’s input().split() converts a space-separated string into a list, which can be conveniently passed directly to set().

  Source Code

N, K = map(int, input().split())

research_labs = []

for _ in range(N):
    M = int(input())
    themes = set(input().split())
    research_labs.append(themes)

count = 0

for i in range(N):
    for j in range(i + 1, N):
        common_themes = research_labs[i] & research_labs[j]
        if len(common_themes) >= K:
            count += 1

print(count)

---

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