Overview

This is a problem of counting the number of pairs among \(N\) laboratories that share at least \(K\) common research themes.

Analysis

Understanding the Problem

Each laboratory has multiple research themes (strings), and if the intersection of research themes between two laboratories has at least \(K\) elements, we count them as a “collaboratable” pair.

Thinking with a Concrete Example

For example, consider the following case: - Laboratory 1: {ai, ml, nlp} - Laboratory 2: {ai, ml, cv} - Laboratory 3: {biology, chemistry}

When \(K = 2\): - Common themes between Lab 1 and 2: {ai, ml} → 2 elements ≥ 2 → Collaboration possible - Common themes between Lab 1 and 3: {} → 0 elements < 2 → Collaboration not possible - Common themes between Lab 2 and 3: {} → 0 elements < 2 → Collaboration not possible

The answer is 1.

Approach Consideration

• Exhaustive pair search: The number of combinations choosing 2 from \(N\) laboratories is \(\frac{N(N-1)}{2}\)
• Since \(N \leq 500\), there are at most about \(125,000\) pairs
• We need to check the number of common themes for each pair

Since the constraints are small, checking all pairs naively is fast enough.

Efficient Calculation of Intersection

To find the intersection of two sets, using a set data structure is efficient. In Python, we use the set type and can obtain common elements with the & operator (set intersection).

Algorithm

1. Read input: Store each laboratory’s research themes as a set
2. Search all pairs: Use nested loops to enumerate all laboratory pairs \((i, j)\) where \(i < j\)
3. Calculate number of common themes: Find the intersection with labs[i] & labs[j] and get its size
4. Check condition: If the number of common themes is at least \(K\), increment the counter
5. Output result: Output the final counter value

Complexity

• Time complexity: \(O(N^2 \times M)\)

  • For each of the \(N^2\) pairs, calculate the set intersection
  • Each intersection calculation takes at most \(O(M)\) (where \(M\) is the maximum number of themes per laboratory, at most 50)
  • Approximately \(500^2 \times 50 = 12,500,000\), which is fast enough

• Space complexity: \(O(N \times M)\)

  • Store each laboratory’s themes as a set

Implementation Notes

1. Use sets: Using the & operator on set is faster and more concise than searching for common elements in lists.

2. Avoid duplicate pairs: By using for j in range(i + 1, N), we prevent counting \((i, j)\) and \((j, i)\) as duplicates.

3. Reading input: Note that for each laboratory, we need to read two lines (the number of themes and the actual themes).

# Example of set intersection (common elements)
set1 = {"ai", "ml", "nlp"}
set2 = {"ai", "ml", "cv"}
common = set1 & set2  # {"ai", "ml"}
print(len(common))    # 2

Source Code

def main():
    import sys
    input = sys.stdin.read().split('\n')
    idx = 0
    
    first_line = input[idx].split()
    N = int(first_line[0])
    K = int(first_line[1])
    idx += 1
    
    labs = []
    for i in range(N):
        M = int(input[idx])
        idx += 1
        themes = set(input[idx].split())
        idx += 1
        labs.append(themes)
    
    count = 0
    for i in range(N):
        for j in range(i + 1, N):
            common = len(labs[i] & labs[j])
            if common >= K:
                count += 1
    
    print(count)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.