Overview

Given a set of winning numbers and a set of lottery numbers you hold, count how many numbers appear in both sets (i.e., the size of their intersection).

Analysis

The key point is how to efficiently determine “Is a given number included in the winning numbers?”

Naively, for each \(B_j\), searching through the entire winning number list \(A\) from start to end (linear search) would result in: - \(O(K)\) per search - Doing this \(M\) times gives a total of \(O(KM)\)

This requires up to \(10^5 \times 10^5 = 10^{10}\) comparisons, which will not fit within the time limit (causing TLE).

Instead, by storing the winning numbers \(A\) in a set, checking whether an element exists with x in a can be done in average \(O(1)\), allowing us to speed up the entire process.

Example: - Winning numbers \(A = \{3, 10, 20\}\) - Numbers you hold \(B = [1, 3, 20, 7]\)

In this case, 1 in A is false, 3 in A is true, 20 in A is true, 7 in A is false, so 2 tickets are winners.

Algorithm

1. Store the winning numbers \(A_1 \ldots A_K\) in a set (winning number set a).
2. For each number \(B_j\) you hold, check whether B_j in a.
3. Sum up the number of times it was true and output the result.

In Python, the counting can be done as follows: - sum(1 for x in b if x in a)

Complexity

• Time complexity: \(O(K + M)\) (building the set takes \(O(K)\), and each lookup is average \(O(1)\), done \(M\) times)
• Space complexity: \(O(K)\) (storing the winning numbers in a set)

Implementation Notes

• Since the input can have up to about \(2 \times 10^5\) elements, reading all at once with sys.stdin.buffer.read() is faster.

• According to the constraints, \(A_i\) and \(B_j\) are each distinct, so no duplicate handling is needed. However, this solution would work correctly even if duplicates existed (though since we’re counting “number of tickets,” duplicates would be counted accordingly).

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    k, m = data[0], data[1]
    a = set(data[2:2 + k])
    b = data[2 + k:2 + k + m]
    ans = sum(1 for x in b if x in a)
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.