PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You’re given a permutation P of length N.
It’s called K-sortable if it’s possible to add K to some of its elements and obtain a sorted array.
Find the sum of all K such that P is K-sortable.
EXPLANATION:
First, we solve a simpler problem: given K, how do we decide whether P is K-sortable?
That problem can be solved by greedily increasing only the elements that need to be increased, that is:
- For each i from 1 to N-1 in order, if P_i \gt P_{i+1}, increase P_{i+1} by K.
- In the end, check if P is sorted.
Proof
Suppose P is K-sortable, say by operating on indices i_1, i_2, \ldots, i_m, where i_j \lt i_{j+1}.
We’ll perform these operations in order from left to right (since the order they’re performed in doesn’t affect the final result).
Looking at index i_1 before it was operated on:
- If P_{i_1 - 1} \gt P_{i_1}, then our greedy algorithm would’ve increased index i_1.
- Otherwise, increasing P_{i_1} serves no purpose: everything before i_1 is already sorted, everything after i_1 + 1 will become sorted by future moves, and not operating on P_{i_1} will still ensure that it doesn’t exceed P_{i_1 + 1} (no matter whether P_{i+1} is operated on or not).
So, in such a case, we can simply discard the operation on i_1 and the sortedness won’t change.
Repeat this argument for i_2, then i_3, and so on.
The final result is that we end up with exactly the set of moves used by the greedy algorithm, so if it’s possible to sort P, the greedy will find it.
With this in mind, let’s attempt to find how small or large K can be.
First, note that if P_i \gt P_{i+1} for some index i, P_{i+1} must definitely be increased.
Since the final array must be sorted, certainly we must have K\geq P_i - P_{i-1}.
Let L be the maximum across all such differences (or 1 if no such index exists).
That is,
L is then a lower bound for K, i.e, for any K\lt L, P is definitely not K-sortable.
Now, note that when P_i is increased, it might cause P_{i+1} to require an increase, even if P_i \lt P_{i+1} initially.
More generally, consider two indices x and y (x\lt y) such that:
- P_x \gt P_{x+1}
- P_{x+1} \lt P_{x+2} \lt \ldots \lt P_y
- P_y \gt P_{y+1}
That is, the block from index x+1 to y is a maximal increasing block in P.
For such a block,
- P_{x+1} must definitely be increased.
- This might cause some of indices x+2, x+3, \ldots to require an increase too, in a sort of chain reaction.
- P_y definitely cannot be increased: if it is, then even if P_{y+1} is increased the array cannot remain sorted.
So, there must exist some index m (x+1 \leq m \lt y) such that exactly the elements at indices x+1, x+2, \ldots, m are increased, and the rest aren’t.
Note that for the array to be sorted after this, P_m+K \leq P_{m+1} should hold, that is, K \leq P_{m+1} - P_m.
So, let d be the maximum adjacent difference within this block, i.e,
d = \max \{P_{m+1} - P_m : m \lt x \lt y \}
Clearly, if K \gt d then there’s no way to make this block sorted, while if K \leq d it’s always possible (we’ll definitely stop increasing once we reach whichever pair of indices have a difference of d).
This gives us an upper bound on K.
Note that this computation can be done separately for each increasing block in P, and the true upper bound is the minimum of all the d obtained this way.
Let this upper bound be R.
We now have a lower bound L and an upper bound R.
Given how they were obtained, it’s not hard to see that P is K-sortable for every K between L and R.
So, the answer is simply the sum of all the integers between L and R.
Note that if L \gt R, no valid K exists, and the answer is 0.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author'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());
int solve(int n, vector <int> p){
// so there are 3 types of indices
// fixed + prefix max
// prefix max
// otherwise
vector <bool> fx(n, false);
vector <bool> add(n, true);
int mx = -1;
for (int i = 0; i < n; i++){
if (p[i] > mx){
add[p[i]] = false;
if (p[i] == i){
fx[i] = true;
}
mx = p[i];
}
}
vector <int> a(n);
iota(a.begin(), a.end(), 0);
int lk = 0, rk = n;
for (int i = 1; i < n; i++){
if (fx[i]) continue;
if (add[p[i]] != add[p[i - 1]]){
if (add[p[i]] == true){
int mn = p[i - 1] - p[i];
lk = max(lk, mn);
} else {
int mx = p[i] - p[i - 1];
rk = min(rk, mx);
}
} else if (p[i] < p[i - 1]){
return 0;
}
}
if (lk > rk){
return 0;
}
vector <int> prevadd(n, -n);
int last = -n;
for (int i = 0; i < n; i++){
prevadd[i] = last;
if (add[i]){
last = i;
}
}
vector <int> nxadd(n, 2 * n);
last = 2 * n;
for (int i = n - 1; i >= 0; i--){
nxadd[i] = last;
if (!add[i] && !fx[i]){
last = i;
}
}
vector <int> ac(n, n);
last = -n;
for (int i = 0; i < n; i++){
if (fx[i]){
ac[i] = i - prevadd[i] + 1;
if (last != -n){
ac[i] = min(ac[i], max(ac[last], i - last + 1));
}
last = i;
}
}
for (int i = 0; i < n; i++){
if (fx[i]){
int kk = max(ac[i], nxadd[i] - i + 1);
rk = min(rk, kk - 1);
}
}
if (lk > rk) return 0;
int ans = 0;
for (int i = lk; i <= rk; i++){
ans += i;
}
return ans;
}
void Solve()
{
int n; cin >> n;
vector <int> p(n);
for (auto &x : p) cin >> x, x--;
cout << solve(n, p) << "\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;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
#define IGNORE_CR
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
#ifdef IGNORE_CR
if (c == '\r') {
continue;
}
#endif
buffer.push_back((char) c);
}
}
string readOne() {
assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
assert(!isspace(buffer[pos]));
res += buffer[pos];
pos++;
}
return res;
}
string readString(int min_len, int max_len, const string& pattern = "") {
assert(min_len <= max_len);
string res = readOne();
assert(min_len <= (int) res.size());
assert((int) res.size() <= max_len);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int min_val, int max_val) {
assert(min_val <= max_val);
int res = stoi(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
long long readLong(long long min_val, long long max_val) {
assert(min_val <= max_val);
long long res = stoll(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
vector<int> readInts(int size, int min_val, int max_val) {
assert(min_val <= max_val);
vector<int> res(size);
for (int i = 0; i < size; i++) {
res[i] = readInt(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
vector<long long> readLongs(int size, long long min_val, long long max_val) {
assert(min_val <= max_val);
vector<long long> res(size);
for (int i = 0; i < size; i++) {
res[i] = readLong(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
input_checker in;
int tt = in.readInt(1, 5e4);
in.readEoln();
int sn = 0;
while (tt--) {
int n = in.readInt(1, 5e5);
in.readEoln();
sn += n;
auto p = in.readInts(n, 1, n);
in.readEoln();
assert((int) set<int>(p.begin(), p.end()).size() == n);
int low = 0, high = n;
vector<int> t;
for (int i = 1; i < n; i++) {
if (p[i - 1] > p[i]) {
t.emplace_back(i);
}
}
int sz = (int) t.size();
for (int i = 0; i < sz; i++) {
low = max(low, p[t[i] - 1] - p[t[i]]);
if (i + 1 < sz) {
int mx = 0;
for (int j = t[i]; j < t[i + 1]; j++) {
mx = max(mx, p[j + 1] - p[j]);
}
high = min(high, mx);
}
}
long long ans = 0;
for (int k = low; k <= high; k++) {
ans += k;
}
cout << ans << '\n';
}
cerr << sn << endl;
assert(sn <= 5e5);
in.readEof();
return 0;
}
Editorialist's code (Python)
def solve(p):
n = len(p)
lo, hi = 0, n
for i in range(1, n):
if p[i-1] > p[i]:
lo = max(lo, p[i-1] - p[i])
if i+1 < n and p[i] > p[i+1]: return 0
cur = n
for i in range(1, n):
if p[i] > p[i-1]:
cur = max(cur, p[i] - p[i-1])
else:
hi = min(hi, cur)
cur = 0
if lo <= hi: return hi*(hi+1)//2 - lo*(lo-1)//2
return 0
for _ in range(int(input())):
n = int(input())
p = list(map(int, input().split()))
print(solve(p))
