DELARRAY - Editorial

PROBLEM LINK:

Div1
Div2
Practice

Setter- Erfan Alimohammadi
Tester- Roman Bilyi
Editorialist- Abhishek Pandey

DIFFICULTY:

EASY

PRE-REQUISITES:

Binary Search, Two Pointers

PROBLEM:

Given an array A of size N, find number of ways to delete a non-empty subarray from it so that the remaining part of A is strictly increasing.

QUICK-EXPLANATION:

Key to AC- Don’t over-complicate the solution. Think in terms of, that, “If I start deleting from index i, then how many ways are possible?”

Maintain 2 arrays, Prefix[i] and Suffix[i] - where Prefix[i] will store true if subarray from [1,i] is strictly increasing, and similarly Suffix[i]=true if the subarray from [i,N] is strictly increasing. Note that, once Prefix[i]=false for any index i, it will remain false for every index after i as well. A vice-versa observation holds for Suffix[] array as well.

Notice that if Prefix[i]=false, then deleting a sub-array starting from index i will not yield a strictly increasing array (as its falsified before this index already). Hence, for every index starting from 1 (1-based indexing), as long as Prefix[i] is true, Binary search for the least index j such that A_j>A_i and array from index j onwards is strictly increasing. (This can be easily achieved by using our Suffix[j] array) . We can now delete N-j+1 subarrays from index (i+1) to index [j-1,N]. Note that, it is implicitly implied that j must be greater than (i+1).

Make sure to account for cases where you might delete an empty subarray (for some test cases) when i=0, or when you are deleting the first element of the array in operation as well.

(Note- I said the range [j-1,N] because you have the option to keep entire range [j,N] as well. In other words, starting from index i, you have to compulsorily delete upto index j-1. Thats the reason for +1 in the expression)

EXPLANATION:

We will first discuss the importance of Prefix[] and Suffix[] array. Once that is done, we will move on to the binary search part, touching upon little implementation details and summarize the editorial. The editorial uses 1-based \ indexing unless explicitly mentioned otherwise.

1. Maintaining the Prefix[] and Suffix[] array-

We define Prefix[i] to be true if the subarray from [1,i] is strictly increasing. Similarly, we maintain another array Suffix[], where Suffix[i] is true if the array from [i,N] is strictly increasing. The first step towards solution is to realize why they are needed in first place - hence give some time thinking of it. In case you are unable to grasp, the solution is below.

If you are still not clear about Role of Prefix & Suffix Arrays here

The rationale behind these two, is that, we only have those many starting positions to consider where Prefix[i]=true. Once Prefix[i] becomes false, it will never be true again because if subarray from [1,i] is not strictly increasing, then the subarray from [1,j] will never be strictly increasing either, for all j > i.

Hence, if we start from an index where Prefix[i]=false, then we cannot make the resulting array strictly increasing no matter what. Hence, starting from index 1, we can go upto only that index i till where Prefix[i] is true.

Similar reasoning holds for Suffix[] array as well. Try to think of it a little, in case you face any issue, the reasoning is there in bonus section. Look at it before proceeding to the next section if the purpose is not clear.

Once you are clear with the idea that what is the need of these arrays, or what do these arrays denote, proceed to the next section to see how they will be used.

2. Binary Searching-

Now, the things to note are that we can perform the operation only once, and the operation must remove a contiguous subarray. Starting from index 1, iterate along all indices i till which Prefix[i]=true. For all such indices, if we can find the index j, such that A_j>A_i and Suffix[j]=true (i.e. the subarray from index [j,N] is strictly increasing), then we are done! That is because, we can then claim that "We get (N-j+1) ways of removing sub-array from range [j-1,N]. Note that it is (j-1) here because A_j>A_i and Suffix[j]=true, which allow the final array formed by elements in range [1,i] \cup [j,N] to be strictly increasing as well! Iterating for all such valid i's will give us the final answer!

Now, the question reduces to, how will we find such a valid index j ? Easy, but perhaps unexpected for some newcomers - Binary Search!

Have a look at your Prefix[] and Suffix[] arrays. Prefix[] is initially true at i=1, and once it becomes false, it remains false till the end. Vice Versa holds for the Suffix[] array. Because of this, we can apply Binary Search on the array!

For Binary Search, we look for 2 things-

  1. Suffix[j] must be true.
  2. A_j must be strictly greater than A_i

The second part is very much valid even if original array A is unsorted (Why?). With this, all that is left is to code our binary search. Setter’s implementation is given below-

