cppAcademy
FROM LEARNING TO COMPETING

Real problems.
Your next challenge.

Explore the Group C Olympiad archive.
Choose a topic. Find a challenge. Build your solution.

213 tasks across the Municipal, Regional, and National rounds (2009–2026), plus 4 previously featured problems. 146 tasks have independently written English summaries, analyses, and C++17 solutions; the remaining entries link to Arena. Topic tags are from Arena or our reviewed explanations. Difficulty labels are learning estimates, not official ratings.
GROUP C2012 · MediumSets

Empty Boxes

National Olympiad — Municipal round

Submission name: balls.cpp

Solve in Editor →

Problem summary

Initially n boxes are empty. Each of k records places one ball into its specified box. Find the number still empty.

Input

n k, followed by k box numbers in 1…n.

Output

The empty-box count.

Constraints

1 < n < 1,000,000,000,000; 1 < k < 101.

Worked example

An independently prepared example for this explanation.

Input

8 5
2
4
2
8
4

Output

5

Solution analysis

  1. Store the recorded box numbers in a set.
  2. Subtract the number of distinct occupied boxes from n.

Why it works

A box is nonempty exactly when its number appears at least once. Sets count each such box once.

Complexity: O(k log k) time, O(k) space.

Watch out. n needs a 64-bit integer; do not allocate n entries.

Commented C++17 solution

An independently written complete program with standard headers.

// Key idea: A box is nonempty exactly when its number appears at least once. Sets count each such box
// once.
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
int main(){
    long long n,x;
    int k;
    cin>>n>>k;
    set<long long>used;
    while(k--){
        cin>>x;
        used.insert(x);
    }
    cout<<n-(long long)used.size()<<'\n';
}

Source: Arena Olimpiici ↗