PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Counting inversions, sorting
PROBLEM:
You’re given a 2\times N grid, with both rows being permutations of [1, N].
You’re allowed to swap adjacent elements within the first row.
Find the minimum number of adjacent swaps needed to allow for the following:
- It’s possible to start at (1, 1) and reach (2, N), while always moving a cell with value x to an adjacent cell with value either x or x+1.
EXPLANATION:
Let P denote the permutation of the first row, and Q denote the second row.
Each movement must either keep the current value the same, or increase it by 1.
However, since each row is a permutation, making a move within a row (left/right) must result in a change of value.
We start in the first column and need to reach the last; so any path we take will surely need at least N-1 rightward moves - meaning our value will increase N-1 times at least.
Since all values are in [1, N], this means the only possible way this can happen is if:
- We start with value 1 at (1, 1) and end with value N at (2, N)
- Each rightward move increases value by 1 (and there cannot be any leftward moves.)
- Each up/down move within a column does not change the value.
In particular, observe that if Q_N \ne N then no solution exists, so we output -1.
As long as Q_N = N a solution always exists since we can rearrange P to become [1, 2, \ldots, N].
Thus, for the Q_N = N case we only need to focus on the minimum swaps needed.
From the above properties, observe that we must be standing on value i in the i-th column.
So, if Q_i \ne i holds, we’re forced to have P_i = i.
Further, observe that this also forces P_{i-1} = i-1 and P_{i+1} = i+1 to hold, since that’s the only way we can “enter/exit” the i-th column.
And of course, P_1 = 1 is also forced, since we must start with the value 1 as noted above.
These “forced” conditions are also sufficient.
That is, if we have:
- P_1 = 1
- Q_N = N
- P_{i-1} = i-1, P_i = i, P_{i+1} = i+1 for every i such that Q_i \ne i
then there will always exist a valid path from (1, 1) to (2, N).
Proof
We start at column 1, at position (1, 1) with value 1.
First, suppose there exists a column i \gt 1 such that P_i = i.
If there are multiple, choose the leftmost such i.Observe then that, because P_j \ne j for 1 \lt j \lt i, we must have Q_j = j for each 1 \le j \le i as well as per our assumptions about what happens when Q_j \ne j.
This allows us to take the path(1, 1) \to (2, 1) \to (2, 2) \to (2, 3) \to\ldots\to (2, i) \to (1, i)To reach the i-th column and remain in the first row.
If i = N then we can also just stop at (2, N) and reach our goal.(The one exception is when i = 2, in which case there’s no condition on Q_1 or Q_2; but that’s fine since we just move (1, 1) \to (1, 2) directly.)
Next, consider the case where there’s no i \gt 1 satisfying P_i = i.
In this case, the same argument proves that Q_j = j must hold for all j, so we can just follow (1, 1) \to (2, 1) \to (2, 2) \to\ldots\to (2, N) and reach the goal directly.Now, by simply repeating the first case over and over again, we are able to always move right between columns that have P_i = i till we reach the last such column; after which applying the second case allows us to reach the goal, as claimed.
Thus, the problem boils down to computing the minimum number of adjacent swaps in P needed to bring the “forced” values of P to their positions.
Let the forced values in P be i_1, i_2, \ldots, i_K from smallest to largest.
We want each i_j to be brought to position i_j.
Observe that we don’t care about the configuration of non-forced values, so we can basically ignore them entirely.
Or, more precisely, we never need to perform a swap between two non-forced values.
Thus, the optimal final permutation is to place all forced values at their respective columns; and then place all non-forced values from left to right in the remaining columns, without changing their order.
Once we know the optimal final permutation, the number of swaps needed to reach there is easy to find: it’s simply the number of inversions between the initial and final permutation.
That is, if R denotes the optimal final sequence, then the answer equals the number of pairs (x, y) such that:
- x appears before y in P, but
- x appears after y in R.
Counting the number of inversions in a sequence of length N is a classical problem that can be solved in \mathcal{O}(N\log N) in many ways; for example using divide-and-conquer (by slightly modifying mergesort), or using a data structure like a segment tree/fenwick tree.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
template<typename T>
struct fenwick {
int n;
vector<T> tr;
int LOG = 0;
fenwick() {
}
fenwick(int n_) {
n = n_;
tr = vector<T>(n + 1);
while((1<<LOG) <= n) LOG++;
}
int lsb(int x) {
return x & -x;
}
void pupd(int i, T v) {
for(; i <= n; i += lsb(i)){
tr[i] += v;
}
}
T sum(int i) {
T res = 0;
for(; i; i ^= lsb(i)){
res += tr[i];
}
return res;
}
T query(int l, int r) {
if (l > r) return 0;
T res = sum(r) - sum(l - 1);
return res;
}
int lower_bound(T s){
// first pos with sum >= s
if(sum(n) < s) return n+1;
int i = 0;
rev(bit,LOG-1,0){
int j = i+(1<<bit);
if(j > n) conts;
if(tr[j] < s){
s -= tr[j];
i = j;
}
}
return i+1;
}
int upper_bound(T s){
return lower_bound(s+1);
}
};
void solve(int test_case){
ll n;
cin >> n;
vector<ll> a(n+5), b(n+5);
rep1(i, n) cin >> a[i];
rep1(i, n) cin >> b[i];
if(b[n] != n){
cout << -1 << endl;
return;
}
auto get_inversions = [&](vector<ll> v){
ll res = 0;
fenwick<ll> fenw(n+5);
rep1(i,sz(v)-1){
res += fenw.query(v[i]+1,n);
fenw.pupd(v[i],1);
}
return res;
};
auto min_swaps = [&](vector<ll> v1, vector<ll> v2){
vector<ll> p1(n+5), p2(n+5);
ll zeros = 0;
rep1(i,n){
if(!v1[i]){
zeros++;
}
else{
p1[v1[i]] = zeros;
}
}
zeros = 0;
rep1(i,n){
if(!v2[i]){
zeros++;
}
else{
p2[v2[i]] = zeros;
}
}
vector<ll> non_zeros = {0};
rep1(i,n){
if(v1[i]){
non_zeros.pb(v1[i]);
}
}
ll res = get_inversions(non_zeros);
rep1(x,n) res += abs(p1[x]-p2[x]);
return res;
};
vector<pll> segs;
vector<ll> c(n+5);
rep1(i,n){
if(b[i] == i){
if(!segs.empty() and segs.back().ss+1 == i){
segs.back().ss++;
}
else{
segs.pb({i,i});
}
}
else{
c[i] = i;
}
}
for(auto [l,r] : segs){
c[l] = l;
if(r != n) c[r] = r;
}
vector<bool> exist(n+5);
rep1(i,n) exist[c[i]] = 1;
rep1(i,n){
if(!exist[a[i]]){
a[i] = 0;
}
}
ll ans = min_swaps(a,c);
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
cerr << "RUN SUCCESSFUL" << endl;
return 0;
}