Setter's Binary Search
int lo = i + 1, hi = n + 1;
		while (hi - lo > 1){
			int mid = (lo + hi) >> 1;
			if (pd[mid] == 1 and a[mid] > a[i]) //pd = Suffix Array
				hi = mid;
			else
				lo = mid;
		}
		answer += n - lo + 1;

However, one thing is still left!!

Recall our interpretation! For every index i, we are fixing the starting point of the to-be-deleted subarray to (i+1). Got what I am trying to imply? Take it like this - For every index i, finding a j such that the array formed by [1,i] \cup [k,N], where j-1 \leq k \leq N. This means that the deleted sub-array is [i+1,k-1]. Can you think the corner case we are missing here? :thinking:

We are not deleting the first element here!! To account for this, just do another binary search without the A_{mid} > A_i condition, as all elements from index 1 upto index k will be deleted. (Alternate - What if we simply see for upto how many indices the Suffix[i] is 1 ?)

With this done, all that is left is to take care of implementation issues, for instance, if your implementation needs to handle the case of deleting an empty subarray, or getting an empty sub-array &etc.

SOLUTION

Setter
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int maxn = 2e5 + 10;
const int inf = 1e9 + 10;
 
bool dp[maxn], pd[maxn];
int a[maxn], t, n;
 
int main(){
	ios_base::sync_with_stdio (false);
	cin >> t;
	while (t--) {
		cin >> n;
		dp[0] = 1;
		a[0] = -inf;
		for (int i = 1; i <= n; i++){
			cin >> a[i];
			dp[i] = (dp[i - 1] & (a[i] > a[i - 1]));
		}
		pd[n + 1] = 1;
		a[n + 1] = inf;
		for (int i = n; i >= 1; i--)
			pd[i] = (pd[i + 1] & (a[i] < a[i + 1]));
		
		ll answer = 0;
		int lo = 0, hi = n + 1;
		while (hi - lo > 1){
			int mid = (lo + hi) >> 1;
			if (pd[mid])
				hi = mid;
			else
				lo = mid;
		}
		answer = (n - lo);
		for (int i = 1; i <= n - 1; i++){
			if (dp[i] == 0)
				break;
			int lo = i + 1, hi = n + 1;
			while (hi - lo > 1){
				int mid = (lo + hi) >> 1;
				if (pd[mid] == 1 and a[mid] > a[i])
					hi = mid;
				else
					lo = mid;
			}
			answer += n - lo + 1;
		}
		cout << answer - dp[n] << endl;
	}
}
Tester
#include "bits/stdc++.h"
using namespace std;
 
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))
 
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
 
typedef long long Int;
typedef vector<int> VI;
typedef pair<int, int> PII;
 
const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000;
const Int LINF = INF * (Int) INF;
const int MAX = 100007; 
 
