ONEKING - Editorial

editorial
, , , ,
21

3

1 3

2 2

3 4

(Answer:2)

In the above test case if I placed the bomb on positon 3, won’t it destory all the locations?
So only one bomb required.
why the accpeted answer is 2?

22

“EXPLANATION:
First we sort all intervals according to increasing Bi.
Now, let’s say we have placed a bomb at position x on the line. All intervals such that their starting point Ai ≤ x will get destroyed. So we’ll greedily place the bombs when required.”

Clearly, this explanation is wrong. All intervals with Ai <= x AND x <= Bi will get destroyed. Just having the starting point less than x is not enough. Consider the example
Let {[1, 2], [3, 4], [5, 6], [7, 8]} be the intervals. As we can see they are sorted by increasing Bi. if we choose x = 7, the none of the intervals [1, 2], [3, 4], [5, 6] will be destroyed even though they satisfy Ai <= x.

23

Someone please throw lights on the necessity of sorting the array according to ending time.A counter example will be enough.

24

Hello everyone ,there is no need of sorting here you can implement the above code without sorting.
here is my solution:
https://www.codechef.com/viewsolution/14315810

25

Why is this solution wrong – sorting the intervals based on Ai (start time), overlapping them, and then count the disjoint intervals?

26

Setter and tester’s solution link showing access denied.

27

According to editorialist’s answer it will be available a little later (as I understood for all problems).

28

Can you explain your approach? :slight_smile:

29

I added it in meanwhile…

30

I too used a similar approach with O(N*log(N)) solution.

  1. Sorted the intervals with start time.

  2. Pushed first interval in stack.

  3. From 2nd interval onwards i checked if intersects with the interval on top of stack ,if it does i need to push only the intersection.Otherwise push the new interval too.

  4. Total no of intervals on stack is the number of bombs.

4 Likes
31

I also used similar approach with sorting by start time, only counted the number of bombs downwards.

32

Maybe I missed something, but you have several intervals on stack, how can you check only with first one?

Let say intervals are [1, 3], [2, 4], [5, 7] and [6, 8], stack processing 3 intervals is [2, 3], [5, 7]. Can you describe better what are you doing with last interval?

33

after processing 3 intervals [5,7] will be on top of stack so i compare [5,7] with [6,8] they intersect so i pop [5,7] and push [6,7].
Finally stack contents are [2,3] [6,7]

1 Like
34

I agree with you, first I got confused on how to do it under 0.50 seconds. I tried O(N) but got WA. I knew the code was wrong (it gave wrong answers in some test cases by me). Then when I saw time limit as 2 seconds, I got angry on the problem setter, as this means the question in nothing but reduced to an activity selection problem in which N*log(N) can be used. thus ACed today.

35

Thanks for a reply, it’s all clear now :wink:

36

@abcdexter24: It was discussed in advance here - Long JAN15 - One Dimensional Kingdoms - Time Limit - general - CodeChef Discuss and is also in announcements on contest page

37

We can take advantage of the fact that the numbers are between 0 and 2000 and use counting sort - Counting sort - Wikipedia in O(N)

3 Likes
38

Thanks for telling, I missed that part, I will read about counting sort.

39

sad story :frowning:

1 Like
40

I am the author of that problem. I LOLed hard when I saw this question. xD

3 Likes