PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Anton Trygub
Tester: Danny Mittal
Editorialist: Nishank Suresh
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Understanding of permutations, a good eye for constructions
PROBLEM:
You have two permutations P and Q of size N. Find a permutation R of size N such that
- The number of inversions of the permutation \left(P_{R_1}, P_{R_2}, \dots, P_{R_N}\right) equals A
- The number of inversions of the permutation \left(Q_{R_1}, Q_{R_2}, \dots, Q_{R_N}\right) equals B
or say that none exist.
EXPLANATION:
First, it can be observed that independent of the choice of R, the set of pairs of indices splits into two equivalence classes:
- One class where each pair contributes either one inversion to both P\circ R and Q\circ R, or does not contribute to either
- The other class where each pair contributes one inversion to P\circ R and none to Q\circ R, or vice versa
This follows from the fact that R flips the contribution to inversions of P of a pair of indices (i, j) if and only if the contribution to Q of this pair is also flipped (which is really just a fancy way of saying that both P and Q are acted on by the same permutation).
Now, suppose we have x pairs of type 1 (i.e contributes the same to both) and y pairs of type 2.
Just this information is enough to tell us whether an answer exists or not.
Claim: Given A and B, a required permutation R exists if and only if the following conditions are satisfied:
- A+B has the same parity as y
- y\leq A+B\leq 2x+y
- -y\leq A-B\leq y
The remainder of the editorial will prove this by constructing such a permutation R.
A slight transformation
Let us perform the transformation (A, B) \to (A+B, A-B) - this will make some costs a bit easier to work with.
In particular:
- A pair of indices of type 1 now contributes either 0 or 2 to A+B, and 0 to A-B.
- A pair of indices of type 2 now contributes 1 to A+B, and either -1 or 1 to A-B.
Notice that this immediately gives us the bounds from the claim above:
- A+B lies between y and 2x+y, and always has the same parity as y.
- A-B lies between -y and y.
Thus the conditions in the above claim are certainly necessary. It remains to be seen that they are sufficient.
It can also be seen that choosing R such that P ends up being the identity permutation minimizes both A+B and A-B.
Why?
Every type 1 pair is sorted in P, and thus contributes 0 to A+B since it must also be sorted in Q. So, A+B equals exactly the number of type 2 pairs, i.e, y. This is the minimum attainable value.
Every type 2 pair contributes -1 to A-B, and type 1 pairs contribute 0 so A-B equals exactly -y. Again, this is the minimum possible.
A similar analysis tells us that when Q is the identity permutation, A+B is minimum but A-B is maximum.
Now, let P be the identity permutation (and Q transformed appropriately). Consider the following process:
for i from 1 to N:
while the element to the immediate left of i in Q is greater than i:
swap i with the element to its left
Every time this operation performs a swap, A-B increases by exactly 2 because we only swap type 2 pairs.
Why?
This follows from the fact that P was initially sorted and the way our process works.
When we are moving i to the front of Q, note that we never touch indices 1, 2, \dots, i-1, because Q_j = j for those indices.
The nature of our swapping also guarantees that P_i, P_{i+1}, \dots, P_N is sorted, and hence any swap we make turns an inversion into a non-inversion in Q, while turning a non-inversion into an inversion in P - which means we swap a type 2 pair.
Of course, this also means that we don’t swap any type 1 pairs at all - in other words, A+B remains unchanged throughout this process.
So, as long as -y\leq A-B\leq y and A-B has the same parity as y, we will reach a state where A+B = y and A-B is our target value.
Now we do something similar: we perform a sequence of swaps which increases A+B by 2 each time and leaves A-B unchanged.
The idea is as follows:
Iterate i from 1 to N. Let cur_P = P_i, cur_Q = Q_i, cur_{id} = i.
For each j from i-1 to N, if P_j < cur_P and Q_j < cur_Q, swap the pairs (cur_P, cur_Q) with (P_j, Q_j), and set cur_{id} = j (in terms of R, this equates to performing the swap (R_{cur_{id}}, R_j)).
In other words, we just swap the pair (P_i, Q_i) down as much as possible.
Notice that any pair swapped in this process is a type 1 pair which initially contributed 0 to A+B. So, swapping it increases A+B by 2 and does not change -B$.
However, this time we also need to worry about indices between the two we swapped - because if we have i < k < j, swapping i and j also swaps the contribution of the pairs (i, k) and (k, j).
It turns out that the overall contribution of all such flips is 0.
Proof
Suppose we swap i and j, and have j < k < i.
Our process chose j such that it was the closest to i with P_j < P_i and Q_j < Q_i.
Thus, either P_k > P_i or Q_k > Q_i.
- If both P_k > P_i and Q_k > Q_i, we also have P_k > P_j and Q_k > Q_j. Swapping (i, j) doesn’t change the relative comparisons so the number of inversions of both permutations is unchanged.
- If P_k > P_i but Q_k < Q_i, we have P_k > P_j. If Q_k < Q_j, just as above swapping i and j doesn’t change the relative order of elements in both P and Q, so the number of inversions doesn’t change.
What if Q_j < Q_k < Q_i?
In this case, we have Q_j < Q_k and P_j < P_k, but notice such that if such a pair did exist, it would have been swapped at an earlier step of our process.
(Formally, the invariant maintained is that when starting the process at index i, there is no ‘swappable’ pair before i)
This is a contradiction, so such a pair cannot exist.
Thus, the number of inversions of both P and Q does not change, except from the pair (i, j).
Note that the problem is solved now - we modify Q to obtain the correct value of A-B, then modify both permutations to obtain the correct value of A+B.
No special data structure is required to implement this: the constraints are low enough that a straightforward \mathcal{O}(N^2) implementation is fast enough.
TIME COMPLEXITY:
\mathcal{O}(N^2)
CODE:
Setter (C++)
#include <bits/stdc++.h>
using namespace std;
bool check(int X, int Y, int A, int B)
{
if ((B+A+Y)%2) return false;
int X1 = (B+A-Y)/2;
int Y1 = A - X1;
if (X1<0||X1>X) return false;
if (Y1<0||Y1>Y) return false;
return true;
}
void solve()
{
int n, A, B; cin>>n>>A>>B;
vector<pair<pair<int, int>, int>> p(n);
for (int i = 0; i<n; i++)
{
cin>>p[i].first.first; p[i].second = i;
p[i].first.first--;
}
for (int i = 0; i<n; i++)
{
cin>>p[i].first.second;
p[i].first.second--;
}
int X = 0;
int Y = 0;
for (int i = 0; i<n; i++)
for (int j = i+1; j<n; j++)
{
if ((p[i].first.first<p[j].first.first)==(p[i].first.second<p[j].first.second)) X++;
else Y++;
}
if (!check(X, Y, A, B)) {cout<<-1<<endl; return;}
vector<int> same(n), diff(n), P_invs(n), Q_invs(n);
for (int i = 0; i<n; i++)
{
for (int j = 0; j<n; j++) if (i!=j)
{
if ((p[i].first.first<p[j].first.first)==(p[i].first.second<p[j].first.second)) same[i]++;
else diff[i]++;
if (p[i].first.first>p[j].first.first) P_invs[i]++;
if (p[i].first.second>p[j].first.second) Q_invs[i]++;
}
}
for (int iter = 0; iter<n; iter++)
{
int cur = iter;
while (true)
{
if (check(X-same[cur], Y-diff[cur], A-P_invs[cur], B-Q_invs[cur]))
{
X-=same[cur];
Y-=diff[cur];
A-=P_invs[cur];
B-=Q_invs[cur];
for (int i = iter; i<n; i++) if (i!=cur)
{
if ((p[i].first.first<p[cur].first.first)==(p[i].first.second<p[cur].first.second)) same[i]--;
else diff[i]--;
if (p[i].first.first>p[cur].first.first) P_invs[i]--;
if (p[i].first.second>p[cur].first.second) Q_invs[i]--;
}
swap(p[iter], p[cur]);
swap(same[iter], same[cur]);
swap(diff[iter], diff[cur]);
swap(P_invs[iter], P_invs[cur]);
swap(Q_invs[iter], Q_invs[cur]);
break;
}
else cur++;
}
}
for (int i = 0; i<n; i++) cout<<p[i].second+1<<' ';
cout<<endl;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int t; cin>>t;
while (t--) solve();
}
Tester (Kotlin)
import java.io.BufferedInputStream
fun main(omkar: Array<String>) {
val jin = FastScanner()
val out = StringBuilder()
repeat(readLine()!!.toInt()) {
val n = jin.nextInt()
val a = jin.nextInt()
val b = jin.nextInt()
val p = listOf(0) + List(n) { jin.nextInt() }
val q = listOf(0) + List(n) { jin.nextInt() }
val answer = Array(n + 1) { it }
answer.sortBy { p[it] }
var inversionSum = 0
var inversionDiff = 0
for (j in 1..n) {
for (k in j + 1..n) {
if (q[answer[j]] > q[answer[k]]) {
inversionDiff++
inversionSum++
}
}
}
xLoop@for (x in 1..n) {
for (j in n downTo x + 1) {
if (inversionDiff == b - a) {
break@xLoop
}
if (q[answer[j]] == x) {
inversionDiff -= 2
val u = answer[j]
val v = answer[j - 1]
answer[j] = v
answer[j - 1] = u
}
}
}
if (inversionDiff != b - a) {
out.appendln(-1)
return@repeat
}
jLoop@for (j in 1..n) {
var j = j
for (k in j - 1 downTo 1) {
if (inversionSum == a + b) {
break@jLoop
}
if (p[answer[k]] < p[answer[j]] && q[answer[k]] < q[answer[j]]) {
inversionSum += 2
val x = answer[j]
val y = answer[k]
answer[j] = y
answer[k] = x
j = k
}
}
}
if (inversionSum != a + b) {
out.appendln(-1)
return@repeat
}
out.appendln(answer.toList().subList(1, n + 1).joinToString(" "))
}
print(out)
}
class FastScanner {
private val BS = 1 shl 16
private val NC = 0.toChar()
private val buf = ByteArray(BS)
private var bId = 0
private var size = 0
private var c = NC
private var `in`: BufferedInputStream? = null
constructor() {
`in` = BufferedInputStream(System.`in`, BS)
}
private val char: Char
private get() {
while (bId == size) {
size = try {
`in`!!.read(buf)
} catch (e: Exception) {
return NC
}
if (size == -1) return NC
bId = 0
}
return buf[bId++].toChar()
}
fun nextInt(): Int {
var neg = false
if (c == NC) c = char
while (c < '0' || c > '9') {
if (c == '-') neg = true
c = char
}
var res = 0
while (c >= '0' && c <= '9') {
res = (res shl 3) + (res shl 1) + (c - '0')
c = char
}
return if (neg) -res else res
}
}