i_love_vim's blog

By i_love_vim, history, 9 months ago, In English

Hello all,

I am trying to solve CSES movie festival II using the same logic for movie festival I. I am greedily assigning the movies to k people sorted by end times. But this is giving me WA on cases 5, 6, and 7. These cases have n = 200000, so I cannot work them out on paper to find out the problem in my logic. So request to please give me some test cases to help me find the mistake in my logic.

My code

Spoiler
 
 
 
 
  • Vote: I like it
  • -6
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by i_love_vim (previous revision, new revision, compare).

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem link is 1632

Greedy. We process films in order of end time. For every film, if no person is free at start time, we dont watch that film. If at least one person free, we use the one latest free. Repeat.

We need to maintain a list/queue of persons with their times when they get available to watch the next film. Initially all persons are available at time 0.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks!

    I also found this for better understanding the latest free part.

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

    Hi spookywooky!

    Are you sure that list/queue (linear data structure) is enough and no need for set/multiset/pq?

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

      You are right, since we need to query the one latest free from the list/queue we need some sort of priority queue.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    whats the proof that this is optimal?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We process the films in the order of first end, that means we find the max number of watched films of a non increasing interval. Obviously we cannot watch more than the films that exist in that interval. So, foreach film we can watch it or not watch it. If we can watch the film it is allways optimal to do so since we cannot get a better result by not watching a film. "Can watcht the film" means that there is a person available at start of the film. If there is more than one person available it is always optimal to choose the person latest available, because again, we cannot get a better result by choosing another person.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

(For future reference)
A sample TC for which my logic will give WA is->

4 2  
1 5  
1 3  
4 12  
8 10