Editorial for the problem KTHMAX

Can anyone share their approach for the problem KTHMAX from DEC16

First try solving the problem maximum area in a histogram here https://www.hackerrank.com/challenges/largest-rectangle and also look at the editorial. It has a very similar stack approach.

Here is my approach:
Since we want to know the maximum element in a subarray and all the subarrays are sorted in descending order of the maximum element in them,we only want to know how many subarrays contain an element x.Suppose A[i] to be the number of subarrays whose maximum element is i.After solving this,answers can be easily got by binary search.
Now we consider how to calculate A[i],it is a typical way to solve this:consider i in descending order and we can simply calc this by linked list.
u can check my code at:link text

Sorry for my poor English.

The problem involves only observation, When we sort all subarray individually in decreasing order, then the maximum element in any subarray involves only those element which are less then equal to maximum element.

Only we have to find the starting and ending range of all element out of all subarray.

Highest element occurs in the range from ( 1 : k1 ) where k1 is number of subarray which will include highest element

Second highest element occurs in range (k1 + 1 : k2 ) where k2 is number of subarray which will include second highest element excluding those subarray which have highest element present in them.

And so on…

Lets take and example :

Array : { 4 , 1 , 3 , 4 , 2 , 5 }

5 will be maximum element in range from 1 to 6 : { (1 - 6 ) , ( 2 - 6 ) , ( 3 - 6 ) , ( 4 - 6 ) ,
( 5 - 6 ) , ( 6 - 6 ) }

Now , 4 will present in 2 places.

Let us take position 1 : { ( 1 - 1 ) , ( 1 - 2 ) , ( 1 - 3 ) , ( 1 - 4 ) , ( 1 - 5 ) }

Hence it will involves in 5 subarray range from 7 to 11.

Now next element 4 at position 4 : { ( 2 - 4 ) , ( 2 - 5 ) , ( 3 - 4 ) , ( 3 - 5 ) , ( 4 - 4 ) , ( 4 - 5 ) }

It will involves in 6 subarray range from 12 to 17.

And so on…

So for any ith element number of subarray in which that element is maximum is : A * B + B
where A is count of element to the left of ith element which are less then ith element and
B is count of element to the right of ith element which are less then equal to ith element( including ith element in case of B )

For the above array values of A and B are : { 4 , 1 , 3 , 4 , 2 , 5 }

index 1 : A = 0 and B = 5

index 2 : A = 0 and B = 1

index 3 : A = 1 and B = 1

index 4 : A = 2 and B = 2

index 5 : A = 0 and B = 1

index 6 : A = 5 and B = 1

It is the difference of positions of next greater element to the left and right side , which can be calculated using stack in linear time.

Now sort all numbers in decreasing order , and do prefix sum of number of subarray.

Then with the help of binary search we can find the value present in the range which will be the answer of our query.

Time complexity : log(N) per query.

Solution link : https://www.codechef.com/viewsolution/12194666

4 Likes

@vipsharmavip
I had a similar approach.
The only difference was that in the term AB+B which was eventually being calculated as (i-next_greater_to_i_left[i])**(next_greater_to_i_right[i]*i) (Your code eventually reduced it to this form only) I counted A as the count of element to the left of ith element which are less then ith element(including ith element) and B is count of element to the right of ith element which are less then equal to ith element( NOT including ith element in case of B ). But it was giving wrong answer. I cannot figure out how it’ll be different from your answer, since either of them can work. Care to explain? Thanks in advance.

I may have understood the problem wrongly.

For the case:
4 5 4 6, isn’t below the right decreasing sequence?

6

5 4 6

5 4

5

4 6

4 5 4 6

4 5 4

4 5

4

4

If yes, then an user has outputted 6 instead of 5 for query 3 and he is AC. I’m pretty sure I’m wrong, so I would be glad if you can tell me the right sequence. :slight_smile:

@samjia2000 i have used the exact same approach but getting WA.
can u pls tell what’s wrong


[1] 


  [1]: https://www.codechef.com/viewsolution/12253490

@samjia2000: Can you please answer my query in second comment? :slight_smile:

Let us sort each of the subarrays in descending order of the numbers in it.

Now you want to sort these subarrays in descending order. You can compare two subarrays B, C, as follows.

So we perform two sortings. One of the subarray itself and the second on the set of subarrays itself. I missed this point. :frowning: :frowning:

1 Like

Standard stockspan problem :slight_smile:

May be your code have some issue , kindly debug your code , because my code works for both the case.
Answer will be always same for both the cases , either you can take equal to its left or to its right.