-grace-'s blog

Movie Festival Queries Problem
By -grace-, history, 4 years ago, In English

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

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it
Spoiler
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For each segment, find the next segment, the next next segment, the 4x next segment and so on

    Can you explain with an example?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      I mean that I know binary lifting but I am unable to think of how to apply it here

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Or you could just explain it a bit. At least I will learn something new.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +2 Vote: I do not like it

            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.

            → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Did you considered using Binary search for each query?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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)$$$.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ah! got it now. Well explained. Thanks a lot. (I was initially thinking dp[i][j] as answer for interval i to 2^j)

    → Reply