ABSNX - Editorial

[w_marlin]

It is Very Strict Time Limit. My time complexity was O(2nlog(2n)) it failed on one subtask

[s_h_shahin]

Similar situation in my case too.
My complexity was O(2 * n * log(n)). Really depressing.

[a_nonymous1999]

I tried the same with pbds but ended up replacing with Fenwick tree due to tle, pbds is significantly slower than Fenwick tree. I think the reason behind is it utilizing bitwise operations which are simple to process.

[l_returns]

Seems like my approach is different from the editorial. I am sharing it here.
Used Divide and conquer with sliding window for solving this problem in O(n*log(n)).

https://www.codechef.com/viewsolution/33514092

• We find answer of subarrays which lies completely inside both children respectively recursively and add their count of subarrays to parent.

• For left children we keep min and max value of suffix having leftmost element of suffix as min or max value of the suffix. ( stored in vector “mx” and “mn” in my code)

• For right children we keep all prefix having rightmost element of prefix as min or max value of the suffix. ( stored in vector “mx” and “mn” in my code)

• The mn,mx pair is naturally sorted as mn decreasing and mx increasing throughout all pairs. ( So it sorted in non increasing order if we see min value and at the same time it is also sorted in non decreasing order in we look at max value)

• Now parent will find all the subarrays which starts in left child and ends in right child using two pointers.

• For that we will try to pair suffix arrays of left child whose leftmost element is its minimum value with prefix arrays of right child whose rightmost element is its max value and vice versa (i.e max from left and min from right).

• Suppose we select ith suffix then there will be a range l_i,r_i such that the all the ranges (valid prefix of right child) with index in range l_i,r_i are valid for this suffix.

• If you think or observe, l_i <= l_{i+1} and r_i <= r_{i+1}. Hence we can use sliding window here.

• Also we will have to exclude double-counted subsequences as mentioned in editorial.

Example to help you observe and understand better

• Left child elements

  0 20 0 1 5 3 2 8 2 3 4 6 4 

• Left Child’s min and max value of prefix where leftmost element is its min value

  4 4 ( considering 4 )
  4 6 ( considering 4 6 4)
  3 6 ( considering 3 4 6 4)
  2 6 ...
  2 8 ( considering 2 8 2 3 4 6 4)
  0 8 
  0 20

• Right child’s elements

  5 3 5 7 7 1 7 0 8 10 15 20

• Right Child’s min and max value where rightmost element is its max value

  5 5
  3 5  ( 5 3 5)
  3 7  ( 5 3 5 7)
  3 7 ( 5 3 5 7 7)
  1 7 
  0 8 (5 3 5 7 7 1 7 0 8)
  0 10
  0 15 
  0 20

Feel free to ask in case you have any query.

[i_gupta0903]

Here, since we know that max/ min element has to be one of a[L] and a[R], so is it not correct to find out the continuous increasing ,decreasing subseq in the array and count the no. of subarrays in those continuous increasing and decreasing subseq.
https://www.codechef.com/viewsolution/33497864
(here ans-1 at each step is done remove the overlapping element in two consecutive increasing , decreasing segment )
It would be a great help if somebody could point out the mistake…

[rock19]

Yes, I also thought the same logic. Can anyone point out the flaw in the logic?

[rath772k]

Consider this test:
4
10 9 10 9

Actual answer 10, your answer 7

[pastor]

actual ans must be 8

[i_gupta0903]

okay got the error in logic … my logic is not including subseq 10 9 10 9 …
PS: actual answer would be 8

[anon97456879]

@taran_1407

Here, we can simply use Merge Sort Tree to solve the problem in O(N*log^2(N)) time by building Merge Sort on nxt and querying (prevr,r] for number of elements greater than r

i can’t understand this part… can someone please elaborate.?

[abc1233]

Can anyone explain the query and update part in fenwick tree with l nxtl prevr r in more detail as that part is not detailed by editorialist well?

[abc1233]

Anyone please explain this part! Thanks in advance

@taran_1407

But we have an efficient approach. Let’s fix lll and consider all such rrr which have prevr<lprev_r < lprevr​<l. We need the number of such rrr which have l≤r<nxtll \leq r < nxt_ll≤r<nxtl​. We need to use a range structure (Fenwick Tree would be best here).

Let’s sort all pairs (prevr,r)(prev_r, r)(prevr​,r) by prevrprev_rprevr​ and considering lll from left to right, we can have a pointer moving towards the right, considering all such rrr which have prevr<lprev_r < lprevr​<l. We can update all such rrr in Fenwick Tree and query for the number of values in range [l,nxtl)[l, nxt_l)[l,nxtl​)

[vaibnak7]

Imortant thing to observe here is that all l, r, prev( r),next(l) are all indices in the array.

As per the give equation defined above you can see that if you think of l and r as two indices then l must repsect the property of r (>prev( r)) and r must respect the property of l (<next(l)).

so if we iterte over l, then for a particular l, all the rs having prev( r)<l have already been processed (we can sort and go through prev( r), untill prev( r) >= l), so we mark all the rs corresponding to those prev( r)s in our BIT (Binary Indexed Tree), now we just have to find out of all the rs marked how many of them are between l and next(l), that we do by doing a simple query.

when we do that for all l we will get the answer.

[vaibnak7]

I implemented merge sort tree in recursive fashion but got TLE, as the editorial solution creates merge sort tree in iterative way, is my recurive method the reason for me getting TLE

link to my code

[galencolin]

That’s something you’ll probably have to benchmark with a maxtest, there’s not much of a way for anyone to know that

[vaibnak7]

okay

[abc1233]

Thank you for more detailed explanation , I will try understanding if not I will again disturb you by asking it , OK

[virtuality]

I think I’m using the same logic as given in the editorial, but I’m still getting TLE.
I didn’t completely understand the fenwick tree method given in the editorial. What I did was for every r = 0 to r = n-1, I found the values of l that have next[l] > r using fenwick tree (Number of elements greater than K in the range L to R using Fenwick Tree (Offline queries) - GeeksforGeeks). I think this is the same logic given in the editorial. Then I reversed the array and computed the count again and then subtracted the common elements as mentioned in the editorial. I have no idea why I’m getting TLE. Please help…
Code: CodeChef: Practical coding for everyone

[sudhanshu_38]

Has anybody solved this using segment trees?

[aditya_sheth]

We can also solve this problem in O(n log n) using Divide and conquer. But I guess the intended solution is much more elegant.