Overview

Given information about which student each student gives a present to, find the number of students who do not receive any presents.

Analysis

In this problem, we are given information about which student each student gives a present to (directed graph edges). The key observation is that a student who receives a present has at least one present delivered to them. In other words, whether a student receives a present can be determined by checking whether that student is designated by someone.

Specifically, for student \(i\) to receive a present, there must exist at least one student \(j\) such that \(T_j = i\). Conversely, a student who is not designated by any other student will not receive any presents at all.

A naive approach would be to check every student’s designation target for each student, but this would result in \(O(N^2)\) time complexity, which is too slow given the constraint \(N \leq 2 \times 10^5\).

Algorithm

As an efficient solution, consider the following steps: 1. Prepare a boolean array received of size \(N+1\) and initialize all entries to False 2. For each student \(i\), look at their designation target \(T_i\) and set received[T_i] to True - This indicates that student \(T_i\) receives at least one present 3. Finally, scan the received array from student number 1 to N and count the number of students whose value is False - These students are not designated by anyone and therefore do not receive any presents

This algorithm simply scans the input array twice, yet it efficiently solves the problem.

Complexity

• Time complexity: \(O(N)\)
  • Reading input and initializing the array: \(O(N)\)
  • Processing designation targets: \(O(N)\)
  • Counting the result: \(O(N)\)
• Space complexity: \(O(N)\)
  • \(O(N)\) memory used for the received array

Implementation Notes

1. Since array indices are 1-indexed, prepare an array of size \(N+1\) and leave index 0 unused

2. For reading input, using sys.stdin.read() to read all data at once achieves faster processing

3. The boolean array is initialized with [False] * (N+1) to optimize memory efficiency and speed

4. The final answer is obtained simply by counting the number of False entries in the received array

   Source Code

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    T = list(map(int, data[1:]))
    
    received = [False] * (N + 1)
    for t in T:
        received[t] = True
    
    count = 0
    for i in range(1, N + 1):
        if not received[i]:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.