Overview

This is a problem of counting how many of the \(K\) announced winning numbers are contained among the \(M\) lottery ticket numbers that Takahashi holds.

Analysis

First, let’s consider the simplest approach (brute force). For each lottery ticket, we check the list of winning numbers one by one. In this case, up to \(K\) comparisons are needed per lottery ticket, resulting in an overall time complexity of \(O(K \times M)\). Given the constraints \(K, M \leq 10^5\), the number of computations can reach up to \(10^{10}\), which far exceeds the typical time limit (around 2 seconds), resulting in TLE (Time Limit Exceeded).

To solve this efficiently, we need to quickly determine “whether a given number exists in the list of winning numbers”.

Algorithm

To efficiently determine “whether a given element is contained in a set,” we use a hash set (the set type in Python).

1. Store all winning numbers \(A_1, A_2, \ldots, A_K\) in a hash set.
2. Take each of Takahashi’s lottery tickets \(B_1, B_2, \ldots, B_M\) one by one and check whether its number is contained in the hash set.
3. If it is contained, increment the match count by 1.

Using a hash set allows insertion and lookup operations to be performed in average \(O(1)\) time. This dramatically speeds up processing compared to brute force.

Complexity

• Time complexity: \(O(K + M)\)
  • Adding \(K\) winning numbers to the set takes \(O(K)\), and searching the set for each of the \(M\) lottery tickets takes \(O(M)\), so the overall complexity is \(O(K + M)\).
• Space complexity: \(O(K + M)\)
  • Storing the winning numbers in a set requires \(O(K)\), and if the input is stored as lists, \(O(K + M)\) memory is used.

Implementation Notes

• Fast I/O: Since the total number of inputs (\(K + M\)) can be as large as \(2 \times 10^5\), reading all input at once using sys.stdin.read().split() is faster than calling input() repeatedly, reducing execution time.

• Choice of data type: Although lottery numbers can be as large as \(10^9\), since we only need to check for matches, the numbers can be managed in the set as strings (str) without converting to integers (int), and this will still work correctly. Skipping the conversion can slightly improve execution speed.

  Source Code

import sys

def solve():
    # Read all input tokens from standard input
    data = sys.stdin.read().split()
    if not data:
        return
    
    # K: Number of winning numbers
    # M: Number of Takahashi's tickets
    K = int(data[0])
    M = int(data[1])
    
    # Store winning numbers in a set for O(1) average time complexity lookups
    # Numbers are treated as strings for efficiency, which is safe for integer comparison
    winning_numbers = set(data[2:2+K])
    
    # Takahashi's ticket numbers
    takahashi_tickets = data[2+K:2+K+M]
    
    # Count how many of Takahashi's tickets match the winning numbers
    match_count = 0
    for ticket in takahashi_tickets:
        if ticket in winning_numbers:
            match_count += 1
            
    # Output the result
    print(match_count)

if __name__ == '__main__':
    solve()

---

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