Your doubt exists because you are are no clear with the binary search part and how we count using it. Lets see if I can help-
For cases where i=0 has to be deleted, we handle separately. Binary search for the least index after which suffix array is all T. We get i=1 for that. We can now erase N-i arrays, i.e. 3-1=2 subarrays (which are [0.0] and [0,1]) and get correct array.
Then we do the same for i=1 . We get the least index as i=1. A subarray (to be deleted) can now end at 3-1=2 positions, i.e. indices 1 and 2. Hence we add 2 more and get answer 4.
Thanks for replying.
I am missing something very basic here. For 1 1 2, I can think of only two ways in which if we delete elements, the resulting array is strictly increasing.
If we remove index = 0, i.e. 1, the remaining array is 1 2 [ which is strictly increasing]
If we remove index = 1, i.e. 1 again, the remaining array is again 1 2 [ again strictly increasing]
But apart from this, if we remove any other combination, the resulting array won’t be strictly increasing right?
If we remove index = 2, the remaining array is 1 1 [not strictly increasing]
or if we remove index = 0 and index = 1, the remaining array will contain only 2 [ nothing before it so not increasing].
Regarding your explanation,
you said that we can get two ways by erasing [0,0] and [0,1] .
But what is [0,0] or [0,1] ?
Sorry if I sound stupid but somehow I don’t get it.
You said :- " or if we remove index = 0 and index = 1, the remaining array will contain only 2 [ nothing before it so not increasing]."
IN COMPETITIVE PROGRAMMING A SINGLE ELEMENT IS ALSO CALLED AS THE INCREASING SUBARRAY SO “2” IS ALSO THE INCREASING SUBARRAY(SEQUENCE), DON’T IGNORE IT .
@anon55659401 if you don’t mind can you explain the solution to this problem. I don’t understand some parts of the editorial. Please its a humble request
