PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Segment trees/fenwick trees
PROBLEM:
You have a permutation P.
You can move an element at index i to either the front of P for a cost of i-1, or the back of P for a cost of N-i.
Find the minimum cost to sort P.
EXPLANATION:
After we’ve performed several moves, each element of P has one of three states: it was either moved to the front, moved to the back, or not moved at all.
Importantly, it can be seen that if we ever move an element to the front, then it’s never optimal to later move it to the back - it would’ve instead been not-higher cost to not move it to the front in the first place.
Briefly, this is because moving an element to the front can only reduce the cost of moving some elements to the back - but this saving comes at the cost of moving the chosen element past them in the first place, so just avoiding the first move will put us at neutral.
Let’s now decide which elements must be moved, and which need not be.
All elements moved to the front will end up at, well, the front.
Since we want the final sequence to be sorted, this means the values moved to the front must be 1, 2, \ldots, x for some integer x.
Similar reasoning tells us that the values moved to the back must be y, y+1, \ldots, N for some N.
That leaves x+1, \ldots, y-1 that are not moved at all.
Observe that this can only result in a sorted sequence if these values were already present in this order in P.
Our next task is to decide which values of x and y are optimal.
Suppose we fix a pair (x, y). Let’s try to compute the movement cost for now.
For the elements 1, 2, \ldots, x, it can be seen that the optimal order of moving is just
That is, first move x to the front, then move x-1 to the front, and so on down till 1.
This is because, if our first move is not x (and is, say, some k instead), then whenever we do move x to the front, we’ll have to use another move to move k in front of x anyway.
This cost can be saved by just moving x first; and then apply the same logic to the remaining values.
By the same token, the values moved to the end will be done in the order y, y+1, \ldots, N.
What is the cost of doing this?
To answer that, it’s in fact simpler to look at pairs of elements.
This is because the cost of moving an element in either direction is the number of elements it crosses; so we can instead try to count for each pair of elements the number of times one crosses the other.
So, let’s look at two values i and j, where i \lt j.
We consider two cases.
Case 1: i appears before j in P, i.e. (i, j) forms an inversion.
In this case, for the final array to be sorted we definitely must be either moving i to the front or j to the back (or both.)
So, surely one of these two will cross the other.
However, once the crossing is done, they never need to interact again
So, any inversion gives an overall cost of 1.
Case 2: i appears before j in P.
Here, we must consider further sub-cases.
First, suppose i and j belong to different movement classes (where a class is one of moving front/back/not moving.)
Then, i and j will never need to interact with each other, so their contribution to the overall cost is 0.
That leaves the case of them belonging to the same movement class.
For now, suppose they both need to be moved to the front, i.e. i \lt j \le x.
Here, recall that the optimal strategy was to move larger values first to the front.
So, j will be moved to the front, hence crossing i.
However, eventually i will also be moved to the front, and will need to cross j which is now to its left.
The overall contribution of this pair is hence 2.
The same logic applies to y \le i \lt j, with the cost being 2 again.
Finally, if x \lt i \lt j \lt y, then i and j are both among the elements that don’t move, and so the cost is obviously 0.
So, to summarize, with x and y fixed the total cost is the sum of:
- All inversions in P.
- Twice the number of pairs 1 \le i \lt j \le x such that i appears before j.
- Twice the number of pairs y \le i \lt j \le N such that i appears before j.
We can use this fact to now figure out which x and y are optimal.
First, we will do a little precomputation.
Define pre_x to be the number of pairs 1 \le i \lt j \le x such that i appears before j.
It’s possible to compute all pre_x using a segment tree (or fenwick tree) built on values as follows:
- Sweep over x = 1, 2, \ldots, N in order
- Let a be an array, where a_i = 1 if P_i \lt x and a_i = 0 otherwise.
- Then, if x appears at position q_x, the number of elements smaller than x that appear before it is equal toa_1 + a_2 + \ldots + a_{q_x}which is a range sum of the array a.
- This, added to pre_{x-1}, gives the number of pairs we need; since pre_{x-1} takes care of all pairs involving both elements strictly smaller than x.
- When moving from x to x+1, the only change we need to make is setting a_{p_x} to 1.
- Since we need a data structure that supports point updates and range sums, a simple segment tree/fenwick tree does the job.
Similarly, precompute suf_y as the number of pairs y \le i \lt j \le N such that i appears before j.
This is done in the exact same way as pref_x, just by iterating in reverse instead.
With this done, let’s fix a value of x and try to figure out what the optimal choice of y should be.
Since x is fixed, we have a constant cost of 2\cdot pre_x associated to it.
We also also have a global cost of the inversion count, which is always present (observe that this doesn’t need to be separately computed, and just equals N\cdot (N-1)/2 - pre_N instead.)
This means the choice of y will only add suf_y to the cost.
Clearly, this means y should be chosen as large as possible.
The only thing limiting our choice of y is that the values x+1, \ldots, y-1 must all appear in sequence in P.
To find this quickly, we can precompute the longest increasing subsequence of continuous values for each element, and then look that up to find the optimal choice of y with x fixed.
(Alternately, you don’t even need precomputation for this part - you can do a two-pointer like algorithm, as long as you’re careful not to accidentally let it degenerate to quadratic.)
This allows us to solve for a single x in constant time, and so we can just try all x and take the best one.
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());
template<class T, T unit = T()>
struct SegTree {
T f(T a, T b) { return a+b; }
vector<T> s; int n;
SegTree(int _n = 0, T def = unit) : s(2*_n, def), n(_n) {}
void update(int pos, T val) {
for (s[pos += n] = val; pos /= 2;)
s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
}
T query(int b, int e) {
T ra = unit, rb = unit;
for (b += n, e += n; b < e; b /= 2, e /= 2) {
if (b % 2) ra = f(ra, s[b++]);
if (e % 2) rb = f(s[--e], rb);
}
return f(ra, rb);
}
};
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector p(n, 0);
for (int &x : p) cin >> x;
vector pos(n+1, 0);
for (int i = 0; i < n; ++i) pos[p[i]] = i;
vector<ll> pref(n+1, 0), suf(n+2, 0);
SegTree<int> seg(n);
for (int i = 1; i <= n; ++i) {
pref[i] = pref[i-1] + seg.query(0, pos[i]);
seg.update(pos[i], 1);
}
seg = SegTree<int>(n);
for (int i = n; i >= 1; --i) {
suf[i] = suf[i+1] + seg.query(pos[i], n);
seg.update(pos[i], 1);
}
vector<int> best(n+1, n);
for (int i = n-1; i >= 1; --i) {
if (pos[i] < pos[i+1]) best[i] = best[i+1];
else best[i] = i;
}
ll ans = 1e18, invs = 1ll*n*(n-1)/2 - pref[n];
for (int i = 1; i <= n; ++i) {
int j = best[i];
ans = min(ans, 2*pref[i-1] + 2*suf[j+1] + invs);
}
cout << ans << '\n';
}
}