const int MOD = 998244353;
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
           
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            assert(cnt>0);
            if(is_neg){
                x= -x;
            }
            assert(l<=x && x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
void assertEof(){
    assert(getchar()==-1);
}
 
int main(int argc, char* argv[])
{
	// freopen("in.txt", "r", stdin);
	//ios::sync_with_stdio(false); cin.tie(0);
    
    int t = readIntLn(1, 10);
    FOR(tt,0,t)
    {
        int n = readIntLn(1, 100000);
        VI A(n);
        FOR(i,0,n)
        {
            if (i + 1 < n)
                A[i] = readIntSp(-INF, INF);
            else
                A[i] = readIntLn(-INF, INF);
        }
        VI X;
        int val = INF + 47;
        X.push_back(val);
        RFOR(i, n, 0)
        {
            if (A[i] >= val) break;
            val = A[i];
            X.push_back(val);
        }
        Int res = min(SZ(X) - 1, n - 1);
        val = -INF - 47;
        FOR(i,0,n)
        {
            if (A[i] <= val) break;
            val = A[i];
            while (SZ(X) && X.back() <= A[i]) X.pop_back();
            res += min(SZ(X), n - 1 - i);
        }
        cout << res << endl;
    }
    assertEof();
 
    cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
    
} 

Time Complexity=O(NLogN) (Binary Search)
Space Complexity=O(N)

CHEF VIJJU’S CORNER :smiley:

Why we need the Suffix array

Similar to the Prefix[] array, the Suffix[] array highlights about number of suitable ending positions we have for sub-array to delete.

Exactly opposite to Prefix[] array, Suffix[] array is initially 0, and once it takes a value of 1, it will always be 1. This is because if the subarray in range [i,N] is strictly increasing, then so is the subarray in range [i+1,N]

If we put the ending point of the to-be-deleted subarray at some point where Suffix[i]=false AND Suffix[i+1] is NOT true, then the resulting subarray cannot be strictly increasing as the array in range [i+1,N] is not strictly increasing.

"Array A is not sorted, then how is Binary search Possible

Simple! Because this condition matters only if Suffix[i] is true! This means that the range the continuously increasing sub-array ending at index N. In other words the sub-array in which we are binary searching is strictly increasing, or sorted. Hence we are able to avoid wrong answer. Remember, we are not binary searching for some value in the entire array - we are binary searching in the sorted part of the array for some value greater than A[i]!

3.This Question is also solvable by using two-pointer technique! Give it a try and share your approach here :slight_smile:

4.What modifications can you think of, if I modify the problem as “the resulting sub-array must be strictly increasing, however, an error of 1 element is allowed”. Meaning, its ok if ignoring/deleting atmost 1 element, the resulting array after the operation becomes strictly increasing. How can we solve this problem?

Setter's Notes

We can solve the problem using Binary Search for appropriate index, or by two-pointers.

Related Problems
  1. Minion Chef and Bananas
  2. A temple of Snakes
13 Likes

O(N) solution
(code is according to 1 indexing 1…N)

left is length of longest prefix strictly increasing sequence
right is index of first element of longest suffix strictly increasing sequence

ans=0
l=left
r=n
while r>=right and l>0:
     if array[l]>=arr[r]:
          l-=1
     else:
          ans+=l
          r-=1

ans+=left#(when removing subsequences which end at N)
ans+=(n-right+1)#(when removing subsequences which start at 1)

One corner case if left==N and right==1 then answer=(n*(n+1))/2-1 using combinatorics.

5 Likes

For more understanding

let a and b be the longest prefix and suffix interesting sequences.

Claim-If ith element of b is greater than 1st,2nd------------jth element of a then:-
(i+1)th element of b is greater than 1st,2nd----------kth element of a where k is greater than or equal to j

so start from last element and go leftwards in both arrays according to greater than or lesser than or equal to operators

1 Like

solution link-https://www.codechef.com/viewsolution/25452707

1 Like

Can you explain your approach when array is [1,2,5,3,4,6,8]? So left is 3 , right is 4 and n is 7. Right? and then after doing dry run on your code, answer comes out to be 7, but should it be 6?
Edited: Ok I got it answer should be 17. but I still don’t get how your above code gives 17 as answer as it never goes else condition in while loop.

here left=4 as length of longest sequence is equal to 4, [3,4,6,8].

left denotes length of longest prefix strictly increasing sequence. And [3,4,6,8] is not a prefix.

I think you haven’t understood the question properly
answer is neither 6 nor 7 answer is 17 and my code is giving 17 only

Your if condition in while loop should have ‘>=’ instead of ‘<=’. That’s where I had problem in doing dry run on your code in comment. I had to verify by looking at your solution in link. And thanks got your approach.

Nice Editorial :1st_place_medal:

1 Like

By mistake.I have edited it now

Can anyone give an hint for the modified question (when error of one element is allowed)?

is such a question present on any online judge.

hint for the bonus
compute the following
left-length of longest increasing prefix array with one error
right-index of first element of longest increasing suffix array with one error

error_pref[i]=number of errors in the subarray till i
error_suff[i]=number of errors in the subarray starting from i till end

1 Like

answer for the bonus
O(N) solution
(code is according to 1 indexing 1…N)

ans=0
l=left
r=n
while r>=right and l>0:
     if array[l]>=arr[r] or error_pref[l]+error_suff[r]>1:
          l-=1
     else:
          ans+=l
          r-=1

ans+=left#(when removing subsequences which end at N)
ans+=(n-right+1)#(when removing subsequences which start at 1)

One corner case if left==N and right==1 then answer=(n*(n+1))/2-1 using combinatorics.

3 Likes

Hey @vijju123 Can you give me the setter notes for EQMD ? Do I need to email you ? Thankyou :slight_smile:

Hi,

Unofficial editorial is ready, and is now pending approval. You can mail me if you want a pdf of it :slight_smile: . I had some personal things to attend to from 31st and 2nd and hence the delay. Sorry.

1 Like

Unofficial ?? Or official ? :thinking:

You put so much effort in editorials…I saw that EQMD editorial as well. You are the world’s best editorialist @vijju123 . Such editorials helps 1000s of people :slight_smile:

2 Likes

Hello guys, Editorial explanation is nice but I am unable to fully understand it. Can you please show me how it is done in this input: 1 1 2

I am guessing prefix array is : T F F
suffix array is : FTT

But what after that and how the output is 4 for this input?