DONUTSELL- Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Chef sells N types of donuts. He has A_i of the i-th type of donut.

There are M customers. Customer i wants one of donut type B_i.
How many customers will be unsatisfied?

EXPLANATION:

This is a simple simulation task.

Let \text{ans} denote the number of people who are sad.
Initially, \text{ans} = 0.

For each i from 1 to M,

  • If A_{B_i} = 0, there are no more donuts of type B_i remaining. So, person i will be sad.
    In this case, increment \text{ans} by 1.
  • If instead A_{B_i} \gt 0, then this person will be satisfied.
    Since they take one donut, decrement A_{B_i} by one.

The final value of \text{ans} is the answer.

TIME COMPLEXITY:

\mathcal{O}(N+M) per testcase.

CODE:

Editorialist's code (PyPy3)
for _ in range(int(input())):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    sad = 0
    for x in b:
        if a[x-1] == 0: sad += 1
        else: a[x-1] -= 1
    print(sad)