PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You’re given a permutation P. You can swap one pair of elements in it.
Maximize the number of sorted subarrays.
EXPLANATION:
In the easy version, N \leq 2000 so \mathcal{O}(N^2) is fast enough - this means if we can perform a swap and compute the number of sorted subarrays in \mathcal{O}(1) time, we can simply try every swap.
This is exactly what we’ll do.
Suppose we swap P_i and P_j.
Notice that only subarrays that contain indices i and/or j can change from sorted to not sorted (or vice versa) - everything else remains the same.
So, rather than directly count the number of sorted subarrays, we’ll instead find the change in the number of sorted subarrays.
To do that, we need to know a few things:
- How many sorted subarrays initially contained indices i and/or j?
- After the swap, how many sorted subarrays contain indices i and/or j?
Let’s focus on a simpler task first: for a fixed index i, how many sorted subarrays contain it?
Observe that any sorted subarray containing i can be broken up into two parts: a sorted subarray ending at i, and another one starting at i.
Conversely, taking any sorted subarray ending at i and any one starting at i and joining them together gives us a valid subarray.
With that in mind, let’s define L_i to be the length of the longest sorted subarray ending at i, and R_i to be the length of the longest sorted subarray starting at i.
These are easy to compute: for instance, L_i = L_{i-1} + 1 if P_i \gt P_{i-1}, and L_i = 1 otherwise. R_i is similar.
The number of sorted subarrays containing i is then exactly L_i\cdot R_i.
Back to the original problem: we want to know how many sorted subarrays contain indices i and/or j, both before and after the swap.
- Before the swap: there are L_i\cdot R_i subarrays containing i, and L_j\cdot R_j subarrays containing j.
However, there could be some sorted subarrays containing both, which are now being counted twice.- A sorted subarray can contain both if and only if i+R_i-1 \geq j, i.e, the longest sorted subarray starting at i includes j.
- If this condition does hold, it’s easy to see that the number of sorted subarrays containing both is L_i \cdot R_j, with the same reasoning we used above.
Subtract this quantity from the total.
- After the swap, the situation is similar.
The number of increasing subarrays containing P_j when it’s in position i is, for the most part, easily found (from L_{i-1} and R_{i+1}); similarly for P_i in position j.
However, you need to take special care when a sorted subarray can contain both indices i and j after the swap.- Whether the latter case happens boils down to a couple of checks: P_j \lt P_{i+1} and P_{j-1} \lt P_i, along with the segment from i+1 to j-1 being increasing (which can be decided looking at R_{i+1}).
Note that the “after swap” counting above might fail when i = j-1 (i.e when dealing with adjacent elements).
However, there are only N-1 such pairs anyway, you can always just manually swap them and compute the answer in linear time instead of having to do excessive casework - the complexity remains the same.
We now have the maximum possible change in the number of sorted subarrays.
To finish, add this change to the initial number of sorted subarrays, which can be found easily in a number of ways (perhaps the simplest, with the information we already have, is to just sum up all the L_i values).
TIME COMPLEXITY:
\mathcal{O}(N^2) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #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<int> p(n+2);
for (int i = 1; i <= n; ++i) {
cin >> p[i];
}
p[0] = n+1;
vector<int> lt(n+2, 1), rt(n+2, 1);
lt[0] = rt[n+1] = lt[n+1] = rt[0];
for (int i = 2; i <= n; ++i) {
if (p[i] > p[i-1]) lt[i] += lt[i-1];
}
for (int i = n-1; i >= 1; --i) {
if (p[i] < p[i+1]) rt[i] += rt[i+1];
}
auto getct = [&] (int i, int x) {
// Place x at position i
if (x < min(p[i-1], p[i+1])) return 1ll + rt[i+1];
if (x > max(p[i-1], p[i+1])) return 1ll + lt[i-1];
if (p[i-1] < p[i+1]) return 1ll*(lt[i-1] + 1)*(rt[i+1] + 1);
return 1ll;
};
auto solve_oneswap = [&] (int i, int j) {
// Subtract existing count from i and/or j
ll res = -1ll*lt[i]*rt[i] - 1ll*lt[j]*rt[j];
if (i+rt[i] > j) res += 1ll*lt[i]*rt[j];
if (p[j] < p[i+1] and p[j-1] < p[i] and rt[i+1]+i+1 >= j) {
// [i...j] is sorted now
int L = i, R = j;
if (p[j] > p[i-1]) L = i - lt[i-1];
if (p[i] < p[j+1]) R = j + rt[j+1];
res += 1ll*(i-L+1)*(R-i+1);
res += 1ll*(R-j+1)*(j-i);
}
else {
// no interaction
res += getct(i, p[j]) + getct(j, p[i]);
}
return res;
};
ll ans = 0, add = 0;
for (int i = 1; i <= n; ++i)
ans += lt[i];
for (int i = 1; i <= n; ++i)
for (int j = i+2; j <= n; ++j)
add = max(add, solve_oneswap(i, j));
ans += add;
// Adjacent swaps separately
for (int i = 1; i < n; ++i) {
swap(p[i], p[i+1]);
ll cur = 1;
for (int j = 2; j <= n; ++j) {
lt[j] = 1;
if (p[j] > p[j-1]) lt[j] += lt[j-1];
cur += lt[j];
}
ans = max(ans, cur);
swap(p[i], p[i+1]);
}
cout << ans << '\n';
}
}
