Overview

Given \(N\) laboratories, each with a list of research themes, the problem asks us to find how many pairs of laboratories share at least \(K\) themes in common.

Analysis

To solve this problem, we need to check every possible pair of laboratories and count the number of common themes.

1. Total number of pairs: The number of laboratories \(N\) is at most \(500\). The total number of pairs choosing 2 laboratories is \(\frac{N(N-1)}{2}\), which is \(\frac{500 \times 499}{2} = 124,750\) when \(N=500\). This is small enough that brute-forcing all pairs is more than feasible.

2. Determining common themes: For each pair, we need to efficiently compute “how many themes they share.” A naive comparison between lists can be slow, but by using Python’s set type, we can compute the intersection (common elements) very quickly.

3. Checking the constraints: The number of research themes \(M_i\) per laboratory is at most \(50\), and the length of each theme name is at most \(20\). Even with set comparisons during the brute-force search, the overall computation fits well within the time limit.

Algorithm

1. Read the research themes for each laboratory and store each as a set, keeping them in a list labs.
2. Initialize a variable ans to \(0\) to store the answer.
3. Use a double loop to examine all pairs of laboratories \((i, j)\) where \(0 \leq i < j < N\).
4. For each pair, compute the set intersection (labs[i] & labs[j]) and get the number of elements (len).
5. If the number of elements is at least \(K\), increment ans by \(1\).
6. Output the final value of ans.

Complexity

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

  • \(N\): number of laboratories (at most \(500\))
  • \(M\): maximum number of themes per laboratory (at most \(50\))
  • \(L\): maximum length of a theme name (at most \(20\))
  • Iterating over pairs takes \(O(N^2)\), computing the set intersection takes \(O(M)\), and string hashing/comparison takes \(O(L)\).
  • \(500^2 \times 50 \times 20\) is at most around \(2.5 \times 10^8\) with constant factors, but since set intersection computation is highly optimized in practice, it finishes well within the time limit.

• Space complexity: \(O(N \cdot M \cdot L)\)

  • Space is needed to store all research themes as sets in memory.

Implementation Notes

• sys.stdin.read().split(): When input spans multiple lines, this method retrieves all tokens as a list, making it convenient to process them sequentially using an index.

• Using sets (set): In Python, simply writing set_a & set_b creates a new set containing the common elements. Taking its len() easily gives us the number of common themes.

  Source Code

import sys

def main():
    # 全ての入力を読み込み、空白で分割してリストにする
    data = sys.stdin.read().split()
    if not data:
        return
    
    # 研究室の数 N と閾値 K を取得
    N = int(data[0])
    K = int(data[1])
    
    # 各研究室の研究テーマを集合 (set) として格納するリスト
    labs = []
    idx = 2
    for _ in range(N):
        # 研究テーマの数 M_i を取得
        M_i = int(data[idx])
        idx += 1
        # M_i 個の研究テーマを読み込み、集合に変換
        themes = set(data[idx : idx + M_i])
        labs.append(themes)
        idx += M_i
        
    ans = 0
    # 全ての研究室のペア (i, j) について調査 (i < j)
    for i in range(N):
        for j in range(i + 1, N):
            # 2つの研究室の共通するテーマの数を計算
            # 集合の積演算 (&) を用いて共通要素を抽出し、その要素数を数える
            common_count = len(labs[i] & labs[j])
            
            # 共通するテーマが K 個以上あればカウントを増やす
            if common_count >= K:
                ans += 1
                
    # 結果を出力
    print(ans)

if __name__ == "__main__":
    main()

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