Hello everyone, I am having a problem in solving this problem from CSES problem set. I could not find any explanation for this problem.
I solved the "Movie Festival" problem which is easier version of this one by simply sorting the intervals by end time and then iterating over all the intervals and comparing begin time of each interval with previous interval's end. But that approach will give O(n^2) in this problem.
I was thinking of applyng Mo's to use the same approach but could not proceed.
Any help would be appreciated. Thanks and keep coding!!
Binary lifting
For each segment, find the next segment, the next next segment, the 4x next segment and so on
For each segment, find the next segment, the next next segment, the 4x next segment and so onCan you explain with an example?
I mean that I know binary lifting but I am unable to think of how to apply it here
As you see, you don't. Leave this problem and return to it when you become stronger (blue+). Now some Div2Bs are waiting for you.
Or you could just explain it a bit. At least I will learn something new.
I did, and in both cases, either you didn't try to understand it, or you didn't want to, the next step of helping with this problem is to provide a source code.
You can google the code (for example, on my github) and copypaste it and get accepted. Maybe you will learn it.
Still, this knowledge is useless because it never occurs in problems you usually face at your level.
Did you considered using Binary search for each query?
I hope you understand the greedy for maximum events. You want to choose the one that ends as early as possible. Now, what this means, is that if you choose some event, the next events are fixed. You could alternatively, think of it as, you want any next $$$k$$$ events to end as early as possible too.
Let $$$dp_{i,j}$$$, be the last event with the earliest possible ending time, assuming you visit $$$2^j$$$ events after event $$$i$$$.
To compute $$$dp_{i,j}$$$, we just need to find where $$$dp_{i,j-1}$$$ ends, and find the event that ends the earliest after it, and use $$$dp_{e,j-1}$$$, to get the next $$$2^{j-1}$$$
Now consider, for each query, you need to find the event that ends first in that range. Now you want to start binary lifting. Check if $$$2^k$$$ events are fine. If they are, then you can go that event, and binary lift from there with $$$2^{k-1}$$$, and so on. $$$k$$$ is $$$O(\log n)$$$.
Ah! got it now. Well explained. Thanks a lot. (I was initially thinking dp[i][j] as answer for interval i to 2^j)