2025 February USACO Bronze Problems/Problem 3
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 T.
The first line of each test case contains two space-separated integers, N and K.
The second line of each test case contains a sequence of N space-separated positive integers, each at most K, which is the sequence that Bessie wants to produce.
Output Format
For each test case, output "YES" or "NO" (case sensitive) on a separate line.
Sample Input
2 1 1 1 4 1 1 1 1 1
Sample Output
YES YES
Scoring
Input 3: K=1
Inputs 4-7: K≤2
Inputs 8-13: No additional constraints.
Solution
Subtask 1: K = 1
When K=1, the answer will always be "YES" since the sequence will contain all 1s due to the constraint that all elements of the sequence have to be at most K.
Subtask 2: K = 2
When K=2, all sequences can be outputted with code that is described by the following format.
REP outer
REP o1
PRINT x
END
REP o2
PRINT y
END
END
One way is to approach this is to store information about blocks of same numbers. For example, [1,1,1,2,2,1,1,1,2,2] can be broken down into the following.
- Three 1s
- Two 2s
- Three 1s
- Two 2s
From here we can see that a sequence can be outputted by the code if both the following is true.
- The number of blocks is even or ≤2.
- Block i is the same as block i+2 for all i.
Subtask 3: K = 3
We can extend the reasoning for K=3. Let a d-degree sequence be some sequence that can be outputted with at most d "REP"s. We can reduce the K=3 problem into the following cases.
Case 1
REP outer
<Program that outputs a degree 1 sequence>
<Program that outputs a degree 2 sequence>
END
Case 2
REP outer
<Program that outputs a degree 2 sequence>
<Program that outputs a degree 1 sequence>
END
The inside of the outer "REP" will make up some repeating block of the sequence. We can iterate over each prefix and check if it is a repeating block. If so, we check whether it can be the output of the body of the outer "REP". This means that we need to check if it is the concatenation of a degree 1 and degree 2 sequence or vice versa.
Checking can be done by iterating over the dividing point of the degree 1 and 2 sequences and seeing if the sequences on the left and right of the dividing point have the desired degrees. We can use our solution from the previous subtask to help us do this.
