i_love_vim's blog

[HELP] WA in CSES Movie Festival II
By i_love_vim, history, 4 years 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

Comments Comments (14)
| Write comment?
»
4 years 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.

→ Reply
  • »
    »
    4 years 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?

    → Reply
    • »
      »
      »
      4 years 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.

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

    whats the proof that this is optimal?

    → Reply
    • »
      »
      »
      4 years 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.

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

        Why is it always optimal to choose the latest person available? I cannot understand why that is optimal (Why can't we remove the element at the 0th place in case of a tie)?

        multiset<int> ms
it = ms.upper_bound(v[i]) 
if (it != ms.begin()) continue

        Formally, why ms.erase(--it) instead of ms.erase(ms.begin()) ??

        → Reply
        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          did you figure out why do we need to choose the latest person? I am stuck at same problem and can't figure out why it works like that only?

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

            NO

            → Reply
          • »
            »
            »
            »
            »
            »
            8 days ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Consider this case:

            4 2
1 2
1 5
6 7
3 8

            Person 1 will watch the first movie (from time 1 until time 2) and Person 2 will watch the second movie (from time 1 to time 5). When you decide who should watch the third movie (which starts at time 6) both persons are available again. But you have to choose the one that is available later, in this case person 2, then person 1 is free to watch the forth movie. If person 1 watches the third movie no one would be able to watch the forth movie.

            Choosing the latest person always ensures that the remaining persons are available earlier and therefore have the most potential to watch more movies.

            → Reply
»
4 years 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
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    did you get accepted ?

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

      You can see this: https://cses.fi/paste/bc4c79f7eee4db012401f1/

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

        It can be easier like this:

            int n, k;
    cin >> n >> k;
    vector<pair<int, int>> a(n);
    for (auto &[x, y] : a) cin >> y >> x;
    sort(a.begin(), a.end());
    multiset<int> S;
    for (int i = 0; i < k; i ++ ) S.insert(0);
    int res = 0;
    for (auto &[y, x] : a)
    {
        auto it = S.upper_bound(x);
        if (it == S.begin()) continue;
        -- it;
        S.erase(it);
        S.insert(y);
        res ++ ;
    }
    cout << res << '\n';
        → Reply