PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: wuhudsm
Testers: IceKnight1093, tabr
Editorialist: IceKnight1093
DIFFICULTY:
3037
PREREQUISITES:
PROBLEM:
Given an array A containing integers from -1 to N-1, find the lexicographically permutation P (or claim that none exist) such that for each 1 \leq i \leq N the following condition is true
- If A_i = -1, no constraint on P_i
- If A_i = 0, then P_i \gt P_j for every 1 \leq j \lt i
- Otherwise, if A_i = k, then k \lt i and k is the largest index such that A_k \gt A_i.
EXPLANATION:
Clearly A_i \lt i must hold for every index, so if this is not the case for some i the answer is immediately -1.
A simpler version
First, let’s try to solve the problem for the case when A doesn’t contain any -1, i.e, there is a constraint on every i. Also, let’s ignore the lexicographic order condition, and just try to find any solution.
Note that A_i = k gives us the following pieces of information:
- P_i \lt P_k \ (if k \gt 0)
- P_i \gt P_j for every k \lt j \lt i
Using this information, let’s construct a directed graph on N vertices. For each constraint we have of the form P_i \lt P_j, add the directed edge i \to j to this graph.
Looking at this graph tells us a few things:
- If there is a path from i to j in the graph, then P_i \lt P_j must hold.
- Extending the above point, if the graph contains any cycles then no valid P can exist, since it would mean P_i \lt P_i for some i
- That means we’re left with a directed acyclic graph, which means it has a topological order, say [u_1, u_2, \ldots, u_N].
- Note that simply assigning P_{u_i} = i gives us a valid permutation!
We now have a solution to the simpler version of the task. There are three issues with it:
- First off, the graph we create can have \mathcal{O}(N^2) edges since each A_i can create \mathcal{O}(N) edges. This is too slow.
- Second, we found some solution, not the lexicographically smallest one
- Third, we need to deal with the existence of -1 in A.
Let’s deal with all three of those separately.
The full solution
Dealing with -1
This is by far the simplest issue to resolve: note that A_i = -1 means this index doesn’t give us a few constraints, so we simply ignore it and move on.
Lexicographic order
Once we create our directed graph, notice that every possible solution corresponds to some topological order of this graph.
In other words, what we want to do is find the lexicographically smallest topological order of the given DAG.
This can be done with a simple extension of one of the standard topological sort algorithms.
One of the ways to compute a topological sort is to compute the indegrees of every node, then keep picking a node with zero indegree and update its neighbors.
When doing this process, simply pick the smallest available vertex at each step: this gives us the lexicographically smallest topological order.
Reducing edges
Creating $\mathcal{O}(N^2) edges is of course going to lead to TLE, so we’d like to reduce their number while ensuring that no information is lost.
Note that each edge we create is one of two types:
- i \to A_i, ‘leftward’ edges
- j \to i where A_i \lt j \lt i, ‘rightward’ edges
The leftward edges are \mathcal{O}(N) in number so we can leave them as is; it’s the rightward ones that there can be many of.
Do we really need all of them? Let’s analyze them a bit.
Suppose we had edges i \to j and i \to k, where i \lt j \lt k. What does this mean?
- We have the constraints P_i \lt P_j and P_j \lt P_k
- However, the only possible way the i \to k edge can exist is if A_k \lt i
- In particular, this means that P_j \lt P_k must also hold, so we’d have the edge j \to k
- Notice that this means that we don’t actually need the i \to k edge: the path i \to j \to k already exists to capture that information.
In other words, we only need at most one rightward edge per index! This reduces the number of edges to \mathcal{O}(N).
Putting everything together for a complete solution, we have the following approach:
- Iterate i from 1 to N. Let S denote the set of indices that don’t have a rightward edge yet.
- If A_i = -1, ignore it
- Otherwise, add the following edges:
- i \to A_i
- j \to i for every j such that j \in S and A_i \lt j \lt i
- For every j \to i edge added, remove j from S
- Insert i into S
- Finally, compute the lexicographically smallest topological sort of the resulting graph to obtain the answer.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Setter's code (C++)
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T,n;
int a[N],ind[N],ans[N];
vector<int> G[N];
int check()
{
for(int i=1;i<=n;i++) if(a[i]>=i) return 1;
return 0;
}
void topo_sort()
{
int cnt=0;
priority_queue<int,vector<int>,greater<int> > Q;
for(int i=1;i<=n;i++) if(!ind[i]) Q.push(i);
while(!Q.empty())
{
int x=Q.top();
Q.pop();
ans[x]=++cnt;
for(int i=0;i<G[x].size();i++)
{
int y=G[x][i];
ind[y]--;
if(y&&(!ind[y])) Q.push(y);
}
}
if(cnt!=n) printf("-1\n");
else for(int i=1;i<=n;i++) printf("%d%c",ans[i],i==n?'\n':' ');
}
void solve()
{
priority_queue<int> Q;
for(int i=1;i<=n;i++) ind[i]=0,G[i].clear();
for(int i=1;i<=n;i++)
{
if(a[i]==-1) continue;
if(a[i])
{
G[i].push_back(a[i]);
ind[a[i]]++;
}
while(!Q.empty())
{
int t=Q.top();
if(t<=a[i]) break;
Q.pop();
G[t].push_back(i);
ind[i]++;
}
Q.push(i);
}
topo_sort();
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
if(check())
{
printf("-1\n");
continue;
}
solve();
}
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
// cerr << res << endl;
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
template<long long mod>
struct modular {
long long value;
modular(long long x = 0) {
value = x % mod;
if (value < 0) value += mod;
}
modular &operator+=(const modular &other) {
if ((value += other.value) >= mod) value -= mod;
return *this;
}
modular &operator-=(const modular &other) {
if ((value -= other.value) < 0) value += mod;
return *this;
}
modular &operator*=(const modular &other) {
value = value * other.value % mod;
return *this;
}
modular &operator/=(const modular &other) {
long long a = 0, b = 1, c = other.value, m = mod;
while (c != 0) {
long long t = m / c;
m -= t * c;
swap(c, m);
a -= t * b;
swap(a, b);
}
a %= mod;
if (a < 0) a += mod;
value = value * a % mod;
return *this;
}
friend modular operator+(const modular &lhs, const modular &rhs) { return modular(lhs) += rhs; }
friend modular operator-(const modular &lhs, const modular &rhs) { return modular(lhs) -= rhs; }
friend modular operator*(const modular &lhs, const modular &rhs) { return modular(lhs) *= rhs; }
friend modular operator/(const modular &lhs, const modular &rhs) { return modular(lhs) /= rhs; }
modular &operator++() { return *this += 1; }
modular &operator--() { return *this -= 1; }
modular operator++(int) {
modular res(*this);
*this += 1;
return res;
}
modular operator--(int) {
modular res(*this);
*this -= 1;
return res;
}
modular operator-() const { return modular(-value); }
bool operator==(const modular &rhs) const { return value == rhs.value; }
bool operator!=(const modular &rhs) const { return value != rhs.value; }
bool operator<(const modular &rhs) const { return value < rhs.value; }
};
template<long long mod>
string to_string(const modular<mod> &x) {
return to_string(x.value);
}
template<long long mod>
ostream &operator<<(ostream &stream, const modular<mod> &x) {
return stream << x.value;
}
template<long long mod>
istream &operator>>(istream &stream, modular<mod> &x) {
stream >> x.value;
x.value %= mod;
if (x.value < 0) x.value += mod;
return stream;
}
constexpr long long mod = 998244353;
using mint = modular<mod>;
mint power(mint a, long long n) {
mint res = 1;
while (n > 0) {
if (n & 1) {
res *= a;
}
a *= a;
n >>= 1;
}
return res;
}
vector<mint> fact(1, 1);
vector<mint> finv(1, 1);
mint C(int n, int k) {
if (n < k || k < 0) {
return mint(0);
}
while ((int) fact.size() < n + 1) {
fact.emplace_back(fact.back() * (int) fact.size());
finv.emplace_back(mint(1) / fact.back());
}
return fact[n] * finv[k] * finv[n - k];
}
struct sparse {
using T = pair<int, int>;
int n;
int h;
vector<vector<T>> table;
T op(T x, T y) {
return min(x, y);
}
sparse(const vector<T> &v) {
n = (int) v.size();
h = 32 - __builtin_clz(n);
table.resize(h);
table[0] = v;
for (int j = 1; j < h; j++) {
table[j].resize(n - (1 << j) + 1);
for (int i = 0; i <= n - (1 << j); i++) {
table[j][i] = op(table[j - 1][i], table[j - 1][i + (1 << (j - 1))]);
}
}
}
T get(int l, int r) {
assert(0 <= l && l < r && r <= n);
int k = 31 - __builtin_clz(r - l);
return op(table[k][l], table[k][r - (1 << k)]);
}
};
int main() {
input_checker in;
int tt = in.readInt(1, 10);
in.readEoln();
int sn = 0;
while (tt--) {
int n = in.readInt(1, 2e5);
in.readEoln();
sn += n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
a[i] = in.readInt(-1, n - 1);
(i == n - 1 ? in.readEoln() : in.readSpace());
}
multiset<int> st;
st.emplace(0);
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && *st.rbegin() > i) {
st.erase(prev(st.end()));
}
if (st.empty()) {
st.emplace(0);
}
if (a[i] == -1) {
a[i] = *st.rbegin();
}
st.emplace(a[i]);
}
vector<int> ans(n);
vector<pair<int, int>> b(n);
for (int i = 0; i < n; i++) {
b[i] = make_pair(a[i], -i);
}
sparse sp(b);
int t = n;
function<void(int, int)> Solve = [&](int low, int high) {
if (low >= high) {
return;
}
auto p = sp.get(low, high);
ans[-p.second] = t--;
// cerr << low << " " << -p.second << " " << high << endl;
if (p.first != low) {
t = -1;
}
Solve(1 - p.second, high);
Solve(low, -p.second);
};
Solve(0, n);
if (t < 0) {
cout << -1 << '\n';
} else {
for (int i = 0; i < n; i++) {
cout << ans[i] << " \n"[i == n - 1];
}
}
}
cerr << sn << endl;
assert(sn <= 2e5);
in.readEof();
return 0;
}
Editorialist's code (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<int> topo_sort(const vector<vector<int>>& gr) {
vector<int> indeg(size(gr)), ret;
for (auto &li : gr) for (auto &x : li) indeg[x]++;
// queue<int> q; // use priority queue for lexic. smallest ans.
priority_queue<int> q;
for (int i = 0; i < (int)size(gr); ++i) if (indeg[i] == 0) q.push(-i);
while (!q.empty()) {
int i = -q.top();
ret.push_back(i);
q.pop();
for (auto &x : gr[i])
if (--indeg[x] == 0) q.push(-x);
}
return ret;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<int> a(n+1);
bool good = true;
vector<vector<int>> g(n+1);
vector<int> active;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
good &= a[i] < i;
if (a[i] != -1) {
if (a[i]) g[i].push_back(a[i]);
while (!active.empty() and active.back() > a[i]) {
g[active.back()].push_back(i);
active.pop_back();
}
}
active.push_back(i);
}
auto ord = topo_sort(g);
if (ord.size() != n+1 or !good) {
cout << -1 << '\n';
continue;
}
vector<int> p(n+1);
int val = 1;
for (int x : ord) {
if (x == 0) continue;
p[x] = val++;
}
for (int i = 1; i <= n; ++i) cout << p[i] << ' ';
cout << '\n';
}
}