UNSQUERS - Editorial

[dtu_amritkumar]

I solved this problem without using segment tree. I just used array and stack, I think the test files was not so strong.
My Solution - CodeChef: Practical coding for everyone

[he1senberg]

No, you can’t use LIS concept in this question suppose you chose a sub array 1 2 1000 3 4
So for LIS concept the longest sequence will be (1 2 3 4) but for the question the longest will be (1 2 1000) only as u dont have choice for 1000 to take it or not if you encounter a no. Greater than prev you have to take it . Hope it helps

[l_returns]

You could have reported in comments section

[hitesh0710]

Thanks guys , I got it now

[dtu_amritkumar]

Welcome Hitesh!

[anubhavdhar]

I used range maximum query and binary lifting to solve this problem, the main idea is the following.

If we connect each element to its next greater element with an edge; and those which don’t have a next greater element to a universal root, we get a rooted tree. Observe that the indices of the array act as exit numbers in the rooted tree.

Now the queries become, given the two exit numbers, find the maximum length of a chain.

Now the nodes between two exit numbers contain some(possibly zero) entire subtrees and at most one partial subtree. We use Range Maximum query for the entire subtrees and Binary Lifting for the partial subtrees.

my code: CodeChef: Practical coding for everyone

[r_ajan]

This can be done with range max segment tree + stack + next greater element.

[llaki10]

I did exactly this too, was going to post it here but saw your comment. In my case I used constant of 330, but I suspect many other values work too - it essentially got accepted on a very first attempt of choosing this constant.

Here’s my submission in case anyone wants to take a look - CodeChef: Practical coding for everyone.

[jyoti369]

@dalgerok

for(int sz = 2; sz <= n; sz++){
            for(int i = 1; i + sz - 1 <= n; i++){
                int j = i + sz - 1;
                dp[i][j] = max(dp[i][j], dp[i + 1][j]);
            }
        }

I did not understand this part, Please someone explain this part.
Btw the problem is very good.

[codesway]

This post was flagged by the community and is temporarily hidden.

[l_returns]

@llaki10 I really did not expect anyone using this approach
But you have used it !

[devshiv]

For 10 days i was thinking why LIS brute is not passing even for 10.

[anon39640204]

Yor way of doing problems are amazing. I liked your solution of scalar product tree and this one.

[l_returns]

Thanks

[kedar1514]

@l_returns
In the first query, Chef can choose to visit a contiguous subsequence of mountains with heights (4,2,3,1,5,5). The subsequence that gives the maximum satisfaction is (2,3,1,5)

Then why example input has answer 3 ?

[l_returns]

Chef will only not values in increasing order right. So he will write 0 2 3 5 and hence answer is len([2,3,5]) = 3

[kedar1514]

Got it thank you

[argha_kole1]

Here we are calculating the required output(i.e. max satisfaction) for each and every subarray having size “siz” throughout the array and also for each “siz” we’re using the precomputed output for subarrays having size “siz-1” as max satisf. for subarray [l,r] would be max. of values for [l,r] and [l+1,r] .

[jyoti369]

Thanks bro, I loved ur explanation.

[argha_kole1]

My pleasure .