# DELSORT - Editorial

Tester: Riley Borgard
Editorialist: Aman Dwivedi

Easy-Medium

# PREREQUISITES:

Two Pointers, Binary Search

# PROBLEM:

You are given an array A of length N.

Let F(L,R) be the array you get from A after removing all occurrences of A_L, A_{L+1}, \dots , A_R. In other words, for each value in A between the indices L and R, you delete every occurrence of that value, including occurrences outside the range [L, R].

A pair (L, R) is called good if 1\le L\le R\le N and F(L, R) is sorted in non-decreasing order. In the case that F(L, R) is the empty array, we say it is sorted.

Count the number of good pairs.

# EXPLANATAION:

F(L, R) denotes the subarray whose starting index is L and ending index is R.

Claim: If there exists a subarray A[L, R] which is good then all the subarrays whose starting index is L and the ending index greater than R will also be good subarrays.

Why

If the subarray A[L, R] is good that means removing all the occurrences of all the elements of this subarray from the array A will make the resultant array sorted in non-decreasing order.

Now consider any subarray whose ending index is greater than R and starting index is L then:

The subarray A[L, R] is still part of the new subarray. So deleting all the occurrences of all the elements of the subarray A[L, R] from array A will make the array sorted. Now if we delete any element from the sorted array, the array will remain sorted. How?

Consider any array A such that the array is sorted in non-decreasing order:

A_1<A_2<A_3<A_4<A_5

Let us delete any element from the array say A_3. After deletion of element A_3, the elements A_2 and A_4 of the array becomes adjacent to each other. Since A_4>A_3 and A_3>A_2, it means that A_4>A_2. Hence our resultant array will be:

A_1<A_2<A_4<A_5

which remains sorted.

Hence all the subarray whose ending index is greater than R and starting index is L will be good as they contain the subarray A[L, R] which is sufficient to make the array sorted,

Hence for every index i of an array A we will consider that as the starting index of the subarray and will try to find the minimum ending index e such that the subarray A[i,e] is good.

If we try to find the minimum ending index for every possible starting index naively it will be O(N^2) which is quite slow to pass the constraints. Can we optimize it further?

Claim: If the minimum ending index for i is e, then the ending index of j will be greater than or equal to e such that j>i.

Proof

We will try to prove it by contradiction:

Suppose for index i the minimum ending index is e such that subarray A[i, e] is good. Now we say that for the index i+1, the minimum ending index is e-1. It means that the subarray A[i+1,e-1] is sufficient to make the resultant array sorted in the non-decreasing order.

As the subarray A[i+1,e-1] is part of the subarray A[i,e] which means for the subarray A[i,e] removing all the occurrences of all the elements of A[i+1,e-1] is sufficient to make the array sorted. Hence the minimum ending index for the subarray which starts from index i is e-1 which contadicts our assumption.

Hence If the minimum ending index for i is e, then the ending index of j will be greater than or equal to e such that j>i.

So, we can use the two-pointers approach to find the minimum ending index e for every index i of an array A. Once we know the minimum ending index e for every index i, it’s quite easy to find the total number of the good subarrays.

Rest is the implementation. One of the ways to implement is:

Spoiler

Suppose there are only two numbers x and y in the array such that x<y. If the last occurrence of x is greater than the first occurrence of y in an array, then the array won’t be sorted. Now removing all the occurrence of either x or y will make the array sorted in non-decreasing order.

What if the array contains more than 2 elements. Do we need to compare an element with all the elements of the array? No !! It’s enough to compare it with the next smaller (or next greater) element of the array if it exists. Try to prove why? Hence we will store the count of elements that creates trouble in an array.

Now, let us try to find the minimum ending index e for the subarray with starts at index 1. Initially, our ending index is at position 1, we will keep on deleting all the occurrences of elements present at index e and increment e until there is no trouble in an array. Let x be the deleted index, y and z the next smaller and next greater element of x.

• Trouble reduces by 1 if the last occurrence of y is larger than the first occurrence of x.
• Trouble reduces by 1 if the last occurrence of x is larger than the first occurrence of z
• Trouble increases by 1 if the last occurrence of y is larger than the first occurrence of z since now y and z are adjacents.

We can easily find the next smaller and next larger element of x by performing a binary search.

As soon as our trouble becomes 0, that is the minimum ending index e for index i.

Once all the minimum ending indexes are found for every starting index, we are done.

# TIME COMPLEXITY:

O(N*log(N) per test case

# SOLUTIONS:

Setter
Tester
``````#include <bits/stdc++.h>

#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

const int T = 10'000, N = 200'000;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int te;
cin >> te;
assert(te <= T);
int sumn = 0;
while(te--) {
int n;
cin >> n;
sumn += n;
assert(sumn <= N);
vi a(n);
map<int, int> ma, le, ri;
rep(i, 0, n) {
cin >> a[i];
ma[a[i]]++;
if(!le.count(a[i])) le[a[i]] = i;
ri[a[i]] = i;
}
ll ans = 0;
int j = 0;
int cnt = 0;
auto conflict = [&] (int x, int y) {
assert(x < y);
return ri[x] > le[y];
};
map<int, int> ma2;
set<int> se;
auto add = [&](int x) {
auto it = se.lower_bound(x);
if(it != se.end() && it != se.begin()) {
cnt -= conflict(*prev(it), *it);
}
if(it != se.end()) {
assert(x != *it);
cnt += conflict(x, *it);
}
if(it != se.begin()) cnt += conflict(*prev(it), x);
se.insert(it, x);
};
auto del = [&](int x) {
auto it = se.find(x);
assert(it != se.end());
if(next(it) != se.end()) cnt -= conflict(x, *next(it));
if(it != se.begin()) cnt -= conflict(*prev(it), x);
if(next(it) != se.end() && it != se.begin()) cnt += conflict(*prev(it), *next(it));
se.erase(x);
};
rep(i, 0, n) {
while(j == i || (j < n && cnt > 0)) {
if(ma2[a[j]] == 0) del(a[j]);
ma2[a[j]]++;
j++;
}
if(cnt == 0) ans += n - j + 1;
// erase a[i]
ma2[a[i]]--;
}
cout << ans << '\n';
}
}
``````
Editorialist
``````#include<bits/stdc++.h>
using namespace std;

