Thanks for telling, I missed that part, I will read about counting sort.
As per my understanding of the problem, for the following test case :
6
6
1 3
2 3
2 5
5 6
6 9
9 9
7
1 3
2 3
2 5
5 6
6 9
9 9
7 8
3
1 1
2 2
3 3
4
1 1
3 4
6 6
9 12
5
1 1
3 6
5 5
4 12
14 18
5
1 5
3 7
4 9
2 6
8 12
the answer should be :
2
2
3
4
3
2
and not :
3
4
3
4
3
2
(answer by setter’s & tester’s solutions)?
@nssprogrammer @shiplu
1 Like
Can any one please explain what is wrong in this solution.
Am trying to find a point which is contained in maximum number of intervals.
After finding such point, all the intervals which do not contain this point are preserved and which contain this point are removed from the intervallist[].
//intervallist[i].s //start of interval i
//intervallist[i].e //end of interval i
int bomb = 0;
while(totalintervals > 0)
{
bomb += 1;
memset(ab, 0, sizeof(ab));
for(i = 0; i < totalintervals; ++i)
{
ab[intervallist[i].s] += 1;
ab[intervallist[i].e+1] -= 1;
}
for(i = 1; i <= 2000; ++i)
{
ab[i] += ab[i-1];
}
//find the point which is contained in maximum number of intervals.
int max = -1;
int maxi = 0;
for(i = 0; i <= 2000; ++i)
{
if(ab[i] > max)
{
max = ab[i];
maxi = i;
}
}
// now all the intervals which do not contain the point(maxi) are preserved.
max = 0;
for(i = 0; i < totalintervals; ++i)
{
if((intervallist[i].s > maxi) || (maxi > intervallist[i].e))
{
intervallist[max] = intervallist[i];
max++;
}
}
totalintervals = max;
}
printf("%d\n", bomb);I think nobody noticed that 
This thought is same as the GREEDY approach to do maximum jobs done in job scheduling algoithm in operating system.
Anyway,The most funniest part was that this qn was same as link text .
Happened just 10 days before JAN15.
And last but not the least:the solution was EXACTLY same as that problem!!!
7 Likes
sad story 
1 Like
can anyone tell what this line mean and what is the initial value of ar[]
ar[b[i]]=max(ar[b[i]], a[i])I am the author of that problem. I LOLed hard when I saw this question. xD
3 Likes
Can Someone give me the proof of correctness for greedy aproach.
Actually, the setter for this problem added it to the codechef site 16 days before I added mine. xD
1 Like
For the first test case,
6
1 3
2 3
2 5
5 6
6 9
9 9
A bomb has to be placed on 9, in order to destroy [9, 9]. This also destroys [6, 9].
Out of the remaining four intervals [1, 3], [2, 3], [2, 5], and [5, 6], the first and the fourth do not intersect, and hence will need at least two more bombs.
In fact, with two more bombs, the second and the third can also be destroyed. So, the answer is 3 (and definitely not 2).
You must have misunderstood the problem at some point.
1 Like
In this case…if I place bomb at 2 first, it will destroy [1,3], [2,3],[2,5] first. Then if I place bomb at 6 then it will destroy [5,6] & [6,9] now from which logic in this world, [6,9] has been destroyed and [9,9] is intact? I think [9,9] is automatically destroyed with [6,9], so only 2 bombs needed in this case at i=2 & i=9.
for the following test case
(1 100)
(4 8)
(4 15)
(35 43)
(42 55)
if by a single bomb placed at any point in 1 to 100 whole kingdom from 1 to 100 is destroyed .
then wont automatically whole kingdoms lying in range 1 to 100 destroyed?
Just sorted the intervals by right end and always placed a bomb at right end if the current interval cannot be destroyed by immediately previous bomb my solution
Exactly similar to this spoj problem.
1 Like
[6, 9] is destroyed doesn’t mean [9, 9] is also destroyed.
A kingdom of the form [L, R] can be destroyed completely by placing a bomb at a point x on the real line if L ≤ x ≤ R.
As long as you don’t place a bomb at some x such that 9 <= x <= 9, the kingdom [9, 9] won’t be destroyed.
If you are thinking [9, 9] gets destroyed automatically with [6, 9], then there is a small flaw in that. If it was [9, 10], would it also have been destroyed with [6, 9]? Why or why not?
If you answered yes, then you only would have needed one bomb for our original test case, as all the kingdoms are overlapping with one other at some point.
From the problem, for a kingdom to be destroyed, there has to be a bomb placed between its L and R. It is not sufficient that it completely ovelaps with another kingdom, and the outer kingdom is destroyed with a bomb, which is outside the bounds L and R.
anything like [9,10] or [6,11] will not be destroyed because we placed a bomb at x=6 (in previous comment I said we need to place bomb at x=2 and x=9, which is mistyping, I want to say we need to place bomb at x=2 and x=6 only) which destroyed [6,9] interval and hence all things upto x=9 has been destroyed. And if all things upto x=9 has been destroyed then why we need to destroy [9,9] again. but if it was [9,10] then we need to delete all parts>9 and so one more bomb required. And in first case we will need 2 bombs because there is difference bw compeletely overlapping & little overlapping.
I don’t know why it’s so tough for anyone to get. If I destroyed a whole city then of course all colonies have been destroyed. But yes if a city with some part same as other city has been destroyed (because of range/nature of bomb) then we need to place remaining part of that city as well.
You can see my solution here : http://www.codechef.com/viewsolution/5854433
The Greedy approach isn’t always correct and I thing this is that case. Anyways thanks for your explanation. At least you bothered to reply. Admins don’t even care about a genuine doubt. Many people asked for correctness proof.
i used a similar activity selector algorithm given in cormen… but i got wrong answer…
here is the link to my solution http://www.codechef.com/viewsolution/5754242
plz explain why this algorithm can’t be implemented…