Contact Us | CodeChef - Copyright Violations part is for you 
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.
[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 : CodeChef: Practical coding for everyone
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 understand your logic. I was thinking the same way at first.
But, 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. means, there has to be a bomb placed inside [L, R] for it to be destroyed. As long as a bomb is not placed between L and R, both inclusive, that kingdom cannot be destroyed.
The problem statement doesn’t say that if that kingdom completely falls within another that is destroyed, this also gets destroyed. (Unfortunately, … represented as intervals on the real line … makes it confusing. )
in the above case how many bombs are required i think 1.