Overview

This problem asks us to find the number of songs that all \(N\) members have commonly selected. We count how many people selected each song, and count the songs that were selected by all \(N\) members.

Analysis

Key Insight

“Songs that everyone commonly selected” means songs that all \(N\) members have chosen. In other words, if a song is selected exactly \(N\) times, then that song has been selected by everyone.

Understanding with a Concrete Example

For example, suppose there are \(N = 3\) members who selected songs as follows: - Member 1: Song 1, Song 2, Song 3 - Member 2: Song 2, Song 3 - Member 3: Song 1, Song 2, Song 4

Counting how many times each song was selected: - Song 1: 2 times (Members 1, 3) - Song 2: 3 times (Members 1, 2, 3) ← Everyone selected this! - Song 3: 2 times (Members 1, 2) - Song 4: 1 time (Member 3)

Therefore, the song that everyone commonly selected is just “Song 2” — 1 song total.

Comparison with Naive Approach

If we naively check “did everyone select this?” for each song, the time complexity would be \(M\) songs × \(N\) people = \(O(NM)\), requiring up to \(10^{10}\) operations, which could result in TLE.

However, since the total number of selected songs is limited to \(\sum K_i \leq 2 \times 10^5\), we can solve this efficiently by only counting the songs that were actually selected.

Algorithm

1. Prepare a counter (associative array): Use a Counter to record how many times each song was selected.

2. Process all members’ selections: Read the songs each member selected and increment the count for each song by 1.

3. Count songs selected by everyone: Count the number of songs whose counter value equals \(N\). This is the answer.

count[song_number] = number of people who selected that song

Finally, the number of song numbers where count[song_number] == N is the answer.

Complexity

• Time Complexity: \(O(\sum_{i=1}^{N} K_i)\)

  • We perform counting operations proportional to the total number of songs selected by all members
  • Since \(\sum K_i \leq 2 \times 10^5\) by the constraints, this is sufficiently fast

• Space Complexity: \(O(M)\)

  • We may need to store counts for up to \(M\) different songs
  • However, in practice we only need space for the number of distinct songs that were selected

Implementation Notes

1. Pay attention to input format: The first number \(K_i\) on each line is the number of songs, not a song number. Use line[1:] to get the list of song numbers.

2. Using Counter: Python’s collections.Counter makes it easy to count the occurrences of elements.

3. Final counting: Get the number of times each song was selected using count.values(), and count how many values equal \(N\). Songs satisfying the condition c == N are “songs that everyone selected”.

Source Code

from collections import Counter

N, M = map(int, input().split())
count = Counter()

for _ in range(N):
    line = list(map(int, input().split()))
    K = line[0]
    songs = line[1:K+1]
    for song in songs:
        count[song] += 1

# Count the number of songs selected by all N members
result = sum(1 for c in count.values() if c == N)
print(result)

---

This editorial was generated by claude4.5opus.