You are not logged in. Please login at www.codechef.com to post your questions!

×

GANGAAM - Editorial

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

This question is marked "community wiki".

asked 20 Jan '14, 01:02

vinodreddy%40iitb's gravatar image

1★vinodreddy@iitb ♦♦
31225
accept rate: 0%

edited 20 Jan '14, 14:17


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.

link

answered 20 Jan '14, 10:05

johnathan79717's gravatar image

4★johnathan79717
196125
accept rate: 0%

edited 20 Jan '14, 10:55

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

(20 Jan '14, 11:00) vinodreddy@iitb ♦♦1★

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."

(22 Jan '14, 08:47) niting1122★

@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.

(23 Jan '14, 15:04) vinodreddy@iitb ♦♦1★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,654
×3,752
×1,000
×11

question asked: 20 Jan '14, 01:02

question was seen: 2,406 times

last updated: 23 Jan '14, 15:04