Author: Abdullah Al Mahmud
Tester: Gerald Agapov
Editorialist: Vinod Reddy
We will solve the problem using greedy approach. We will traverse the events occurring(Entering and exit of a gangster) according to increasing time and greedily select which gangster to interrogate and finally we proove the optimality using an exchange argument.
We can visualize the traversing time as taking snapshots of the party at each enter and exit of a gangster(We sort these events in increasing order of time and loop through). After each entering of a gangster if there are K gangsters(K > X-1) unmarked gangsters we pick the K-X+1 gangsters whose exit times are farthest and mark them for interrogation. We continue this process for the whole events and finally we get the required no minimum count. The total algorithm can be implemented in O(NlogN). The logN factor here is for maintaining the end points of unmarked gangsters who are present in the party.
Let O be an optimal solution for picking gangsters for interrogation.Let the solution given by above algo is P. When we are traversing the events let t be the first snapshot of party where there are K > X-1 unmarked gangsters. According to O some(at least K-X+1) of these K gangsters are marked. lets take the gangster whose exit time is farthest. P picks this guy for marking but if O doesn’t pick this guy then we can make a change in O by unmarking the gangster with smallest exit time and marking the one with the farthest. We can easily see that this doesn’t cause any problems.
Similarly we can do this for all the K-X+1 gangsters picked by our algo. So at this snapshot we can say that the set of gangsters marked by P is subset of that of O. We can extend the argument to all snapshots and this employs that P is at least as good as O but O being the best so should be P.
Setter’s Solution: GANGAAM.cpp
Tester’s Solution: GANGAAM.cpp