PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Binary search, Range minimum queries
PROBLEM:
You have two permutations P and Q. For each K = 1, \ldots, N solve the following problem:
- You’re allowed to swap adjacent values in P or in Q.
- Find the minimum number of total swaps such that the following process can potentially result in only K remaining:
- Repeatedly choose the leftmost remaining element in either P or Q, then discard this element from both permutations.
EXPLANATION:
Let’s solve the problem for a fixed value of K first.
Define x_K to be the position of K in P, and y_K to be the position of K in Q.
Observe that if there exists some element M such that x_M \gt x_K and y_M \gt y_K, then it’s definitely not possible for K to be the last remaining element.
This is because neither copy of M can be reached till at least one copy of K is discarded; but if one copy is discarded then both are discarded.
What if there’s no M satisfying this condition?
Then, it’s always possible to make K be the survivor.
The method is simple: first discard all cards that appear before K in P, then discard all cards that appear before K in Q.
Since every element must appear before K in either P or Q by assumption, this removes all other elements and we’re done.
Thus, our goal is to reach a state where every element has at least one copy before K, in either permutation.
Let’s now see what adjacent swaps can get us.
First, observe that every swap we do must include K - if it doesn’t we can just not perform the swap and the relative positions of all elements with respect to K doesn’t change anyway.
Further, if we do swap K, it must be to the right - swapping it leftwards doesn’t help at all.
K starts at position x_K in P.
Suppose we perform swaps and it ends up at position i \ge x_K.
We then only need to ensure that the elements at positions i+1, i+2, \ldots, N of P appear before K in Q.
These elements are initially at positions y_{P_{i+1}}, y_{P_{i+2}}, \ldots, y_{P_N} in Q.
We only need to ensure that we move K enough to go beyond all of them - that is, beyond
Note that if we’re already beyond this maximum, we don’t need any moves - otherwise the number of swaps is the distance between our starting position and this maximum.
The total number of moves needed is hence
For a fixed K, this gives a solution in linear time - simply store the suffix maximums of y_{P_i}, after which fixing an i \ge x_K can be handled in constant time.
The constraints don’t allow for a linear-per-K solution though, so we need to do better.
Let’s examine the expression we wish to minimize:
We split this into two cases based on the maximum.
First, suppose \max(0, \max(y_{P_{i+1}}, y_{P_{i+2}}, \ldots, y_{P_N}) - y_K) = 0.
This means y_K is past that suffix maximum - which can only happen for “large enough” values of i.
For all such i, the cost reduces to just i - x_K, and since x_K is a constant it’s clearly optimal to choose the smallest valid i here.
Finding the smallest valid i such that \max(0, \max(y_{P_{i+1}}, y_{P_{i+2}}, \ldots, y_{P_N}) - y_K) = 0 can be done in logarithmic time by just binary searching on i, as long as suffix maximums are computed beforehand.
Next, we consider the other case: where i is not “large enough”.
In this case, the expression is
Here, -x_K-y_K is a constant that can be taken out, so we only wish to minimize i + \max(y_{P_{i+1}}, y_{P_{i+2}}, \ldots, y_{P_N}) across a certain range of i.
Note that this expression depends purely on i.
So, we can create a new array C_i = i + \max(y_{P_{i+1}}, y_{P_{i+2}}, \ldots, y_{P_N}) and then it turns into a range min query on this array, which can be handled by any appropriate data structure (sparse table/segment tree for example.)
This allows us to solve for any single value of K in logarithmic time so we’re done.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
struct SparseTable{
int n, l;
vector<vector<int>> sp;
inline int combine(int x, int y){
// fill this in
return min(x, y);
}
inline void init(int nn, vector <int> v){
n = nn;
if (v.size() == n){
vector <int> v2;
v2.push_back(0);
for (auto x : v) v2.push_back(x);
v = v2;
}
l = 0;
while ((1 << l) <= n){
l++;
}
sp = vector<vector<int>>(l, vector<int>(n + 1));
for (int i = 1; i <= n; i++){
sp[0][i] = v[i];
}
for (int j = 1; j < l; j++){
for (int i = 1; i <= n; i++){
int who = i + (1 << (j - 1));
if (who <= n)
sp[j][i] = combine(sp[j - 1][i], sp[j - 1][who]);
}
}
}
inline int query(int l, int r){
int i = log2(r - l + 1);
int v = combine(sp[i][l], sp[i][r + 1 - (1 << i)]);
return v;
}
};
void Solve()
{
int n; cin >> n;
vector <int> p(n + 1), q(n + 1), ip(n + 1), iq(n + 1);
for (int i = 1; i <= n; i++){
cin >> p[i];
ip[p[i]] = i;
}
for (int i = 1; i <= n; i++){
cin >> q[i];
iq[q[i]] = i;
}
vector <int> c(n + 1);
for (int i = 1; i <= n; i++){
c[i] = iq[p[i]];
}
for (int i = n - 1; i >= 1; i--){
c[i] = max(c[i], c[i + 1]);
}
vector <int> d(n + 1);
for (int i = 1; i <= n; i++){
d[i] = c[i] + i;
}
SparseTable std;
std.init(n, d);
vector <int> ans(n + 1);
for (int i = n; i >= 1; i--){
int x = p[i];
ans[x] = (n - i);
int lo = i + 1, hi = n + 1;
while (lo != hi){
int mid = (lo + hi) / 2;
if (c[mid] > iq[x]){
lo = mid + 1;
} else {
hi = mid;
}
}
if (lo <= n){
ans[x] = min(ans[x], lo - 1 - ip[x]);
}
// i + 1...lo - 1
if (i + 1 <= lo - 1){
ans[x] = min(ans[x], std.query(i + 1, lo - 1) - 1 - ip[x] - iq[x]);
}
}
for (int i = 1; i <= n; i++){
cout << ans[i] << " \n"[i == n];
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}