2025 February USACO Bronze Problems/Problem 2
Contents
Problem
Problem
You are given an array a of N non-negative integers a_1,a_2,…,a_N (1≤N≤2⋅10^5,0≤a_i≤N). In one operation, you can change any element of a to any non-negative integer.
The mex of an array is the minimum non-negative integer that it does not contain. For each i in the range 0 to N inclusive, compute the minimum number of operations you need in order to make the mex of a equal i.
Input Format
The first line contains N.
The next line contains a_1,a_2,…,a_N.
Output Format
For each i in the range 0 to N, output the minimum number of operations for i on a new line. Note that it is always possible to make the mex of a equal to any i in the range 0 to N.
Sample Input
4 2 2 2 0
Sample Output
1 0 3 1 2
Scoring
Inputs 2-6: N≤10^3
Inputs 7-11: No additional constraints.
Solution
For the mex of a to equal an integer i,
- No element of a must equal i.
- All of 0,1,…,i−1 must appear in a.
So the number of changes we need to make is at least the maximum of the following two quantities:
- the number of elements of a equal to i (since we must change each element to a different value)
- the number of non-negative integers less than i that do not appear in a (for each such integer, we must change an element to equal it).
Conversely, it can be seen that as long as 0≤i≤N, the answer is exactly equal to the maximum of these two quantities. We can show this via the following strategy.
While there are changes left to make, prioritize selecting an element equal to i to change if such an element exists, or else any element other than those less than i that appear exactly once in a. Then prioritize changing it to a non-negative integer less than i that doesn't already appear in a if such an integer exists, or else any integer greater than i. This strategy is guaranteed to decrease both quantities by one if they are positive or leave them at zero otherwise.
To compute the first quantity, we can maintain an array of length N+1 storing the count of each value from 0 to N. To compute the second quantity, we can loop i from 0 up to N and increment it as necessary.
