DELARRAY editorial(unofficial) - LUNCHTIME74

Problem

Statement
Given a sequence of integers, find the number of ways to delete a non-empty subsequence such that the resulting sequence is non-empty and strictly increasing.

Solution

The subarray can be removed in 3 ways to form a strictly increasing sequence:

  1. The subarray to be removed starts from first element

  2. The subarray to be removed ends at last element

  3. The subarray to be removed exist in between first and last element

The first and second subtask can be easily solved using prefix and suffix array.
The challenging part is to solve the 3rd subtask

To solve this part, for each valid index i which forms a strictly increasing sequcence starting from index i to last element, we need to compute the number of subarrays(to the left of index i) which starts from first element and forms a strictly increasing sequence ending with number less than number at index i (make sure this subarray doesn’t covers the whole left subarray).
This can be efficiently calculated using Fenwick Tree.

The sum of 1st, 2nd and 3rd subtask gives us the answer

Taking a example : 1 2 1 3 4

The subarrays possible for 1st subtask are :

  • 1 3 4
  • 3 4
  • 4

For 2nd subtask :

  • 1 2
  • 1

Now for 3rd subtask :

(0-based indexing)

  • No need to check for 0 and 1 index(as we need to remove subarray that exist in between 1st and last element)
  • for index 2 there doesn’t exist any strictly increasing subarray to the left, that ends at a element less than 1
  • for index 3, there are two subarrays to the left of index 3 which are strictly increasing and ends at element less than 3, subarrays [1] and [1 2] -> adds 2 to the answer, resulting sequence can be [1 3 4] and [1 2 3 4]
  • similarly for index 4, there exists two strictly increasing subarrays to the left, [1] and [1 2] - > again adds 2 to the answer, resulting sequence can be [1 4] and [1 2 4].

Hence the answer for this case is 3+2+2+2 = 9

As there can be at most 100000 distinct elements, so the elements can be easily mapped to fit onto Fenwick tree

Time Complexity
O(N*logN)

Click to view code

3 Likes

I don’t think any advanced data-structure like fenwick tree is needed. Simple binary search gives the right answer:- https://www.codechef.com/viewsolution/25464607

5 Likes

Correct, just thought to share a different approach. :slightly_smiling_face:

2 Likes

Nice dp :slight_smile: :slight_smile: :slight_smile: :slight_smile:

532 lines of code :no_mouth:

6 Likes

The best achievable complexity is O(n) not nlogn see my solution-https://www.codechef.com/viewsolution/25452707

2 Likes

O(n) solution::

Solution-DELARRAY

1 Like

Cleanest solution C++ O(N*log(N)) - upper bound: https://pastebin.com/F6nr5eHE

I would always prefer the “Advance data structure” part over writing hundreds of lines of code,
also, you should take some time to appreciate the effort that went into writing this editorial,
even if the “Fenwick tree” part is an overkill, it still would save a lot of time and would be a smarter option.
Also, I got to know another use - case for FW tree.
So, in my opinion, this is by far at par the best solutions out there. :+1:

2 Likes

Hey listen, my code can be written in 70-80 lines…And I took only 5 minutes to write my code…instead of all calling the function…I copy-pasted binary search code again and again. I even had the binary search with me already. It was a 2-5 minutes job for me :slight_smile:

500 lines of code can be written in 2-3 minutes if you have the option to copy-paste😂

This is not the official editorial and I wanted the newbies know that it can be solved with binary search as well. Yup, I’ll make my code short. Appreciating something or not depends on my choice. You can’t dictate my actions. Thankyou.

Why use fenwick trees or even binary search.
When this problem can be solved linearly using some observations-https://www.codechef.com/viewsolution/25452707

1 Like

using a monotonic queue/stack?

2 Likes

Could you explain your solution?

For sure :slight_smile:
You need to remove a contiguous sub-array, now make one observation, suppose you have indeed found the smallest such sub-array and that it starts at left and ends right.
Finding left and right is equivalent to finding the longest strictly sorted prefixes and suffixes respectively.
Now, every other possible sub-arrays that can be deleted will at least start at left(or before it) and end at least right(or after it). More formally let’s denote by start and end the indices/positions where such subarrays can start or end, so, then start <= left and right <= end.
The problem thus boils down to finding all possible pairs of start and end. To find them we can fix a start and find all possible ends for this start. The first end for this start will be the first integer on or after right that is greater than the integer at start, you can simply find this integer using upper_bound/binary search in log(N).
Now, it is also possible that you do not select anything from start at all, you only select everything from right and beyond, that is you only consider suffixes and no element from prefixes.
Note- since you need to delete a non-empty subarray you must choose between the max of start + 2 and right

PS: If you want I can comment my solution and re-post a link.

1 Like

instead of binary search use this.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.

Can you explain your approach?Thanks in advance :slightly_smiling_face:

Ok lets start with an example:

1 2 3 4 4 5 3 6 4 7 8

Steps:

  1. Firstly you have to find out the strictly increasing sequence from the starting point.
    which is 1 2 3 4 4 5 3 6 4 7 8.

Now mark this position as left (here 4th index)(which I did in the code).

  1. Now you can have an observation that we can never include 1 2 3 4 4 5 3 6 4 7 8 in our answer. Why? Because we are restricted to remove the continuous subarray from the given.(You will get a clear indication later)

  2. Observe one thing. Like If you want to keep only first sorted string only what are the posible ways to do so? Following are::

1 2 3 4 4 5 3 6 4 7 8
1 2 3 4 4 5 3 6 4 7 8
1 2 3 4 4 5 3 6 4 7 8
1 2 3 4 4 5 3 6 4 7 8

(Remove the BOLD numbers).

  1. Now starting from the last position move towards the index left (which is 4 in this case).

    a. Here also we only need to take care of strictly decreasing sequence. Whenever this condition violates we just BREAK UP.(See my code at this line).

    b. Now take the last element (starting from 8). Find the lower bound of 8 in the first sorted array. i.e, before out left.

    c. How will you find that? If you current element positioned at left is less than 8, then fine and ADD left + 1 to the ans. OTHERWISE you decrease the left by 1(See example at e.)

1 2 3 4 4 5 3 6 4 7 8.
1 2 3 4 4 5 3 6 4 7 8.
1 2 3 4 4 5 3 6 4 7 8.
1 2 3 4 4 5 3 6 4 7 8.
1 2 3 4 4 5 3 6 4 7 8.

(Here BOLD ones can be removed)
Now it must be clear why the ans is just left + 1.

d. Repeat this step until condition of strictly decreasing is violated(for 8, 7, 4). This condition will violate at 1 2 3 4 4 5 3 6 4 7 8. Simply we come out of the loop and print the ANS.

e. Now take an example where our element is 4 (Last 3rd ).
Here we will have to decrease the left by 1. (Before that we have not at all decreased the left). Why are we doing? We need strictly increasing sequence and 4 is already there.

Lets see all ways.

1 2 3 4 4 5 3 6 4 7 8.
1 2 3 4 4 5 3 6 4 7 8.
1 2 3 4 4 5 3 6 4 7 8.
1 2 3 4 4 5 3 6 4 7 8.

Observe that out left was decreased by only 1, in answer we will add left + 1 which is 3.

I hope it is clear.
Please see my code and read these statements to get a clear understanding.

(Dont get confused with the nested loop. At max loop might be executed for 2*n steps. Hence complexity is O(n) ).

Find out the answer yourself if sequence is already strictly increasing.

2 Likes

Can u explain your solution?