Overview

When each student gives a present to exactly one person, find the number of students who did not receive any presents.

Analysis

In this problem, we are given \(T_i\), the person to whom student \(i\) gives a present, and we need to determine the reverse: “who received a present from someone.”

In other words, for each student \(j\), we count the number of \(i\) such that \(T_i = j\). If that count is \(0\), then student \(j\) did not receive any presents.

A naive approach would be, for each student \(j\), to scan through all \(T_i\) values to check whether \(T_i = j\). However, in the worst case this requires \(N \times N = (2 \times 10^5)^2 = 4 \times 10^{10}\) comparisons, which would exceed the time limit (TLE).

Instead, by precomputing how many times each student number appears in the given array \(T\), we can efficiently determine how many presents each student received. This can be easily achieved using Python’s collections.Counter.

Algorithm

1. Read the list \(T\) of recipients to whom each student gives a present.
2. Use Counter to count how many times each student number appears in \(T\).
3. Count the number of students whose appearance count is \(0\) (i.e., who received no presents from anyone).
4. Output that count.

For example, given the following input:

4
2 3 4 2

This means student 1 → 2, 2 → 3, 3 → 4, 4 → 2 give presents.

In this case: - Student 1: Received from nobody (appearance count 0) - Student 2: Received from students 1 and 4 (appearance count 2) - Student 3: Received from student 2 (appearance count 1) - Student 4: Received from student 3 (appearance count 1)

Therefore, only student 1 did not receive a present, and the answer is \(1\).

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• By using Counter, we can efficiently count the number of occurrences of each element.
• Note that indices start from 1 (student numbers range from 1 to \(N\)).
• Using fast I/O (sys.stdin.read) allows handling large inputs efficiently.

## Source Code

```python
import sys
from collections import Counter

def main():
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    T = list(map(int, data[1:]))

    count = Counter(T)
    ans = 0
    for i in range(1, N + 1):
        if count[i] == 0:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.