DIFST - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Sets

PROBLEM:

You’re given a permutation P. You can swap P_i with P_j only if |P_i - P_j| \ge |i-j|.
Find a sequence of at most N swaps that will sort P.

EXPLANATION:

A permutation is sorted if and only if value i appears at position i for each 1 \le i \le N.

We have N elements to place in position and N moves to work with, so a good starting point is to try and place some element x at position x if we can.
If we’re able to manage this with each move, then certainly we’ll end up with a sorted permutation within N moves.

Let’s analyze when this is possible.
Let pos(x) denote the current position of x.
Then, to move x into position, we need to perform the operation using indices x and pos(x).

This is only possible if

|P_x - P_{pos(x)}| \ge |x - pos(x)|

However, observe that P_{pos(x)} = x by definition, so we want |P_x - x| \ge |x - pos(x)|.

Can we always find such an x?
The answer is yes, we can!

To see why, let’s look at the inequality |P_x - x| \ge |x - pos(x)|.
The right side of that inequality is the distance between the current position and the target position of x.
The left side of this inequality is, however, also the distance between the current position and the target position - but for the element P_x instead!
This is because P_x is currently at x and wants to end up at P_x.

With this observation, let’s define d_x = |x - pos(x)| for each value of x.
Note that d_x = 0 if and only if x is in position already; so we can just ignore such x entirely.

Now, considering only those x with d_x \gt 0, we want to find one of them that satisfies

d_{P_x} \ge d_x

This is easy to do - just take whichever x has the smallest value of d_x among all remaining values!

This works because P_x is also surely not in position (since it’s currently at x) and thus d_{P_x} \ge 0, and since x was chosen as the one with smallest d-value, d_{P_x} \ge d_x also holds.

Thus, we can simply repeatedly keep choosing whichever x has the smallest positive value of d_x, and move it into place.
Note that performing a swap affects the d-values of only two elements (and one of them will become 0.)

So, an easy way to implement this is to store a set of pairs (d_x, x), sorted by d_x.
There are only a couple of updates to this set after each swap - a couple of elements will be deleted, and one might be inserted.
For each swap, we only need to know the smallest element of the set.

Something like std::set in C++ or TreeSet in Java handles all these operations in \mathcal{O}(\log N) time each, which is easily fast enough.

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (C++) 
// #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);

    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector p(n+1, 0);
        for (int i = 1; i <= n; ++i) cin >> p[i];

        vector<array<int, 2>> swaps;
        set<array<int, 2>> rem;
        vector<int> d(n+1), pos(n+1);
        for (int i = 1; i <= n; ++i) {
            pos[p[i]] = i;
            d[p[i]] = abs(p[i] - i);
            if (d[p[i]] > 0) rem.insert({d[p[i]], p[i]});
        }

        while (size(rem) > 0) {
            auto [mn, x] = *rem.begin();
            int y = p[x];
            swaps.push_back({x, pos[x]});
            rem.erase({d[x], x});
            rem.erase({d[y], y});
            
            swap(p[x], p[pos[x]]);
            d[y] = abs(y - pos[x]);
            pos[y] = pos[x];
            if (d[y] > 0) rem.insert({d[y], y});
        }

        cout << size(swaps) << '\n';
        for (auto [i, j] : swaps) cout << i << ' ' << j << '\n';
    }
}
1 Like