set <int> s1;
map<int,int> le,ri,co;
int prob;

#define int long long

void remove(int x)
{
if(co[x]==0)
{
auto itr=s1.lower_bound(x);
s1.erase(x);
int l=-1,r=-1;
itr=s1.lower_bound(x);

if(itr!=s1.end())
r=*itr;
if(itr!=s1.begin())
{
itr--;
l=*itr;
}

if(l!=-1 && ri[l]>le[x])
prob-=1;
if(r!=-1 && ri[x]>le[r])
prob-=1;
if(l!=-1 && r!=-1 && ri[l]>le[r])
prob+=1;
}
co[x]++;
}

{
co[x]--;
if(co[x]==0)
{
auto itr=s1.lower_bound(x);
int l=-1,r=-1;

if(itr!=s1.end())
r=*itr;
if(itr!=s1.begin())
{
itr--;
l=*itr;
}

if(l!=-1 && ri[l]>le[x])
prob+=1;
if(r!=-1 && ri[x]>le[r])
prob+=1;
if(l!=-1 && r!=-1 && ri[l]>le[r])
prob-=1;

s1.insert(x);
}
}

void solve()
{
int n;
cin>>n;

int a[n];

s1.clear();
le.clear();
ri.clear();
co.clear();

for(int i=0;i<n;i++)
{
cin>>a[i];
s1.insert(a[i]);
if(!le.count(a[i]))
le[a[i]]=i;
ri[a[i]]=i;
}

int ans=0;

prob=0;

for(auto itr=s1.begin();itr!=s1.end();itr++)
{
if(itr!=s1.begin())
{
auto ptr=--itr;
itr++;
if(ri[*ptr]>le[*itr])
prob++;
}
}

if(prob==0)
{
int temp=n*(n+1);
temp/=2;
cout<<temp<<"\n";
return;
}

int l=0,r=0;

for(int l=0;l<n;l++)
{
while(prob>0 && r<n)
{
remove(a[r]);
r++;
}

if(prob==0)
ans+=(n+1-r);

}

cout<<ans<<"\n";
}

int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);

int t;
cin>>t;

while(t--)
solve();

return 0;
}

``````
6 Likes

Hi, Could anyone please give me a testcase where my code is failing.
https://www.codechef.com/viewsolution/45235450
Sample test cases are passed.

And you can also not think, and maintain a set of all the current elements. And it is easy to check for sorting, you can maintain a Treap sorted by the value of the elements, and by the first occurrence of the element. And if you support its hash, then you can check its sorting by simply comparing the hashes of these two Treaps) With a neat implementation, a pitiful 270 lines are obtained)

True, you still need to check that there are no intersections at the first / last occurrence of elements, but this is easily done using the Segment tree at maximum and + - 1 on the segment

2 Likes

Setter Solution Not visible?

4 Likes

Hey @cherry0697/@anyone,
Can you throw some more light on how we can check if an array is good/sorted using the next smaller element and the next greater element after deleting a particular subarray [l,r]. I got the other observations leading to two pointers but find it difficult to check if the current subarray is good.
Thanks…!

3 Likes

such a bullshit man !! @setter @tester @editorialist, You people have to provide a solution that is readable, this code is not readable and not understandable, if you pretend to provide the solution or explaining the solution, please explain or provide the solution in a way that one can understand !!

very disappointed !!

1 Like

You can read the editorial and implement the solution by yourself. There is no need to look at the solutions.

1 Like

No Sir, no one was trying to explain the solution. I think editorials should contain the observation and their proof. Not explaining the implementation part, although in spoiler I tried to explain implementation too.

Also If I see the solutions of tester and mine are readable too.

Let us consider two values `a` and `b` in an array, where `a < b` and `b` is the next greater element of `a`

We can make the following observations:

• If the array is sorted, then for all possible values of `a` and `b`, `last[a] < first[b]`.
• On the contrary ,if the array is not sorted then there will always exists at least one pair of `a` and `b` where `last[a] > first[b]`. Let us call such pairs of `a` and `b` as bad pairs.

Let `count` be the total number of bad pairs in the array when no element is removed.

After removing elements from the subarray `[l, r]` if the value of `count` becomes `0`, then we can say that the subarray `[l, r]` is good. While removing an element from the array you need to make sure to update the value of `count` as mentioned in the spoiler section above. And removing/addition of elements can be done using two pointer technique.

The above observation along with the others explained in the editorial can help you solve this problem. This took quite a while for me to understand. Hope you find this helpful. My implementation link

2 Likes

What if the array is sorted in decreasing order like 3 2 1 there will be no next greater element. In that case, we will have to use the next smaller element somehow??

In my explanation, `a` and `b` are any two values in the array regardless of their positions. So in your decreasing order example, next greater element of `1` is `2` and next greater element of `2` is `3`.

Wow! Such a cool problem and the observations mentioned in editorial. Thank you this must have a tag of HARD…