PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Dynamic programming, square root decomposition
PROBLEM:
An array is called good if it can be made sorted by deleting some elements at indices that form an arithmetic progression with common difference \ge 2.
Given an array, count the number of its subarrays that are good.
N \le 2\cdot 10^5
EXPLANATION:
Our solution to the easy version, which had lower constraints, was the following:
- Try all 2 \le d \le N
- For a fixed d, compute using DP the largest valid right endpoint, for each left endpoint.
- This information can then be combined pointwise across all d to find the overall largest valid right endpoint for each left endpoint; which then gives us the count we want.
Now that N is larger, it’s obviously impossible to try all values of d.
To overcome this, we’ll use square root decomposition.
First, for all d \le \sqrt N, run the old DP process directly.
At linear time per d, this takes \mathcal{O}(N\sqrt N) time overall which is fine.
Let’s now analyze which larger values of d can possibly be useful.
For a fixed left endpoint L, let i_1 \ge L be the next index such that A_{i_1} \gt A_{i_1+1}, and i_2 \ge i_1 be the second-next index such that A_{i_2} \gt A_{i_2+1}.
Observe that if i_2 doesn’t exist, then every subarray starting at L has already been accounted for by the “small” values of d, because if deleting one of index i_1 or i_1+1 doesn’t fix the issue then nothing can.
So, we assume that i_2 does exist since those are the only interesting remaining L.
Observe now that any value of d that’s chosen surely has to allow us to cover one of i_1/i_1+1 and one of i_2/i_2+1 to delete them and fix unsortedness.
In particular, if we want to cover i_1 and i_2, then d must divide i_2 - i_1, so only divisors of this difference are valid at all.
However, which divisors do we need to care about? Certainly, trying all of them seems too slow.
To answer that, observe that if some value of d works to make an array good, then any divisor of d will also work for that same array; since going finer can’t hurt us.
Taking this argument to its logical conclusion, only prime values of d really need to be checked at all, since composite d can be replaced by any one of its prime divisors instead.
Now, recall that we already checked for all d \le \sqrt N anyway.
Thus, we only need to care about prime divisors that are \ge \sqrt N.
But, since i_2 - i_1 \le N, there can only be at most one such divisor!
Thus, for a fixed value of L, we obtain at most four distinct additional values of d that need to be checked - one from each way of pairing (i_1, i_1+1) with (i_2, i_2+1).
At first glance, this is still too much - we could have \mathcal{O}(N) distinct values to check, after all.
However, this is not actually the case!
Observe that the values we obtained came from consecutive descents in the array.
Each pair of consecutive descents will give us \mathcal{O}(1) values to check - but these values cannot actually exceed the distance between the descents.
Thus, the sum of values we need to check is bounded by \mathcal{O}(N), since the sum of distances between adjacent descents is bounded by the length of the array.
However, we also restricted ourselves to only checking additional values that are \gt \sqrt N, and so there can’t be more than \mathcal{O}(\sqrt N) of them while also satisfying the sum bound.
So, there are only \mathcal{O}(\sqrt N) additional values of d that need to be checked.
Since each one is checked in linear time, we obtain an algorithm that’s \mathcal{O}(N\sqrt N) overall and hence fast enough.
TIME COMPLEXITY:
\mathcal{O}(N\sqrt 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());
void Solve()
{
int n; cin >> n;
vector <int> a(n + 1);
for (int i = 1; i <= n; i++){
cin >> a[i];
}
if (n == 1){
cout << 1 << "\n";
return;
}
vector<vector<int>> d(n + 1);
vector<bool> pr(n + 1, true);
for (int i = 2; i <= n; i++) if (pr[i]){
for (int j = i; j <= n; j += i){
d[j].push_back(i);
pr[j] = false;
}
}
// if a[j] > a[j + 1], not deleting either j or j + 1 is bad
// if a[j] > a[j + 2], deleting j + 1 is bad
vector <int> ri(n + 1, 1);
vector <bool> interesting(n + 1, false);
vector <int> lst;
interesting[n] = true;
interesting[2] = true;
for (int i = n - 1; i >= 1; i--){
if (a[i] > a[i + 1]){
if (lst.size()){
int sz = lst.size();
int v = lst[sz - 1];
if (v == i + 1 && sz == 1){
} else {
if (v == i + 1) v = lst[sz - 2];
// divisor of (v - i), (v + 1 - i), (v - i - 1)
for (int x : d[v - i]) interesting[x] = true;
for (int x : d[v + 1 - i]) interesting[x] = true;
for (int x : d[v - i - 1]) interesting[x] = true;
}
}
lst.push_back(i);
}
}
for (int d = 2; d <= n; d++) if (interesting[d]){
vector <int> ok(d), tt(d);
int glob = n;
int ti = 1;
vector <int> changes;
auto get = [&](int x){
if (tt[x] == ti){
return ok[x];
}
return glob;
};
auto upd = [&](int x, int v){
if (tt[x] != ti) changes.push_back(x);
ok[x] = v;
tt[x] = ti;
};
for (int i = n; i >= 1; i--){
if (i + 1 <= n && a[i] > a[i + 1]){
int x1 = i % d, x2 = (i + 1) % d;
int v1 = get(x1), v2 = get(x2);
ti++;
glob = i;
changes.clear();
upd(x1, v1);
upd(x2, v2);
}
if (i + 2 <= n && a[i] > a[i + 2]){
upd((i + 1) % d, i + 1);
}
// find max
int mx = -1;
if (changes.size() < d) mx = glob;
for (auto x : changes) mx = max(mx, ok[x]);
ri[i] = max(ri[i], mx);
}
}
int ans = 0;
for (int i = 1; i <= n; i++){
ans += ri[i] - i + 1;
}
cout << ans << "\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;
}