PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You’re given an array of length 2N.
You can choose a subarray of length N whose mex equals the mex of the remaining elements, and then replace one element inside the subarray and one element outside the subarray by this mex.
Find the maximum number of operations that can be performed - potentially infinitely many.
EXPLANATION:
The key observation needed to solve this problem is: if we can perform at least two operations, then we can perform operations indefinitely.
Proof
Suppose we perform one move with MEX M_1, and then a second move is possible with MEX M_2.
Clearly M_1 \ne M_2 must hold, since the first move introduces M_1 into the array.If M_2 \lt M_1, then the first move must have deleted all occurrences of M_2 from the array - and there must’ve been two occurrences to begin with (one inside, one outside the chosen subarray.)
Also, there are exactly two copies of M_1 in the array.
On our second move, we can simply choose exactly the same subarray (which will both have MEX M_2 now), and overwrite the copies of M_1 with M_2 instead, putting us back at the original array.
This clearly can be repeated infinitely.If M_2 \gt M_1, again we’ll use the fact that there are two copies of M_1 in the array.
By assumption, a second move is possible - and hence, the chosen subarray must have one copy of M_1 inside it and one outside it.
Simply replace both copies with M_2 - and now, just as in the first case, we are able to infinitely cycle between replacing copies of M_1 with M_2 and vice versa.
Thus, there are only three cases: zero, one, or infinitely many operations.
We now need to check for each one.
Checking for zero operations is simple enough: we need to see if an operation can be performed at all.
For this, observe that if we’re able to find a subarray whose mex equals the mex of everything else, then this common mex must also be the mex of the entire array.
So, let’s first compute M = \text{MEX}(A).
Then, simply go over all windows of length N, while maintaining the frequencies of elements [0, M-1] both inside and outside the subarray (along with how many of them have frequency zero.)
These quantities are easy to update when moving the window, since only the frequencies of two elements change.
This gives a simple \mathcal{O}(N) check for this case, though you can also do it in \mathcal{O}(N\log N) using a couple of sets.
Now that (at least) one operation can be performed, we want to know if we can perform a second.
This depends on two things: the chosen subarray, and also which values are to be replaced inside/outside.
First, suppose there’s some element x \lt M = \text{MEX}(A) such that x appears exactly twice in A overall (note that every value \lt M must appear at least twice, now that we’re in this case.)
For such an x, one copy must be within the chosen subarray and one copy must be outside.
We can then choose any valid subarray (which we know exists) and replace both copies of x with M, which will turn the MEX of the new array into x.
Further, doing this allows us to choose the exact same subarray, and replace the two copies of M we wrote with x instead, giving us back the original array.
So, in this case the answer is infinite (i.e. output -1.)
Thus, the only non-trivial case is when all values \lt M appear at least thrice each.
When every element \lt M appears at least thrice, any first move will surely increase the MEX of the whole array.
Otherwise, let M_2 \gt M be the smallest element such that it appears at most two times in A.
After we perform any move, the new MEX will be at least M_2.
So, if M_2 \gt N, then no second move is possible - because if the MEX of the array is \gt N then it’s impossible for any of its subarrays of length N to also have that MEX.
We’re left to deal with M_2 \le M.
Let’s first try to make a “good” move that makes the new MEX exactly M_2.
For this,
- If M_2 doesn’t appear in A at all, it’s always possible to perform an operation that will replace two elements with M, while also ensuring that all elements \lt M_2 appear at least twice each in the array.
- This allows us to choose the same subarray for the second operation and overwrite the copies of M with M_2, so infinite moves are possible.
- If M_2 appears only once in A, it’s again always possible to perform a valid operation: just that one of the elements we overwrite must be the unique copy of M_2 itself.
So, in this case as well, infinite moves are possible. - Finally, we have the case where M_2 appears exactly twice.
Here, it can be verified that a “good” move exists if and only if we can find a subarray of length N such that all of the values \{0, 1, \ldots, M-1, M+1, \ldots, M_2\} appear both inside and outside it.
(This check can be done in linear time in the same way as the initial answer 0 check.)
The “if and only if” part of the last point above is a straightforward proof: if such a subarray exists we can obviously perform a valid move by overwriting both copies of M_2 with M, and conversely if we are able to perform a valid move then both copies of M_2 must be overwritten by M and everything else \lt M_2 must appear in both subarrays (otherwise the move isn’t “good”.)
Finally, what about checking for reaching a MEX that’s \gt M_2?
It turns out we don’t need to consider that at all!
That’s because:
- If M_2 has \le 1 occurrences, we already saw that the answer is already infinite so there’s no point in trying to check higher values.
- If M_2 has two occurrences, then any “good” move that reaches a greater MEX than M_2 must leave one copy of M_2 inside/outside the subarray - but we could just as well have overwritten these copies to get a good move with a MEX of M_2 instead.
TIME COMPLEXITY:
\mathcal{O}(N) or \mathcal{O}(N\log N) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
// find interval
// if there exists c[i] = 2 for smaller than mex, good
// otherwise, need to replace bigger ones only
// lets say, we want mex = p, and we have m right now
// m needs to be inserted twice
// any p need to be deleted
// there should be valid partition with 0....p - 1 in both sides
// => on either side, we should have at least one of each
// find first x such that on one side, it is empty, that is bad, that must be our value
// on other side, it must have at most one occurence only, is this enough?
// or if exactly one on both sides, that works too?
int n; cin >> n;
vector <int> a(2 * n), f(2 * n + 1);
for (int i = 0; i < 2 * n; i++){
cin >> a[i];
f[a[i]]++;
}
int mex = 0;
while (f[mex] > 1) mex++;
if (f[mex] != 0){
cout << 0 << "\n";
return;
}
bool found = false;
vector <int> g(2 * n);
set <int> s1, s2;
// maintain set of max(b1, b2) <= 1
// maintain set of min(b1, b2) == 0
bool found_valid = false;
bool found_inf = false;
auto upd = [&](int x){
int b1 = g[x], b2 = f[x] - g[x];
s1.erase(x);
s2.erase(x);
if (max(b1, b2) <= 1){
s1.insert(x);
}
if (min(b1, b2) == 0){
s2.insert(x);
}
};
auto check = [&](){
int v1 = *s2.begin();
if (v1 < mex){
return;
}
assert(v1 == mex);
v1 = *(++s2.begin());
int v2 = *s1.begin();
if (v2 == mex) v2 = *(++s1.begin());
found_valid = true;
if (v2 <= v1){
found_inf = true;
}
};
for (int i = 0; i <= 2 * n; i++){
upd(i);
}
for (int i = 0; i < n; i++){
g[a[i]]++;
upd(a[i]);
}
check();
for (int i = n; i < 2 * n; i++){
g[a[i]]++;
upd(a[i]);
g[a[i - n]]--;
upd(a[i - n]);
check();
}
if (!found_valid){
cout << 0 << "\n";
} else if (found_inf){
cout << -1 << "\n";
} else {
cout << 1 << "\n";
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}