Help Solving CSES Movie Festival 2 (Sorting and Searching)

Problems and Contests
#1

Hey guys, I am just here to ask for some help. My initial approach to the problem was to write a for each that would loop for all the movie watchers and on each iteration removing every movie that could be watched and keeping a count alongside it.

My attempt was partially correct. There were just TLE’s that I don’t know how to kill.

I then read the USACO solution and I don’t understand their use of multiset in this problem. (Problem link) Can someone please explain the solution to me.

#2

I simplified the guide solution. Let me know if anything is still unclear.

#3

Thanks for updating the solution, all clear now.

#4

Hello,

I am having trouble with this problem as well.
I have approached the problem in a similar way as Kenna_Nemera. I also got TLE on CSES. I read the solution and I understand the use of multiset. It helped reduce time. But I wanted to solve the WA issue as well. I ran stress testing but couldn’t find anything.

Code:

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    long long n, k;
    cin >> n >> k;
    vector <bool> watched(n, 0);
    vector <vector <long long>> arr (n, vector <long long>(2));
    for (long long i=0;i<n;i++){
        cin >> arr[i][1] >> arr[i][0];
    }
    long long ans = 0;
    sort(arr.begin(), arr.end());
    for (long long i=0;i<k;i++){
        long long currTime = 0;
        for (long long j=0;j<n;j++){
            if (watched[j]==0 && currTime<=arr[j][1]){
                currTime = arr[j][0];
                ans++;
                watched[j]=1;
            }
        }
    }
    cout << ans << endl;
}

Also, I don’t know if this is related, but I was confused about this sentence in the internal sol:
“If there are multiple such elements, choose the greatest one (the member who finished watching his assigned movies the latest).”
Why is this the case? If I don’t do this, could it cause WA?
For myself and future viewers, it would be appreciated if you could add more detailed explanation.

#5

It TLEs because your code has a time complexity of \mathcal O(N\log N + N\cdot K) (N\log N from sorting, and N\cdot K from the two stacked for loops), which is too slow given that K\leq N\leq 2\cdot 10^5.

#6

I already understand why my code TLEs but my focus is on understanding why it WAs. Does my code have any bugs? Or can there be any memory issues or something? On CSES, my code WAs on larger cases so I suspect some kind of memory issue maybe…?

#7

I am pasting the solution which was posted :-

The first step is the same as that of Movie Festival; sort the movies in increasing order of end time. For each movie in order, we will assign it to one of the kkk members to watch (or none of them).

Keep track of the time each member finishes watching all of his currently assigned movies in an ordered multiset (represented by a TreeMap in Java or a multiset in C++). Initially, the collection consists of kkk zeroes.

For each movie in order, we can assign a member to watch it if there exists an element in the sorted collection less than or equal to the start time of the movie. If there are multiple such elements, choose the greatest one (the member who finished watching his assigned movies the latest). Assign the member to watch this movie by incrementing the answer and updating the collection accordingly.

Can someone please explain the greedy idea behind this and how it helps. Thanks in advance :smiley:
@Benq

If there are multiple such elements, choose the greatest one (the member who finished watching his assigned movies the latest).