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:
The subarray to be removed starts from first element
The subarray to be removed ends at last element
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
I donāt think any advanced data-structure like fenwick tree is needed. Simple binary search gives the right answer:- CodeChef: Practical coding for everyone
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.
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
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.
For sure
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.
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.
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).
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)
Observe one thing. Like If you want to keep only first sorted string only what are the posible ways to do so? Following are::
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.)
(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.
