### -grace-'s blog

By -grace-, history, 13 months ago,

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!!

• +5

 » 13 months ago, # | ← Rev. 2 →   +10 SpoilerBinary lifting SpoilerFor each segment, find the next segment, the next next segment, the 4x next segment and so on
•  » » 13 months ago, # ^ |   0 For each segment, find the next segment, the next next segment, the 4x next segment and so onCan you explain with an example?
•  » » » 13 months ago, # ^ |   -10 I mean that I know binary lifting but I am unable to think of how to apply it here
•  » » » » 13 months ago, # ^ |   -8 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.
•  » » » » » 13 months ago, # ^ |   0 Or you could just explain it a bit. At least I will learn something new.
•  » » » » » » 13 months ago, # ^ |   +2 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.
 » 13 months ago, # |   +1 Did you considered using Binary search for each query?
 » 13 months ago, # | ← Rev. 2 →   0 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)$.
•  » » 13 months ago, # ^ |   0 Ah! got it now. Well explained. Thanks a lot. (I was initially thinking dp[i][j] as answer for interval i to 2^j)