PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: satyam_343
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Sorting
PROBLEM:
You’re given an array A of length N.
Find any permutation P of [0, 1, \ldots, N-1] such that, for each i,
A_i = \text{MEX}(P_1, P_2, \ldots, P_i) or A_i = \text{MEX}(P_i, P_{i+1}, \ldots, P_N).
EXPLANATION:
For convenience, let’s define B_i = \text{MEX}(P_1, \ldots, P_i) to be the prefix MEX array of P, and C_i = \text{MEX}(P_i, \ldots, P_N) to be the suffix MEX array of P.
Our goal is now to find some P for which A_i = B_i or A_i = C_i.
Now, P is a permutation, meaning every element occurs exactly once.
This means that for (almost) every index i, either B_i = 0 or C_i = 0, that is, either the prefix MEX or the suffix MEX will be 0.
This is because either the prefix till i or the suffix starting at i will not contain the single occurrence of 0 in P.
The only exception is the index z for which P_z = 0, for which both B_z and C_z will be \gt 0.
In fact, for this index, similar reasoning shows that one of B_i and C_i must equal 1.
Further, note that B_N = C_1 = N always.
The above observation essentially makes indices i with A_i = 0, “free” indices — as in, we can functionally ignore them, and as long as we ensure that none of these indices contain the element 0 in P they’ll automatically be satisfied.
So, from now on we only need to care about the non-zero elements of P.
First, obviously if every element of A is 0 then no solution can exist, so we only deal with the case where non-zero elements do exist.
Observe that the array B of prefix MEX-es is non-decreasing, while the array C of suffix MEX-es is non-increasing.
So, if we decide to satisfy some non-zero A_i with a prefix MEX, all non-zero values in A after index i must also be satisfied by only prefix MEX-es.
Essentially, some suffix of non-zero elements of A will be satisfied by the prefix MEX-es of P. In particular, these non-zero elements of A must be non-decreasing from left to right.
This leaves the remaining prefix of non-zero elements of A, which must be satisfied by the suffix MEX-es of P. These must be non-increasing from left to right.
So, we want the non-zero elements of A to be first non-increasing, and then non-decreasing after reaching the minimum.
If this isn’t the case, we can immediately say that no solution exists.
Let’s now deal with the case of non-zero elements existing.
We know the non-zero elements first decrease then increase.
So, let mn denote the minimum non-zero element in A, and L denote the leftmost index at which mn appears.
Then, certainly the indices of A which must be prefix MEX-es will be some of the ones that are \geq L (and everything else must be a suffix MEX).
It’s not immediately clear where exactly this prefix/suffix split should be, so let’s work on the other part instead: if we’ve decided on a prefix/suffix split, can we construct a valid solution?
That turns out to be not too hard, in fact.
Once the split has been decided, every non-zero element of A gives us some information.
Specifically, if A_i is to be a prefix maximum, we know that:
- The integers 0, 1, 2, \ldots, A_i - 1 must all appear at indices \leq i
- The integer A_i must appear at an index \gt i.
Essentially, for each integer we obtain either a “this element should appear on a certain prefix” or “this element should appear on a certain suffix” condition.
The same applies to A_i that must be suffix MEX-es too, of course.
Putting all these constraints together, we end up with, for each integer x, a certain range [l_x, r_x] where x is allowed to appear.
Our task is now to basically find a matching between elements and indices, while respecting these intervals.
This is normally a hard problem. However, these ranges are special: because of how they’re obtained, if two of them intersect, one of them will contain the other.
This “laminar” property of the intervals allows for a very simple greedy solution to work.
Specifically, sort all the intervals [l_x, r_x] in ascending order of their length, and then attempt to fill them in that order.
When processing interval [l_x, r_x], place x at any free position within that interval: it doesn’t really matter which one.
This is quite easy to implement in \mathcal{O}(N\log N) time using a set to track empty positions, for instance.
If this greedy algorithm finds a solution, great - otherwise no solution exists.
Note that while doing this, the position of 0 is also restricted to only being at some non-zero element of A, so make sure to account for that properly.
We now know how to check for a single prefix/suffix split in \mathcal{O}(N\log N) time.
However, there are seemingly many splits to check - every non-zero element at an index \geq L is a candidate split, after all.
It turns out that most of them aren’t really relevant at all.
In fact, only two splits are can possibly be valid at all!
One of them is to split at L itself.
The second is to do the opposite: if R is the last occurrence of mn, then split just after R (so that everything till R is a suffix MEX).
Why?
This follows from the observation that either every occurrence of mn should be a prefix MEX, or every one should be a suffix MEX.
To see why: suppose i and j are both occurrences of mn, with i \lt j.
Let’s say we make i a suffix MEX and j a prefix MEX.
This means that all the integers \{0, 1, 2, \ldots, mn-1\} must appear in the range [i, j].Now, look at the integer mn itself.
- If it appears at an index \leq j, the prefix MEX till j will be (at least) mn+1, which is undesirable.
- If it appears at an index \geq i instead, the suffix MEX till i will be (at least) mn+1.
- So, it must be at an index that’s both \lt i and \gt j. But i \lt j, so this is impossible!
This is what gives us the two options: making every mn a prefix MEX is to split at L, and making every mn a suffix MEX is to split just after R.
Check both options in \mathcal{O}(N\log N) each. If either of them works, great; otherwise no solution exists.
mn = N is an edgecase for the above solution, so be careful with that.
Particularly, N can only appear at the endpoints of A; but if it does then it doesn’t actually place any restrictions on the elements’ positions.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
auto solve = [&] (vector<int> a, int pivot) -> vector<int> {
int n = size(a);
vector<array<int, 2>> bound(n+1, {0, n+1});
// Prefix
int pr = 0;
for (int i = pivot; i < n; ++i) {
if (a[i] == 0) continue;
if (a[i] < pr) return {-1};
while (pr < a[i]) {
bound[pr][1] = i;
++pr;
}
bound[pr][0] = i+1;
}
// Suffix
pr = 0;
for (int i = pivot-1; i >= 0; --i) {
if (a[i] == 0) continue;
if (a[i] < pr) return {-1};
while (pr < a[i]) {
bound[pr][0] = max(bound[pr][0], i);
++pr;
}
bound[pr][1] = min(bound[pr][1], i-1);
}
bound[0] = {pivot, pivot};
if (pivot == n or (pivot < n and a[pivot] == 0) or (a[pivot-1] > 0 and a[pivot-1] < a[pivot])) bound[0] = {pivot-1, pivot-1};
vector<array<int, 3>> segs;
for (int i = 0; i < n; ++i) {
if (bound[i][1] < 0 or bound[i][0] >= n or bound[i][0] > bound[i][1]) return {-1};
segs.push_back({bound[i][0], bound[i][1], i});
}
ranges::sort(segs, [] (auto x, auto y) {return x[1] - x[0] < y[1] - y[0];});
set<int> active;
for (int i = 0; i < n; ++i)
active.insert(i);
vector<int> ans(n);
for (auto [l, r, i] : segs) {
auto it = active.lower_bound(l);
if (it == end(active) or *it > r) return {-1};
ans[*it] = i;
active.erase(it);
}
return ans;
};
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector a(n, 0);
for (int &x : a) cin >> x;
if (ranges::max(a) == 0) {
cout << -1 << '\n';
continue;
}
int mn = n;
for (int x : a) if (x > 0)
mn = min(mn, x);
if (mn == n and n > 1) {
if (a[0] == n and a[n-1] == n) a[0] = 0;
}
vector<int> ans;
for (int i = 0; i < n; ++i) {
if (a[i] == mn) {
ans = solve(a, i);
break;
}
}
for (int i = n-1; i >= 0; --i) {
if (a[i] == mn) {
ans = max(ans, solve(a, i+1));
break;
}
}
for (int x : ans) cout << x << ' ';
cout << '\n';
}
}