GANGAAM - Editorial

editorial
, , ,
1

PROBLEM LINKS

Contest

Practice

Author: Abdullah Al Mahmud

Tester: Gerald Agapov

Editorialist: Vinod Reddy

DIFFICULTY:

easy

PREREQUISITES:

Greedy Algorithms

EXPLANATION

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.

Proof :
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.

SOLUTIONS

Setter’s Solution: GANGAAM.cpp

Tester’s Solution: GANGAAM.cpp

3 Likes
2

In paragraph 2, it should be (K > X-1) right? Also just to remind you that the above problem link “Practice” is still linked to the contest link.

3

Thanks for the observing the mistakes. I wrote the editorial in a haste. I will correct them.

4

In Paragraph 3, Can someone please explain why this statment is true ?
“According to O some(at least K-X+1) of these K gangsters are marked.”

5

@niting112 : Here lets say K > X gangsters are in the part at at some time t. If O marks less than K-X+1 gangsters of these K gangsters it implies that there are more than X gangsters who are not marked and are in the room at the same time which is contradiction to the given constraint in the problem. Hope this helps.