PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
Given an array A with 1 \le A_i \le N, find any permutation P of [1, N] such that P_i + A_i is not divisible by N+1 for every index i.
EXPLANATION:
Note that since 1 \le A_i \le N and 1 \le P_i \le N, we have 1 \le A_i + P_i \le 2N.
In particular, this means that A_i + P_i can be divisible by N+1 if and only if it actually equals N+1, because every larger multiple of N+1 is larger than 2N.
So, our goal is simply to ensure that A_i + P_i \ne N+1 for all i.
A_i is fixed, which means we just need P_i \ne N+1-A_i.
That is, each index has exactly one forbidden value, and 1 \le A_i \le N means this forbidden value lies in [1, N].
We need to use each value from 1 to N in the permutation.
So, if every index has the same forbidden value, no valid permutation can exist.
Note that this is equivalent to all A_i being equal.
We are now left with the case where there are at least two distinct values among the A_i.
In this case, a solution always exists.
One way to construct a solution is as follows.
We start with simply P_i = i for all i.
There are now a few possibilities.
Case 1: P_i \ne N+1-A_i for all i already
In this case, we’ve already found a valid permutation, so we can simply print it as the answer.
Case 2: There are at least two indices i for which P_i = N+1-A_i.
Let these “bad” indices be i_1, i_2, \ldots, i_K where K \ge 2.
Now simply cyclically shift the values at these bad indices, and all of them now don’t contain their forbidden values!
That is, for each 1 \le j \lt K, place the value i_j at position i_{j+1}, and then place value i_K at position i_1.
Case 3: There’s exactly one index i for which P_i = N+1-A_i.
In this case, we can’t really cyclically shift values because there’s only one.
However, recall that there are at least two distinct elements in A.
So, find any index j such that A_i \ne A_j.
Then,
- We know i+A_i = N+1 because index i is bad.
We also know j+A_j \ne N+1 because index j is not bad. - Since i \ne j, we thus certainly have j+A_i \ne N+1.
- Since A_i \ne A_j, we also have i+A_j \ne N+1.
So we can simply set P_i = j and P_j = i, and that gives us a valid permutation!
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
if min(a) == max(a):
print(-1)
continue
p = list(range(1, n+1))
bad = []
for i in range(n):
if a[i] + p[i] == n+1:
bad.append(i)
if len(bad) == 1:
x = bad[0]
for i in range(n):
if a[i]+x+1 == n+1: continue
if a[x]+i+1 == n+1: continue
p[i], p[x] = p[x], p[i]
break
else:
k = len(bad)
for i in range(k):
nxt = (i+1) % k
p[bad[i]] = bad[nxt]+1
for i in range(n):
assert a[i]+p[i] != n+1
print(*p)