UNSQUERS - Editorial

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

2 Likes

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

1 Like

Thanks :slight_smile:

@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 ?

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

Got it thank you

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] .

1 Like

Thanks bro, I loved ur explanation.

1 Like

My pleasure :smiley: :innocent:.

1 Like

@dtu_amritkumar can you explain what actually you are doing in your code by some text and example

LIS is (Longest Increasing Subsequence). But in this problem we are required to consider only contiguous subsequence. so if you want to use LIS then there is something called LCIS.
that is Longest Contiguous Increasing Subsequence. I hope that will help.

Can you explain your approach??

please any one explain test case-2.

I think this can also be done using HLD? Just construct a tree(s) of the “next maximum” and convert it to finding number of nodes in the path from L to R in the tree.

Yeah, I also passed this problem with the method.

How you using binary lifting can you explain bit more it will be helpfull for entire range I got… But how you using binary lifting for partial tree??

So what I did initially was reverse the indices to get the entry numbers of the tree nodes, which are more convenient to handle than exit numbers. Also I’ll be assuming that the nodes are indexed by their entry numbers

Now, the entire subtrees can be done with range maximum query where you store the maximum chain length in the subtree of i (which is basically maxdepth[i] = \max \limits_{u \text{ descendent of } i}\{depth[u] - depth[i]\}) and use rmq on that (not commenting much on this); and we solve for the partial subtree using binary lifting.

So the problem gets modified to Find the maximum chain length in a tree considering nodes with entry numbers between a and b only, where a is an ancestor of b. Why is a an ancestor of b? … well the rest of the query is handled by the rmq part, and we are only left with the partial subtree with a as the root of the partial subtree and b being the endpoint.

Now, for each child v of i, call dp[i] to be the maximum chain length considering nodes with entry numbers between i and v (loosely speaking, if you draw the tree this gives the maximum chain lengths among all descendent of i that arre drawn to the left of (before) v ). This is equal to \max \limits_{u \text{ descendent of } i \text{ and } u < v}\{depth[u] - depth[i]\}.

Now our final answer would be depth[a] + \max \limits_{c \text{ is in the path from } a \text{ to } b}\{dp[c] - depth[parent[c]]\}

Now, call dp2[c] = dp[c] - depth[parent[c]], and now it just becomes a matter of finding maximum value (i.e, value dp2[i]) in an ancestor-descenndent path, which can be solved using sparse table. And we finally add depth[a] to get the final answer.

Sorry for being miserable in explaining. Hope that helped :slight_smile:

1 Like

Did anyone implemented the code in the explanation in the video tutorial of Bharat Singla ???
i implemented the solution but this won’t give me the right answer .
If you did and get AC then please send me the link.

thanks for your good explanation …nice solution …have to implement it myself also to get clear picture…

1 Like

Check it out @maruf089
https://www.codechef.com/viewsolution/39789496

2 Likes