ONEKING - Editorial

PROBLEM LINK:

Practice
Contest

Author: Snigdha Chanda
Tester: Shiplu Hawlader
Editorialist: Lalit Kundu

DIFFICULTY:

EASY-MEDIUM

PRE-REQUISITES:

Greedy

PROBLEM:

Given N (≤100000) intervals [Ai, Bi], one such interval can be deleted by placing a bomb at x if Ai ≤ x ≤ Bi. Find minimum number of bombs required to delete all intervals.

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.

Pseudo code:

n,a,b = input
ar=[]    //ar[i] denotes maximum starting point for intervals ending at i

for i=1 to N:
    ar[b[i]]=max(ar[b[i]], a[i])
    
ans=0
max=-1  //denotes the latest value of x where we placed a bomb

for i=0 to 2000:
    //we need a bomb to all intervals ending at i'th position
    if max < ar[i]:
        ans += 1
        max = i
print ans

Complexity: O(N+2000).

SOLUTIONS:

Setter’s solution
Tester’s solution

7 Likes

I spent a lot of time on this ones, getting TLE for O(2N * log(2N)) solution (both in Java and C++). I think this is not a problem if we had to solve it in O(N+2000) and then time limit was increased :frowning:

With increased time limit the solution can be:

  1. for earch interval add two events - interval start/end
  2. sort events by coordinates if two events have same coordinate, start events are before end events
  3. process all events - for start event insert interval index to set of opened intervals, on end event if interval index is in set of opened intervals add bomb and clear set of opened intervals (all are destroyed) if is not in set (because it was cleared before) do nothing (continue with next event)

My code - http://www.codechef.com/viewsolution/5739201 (Java), http://www.codechef.com/viewsolution/5740255 (C++)

1 Like

Setter and tester’s solution link showing access denied.

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

Can you explain your approach? :slight_smile:

I added it in meanwhile…

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.

1 Like

check out my solution
http://www.codechef.com/viewsolution/5877185

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

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?

As usual, link is missing :slight_smile:

2 Likes

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

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.

Why I am not able to see the Setter’s solution.
Showing:
This XML file does not appear to have any style information associated with it. The document tree is shown below.

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

@abcdexter24: It was discussed in advance here - http://discuss.codechef.com/questions/60641/long-jan15-one-dimensional-kingdoms-time-limit and is also in announcements on contest page

I have a similar approach but slightly different. sort according to ending time. then have the answer as n(no. of intervals ). for each overlap subtract the answer by 1. got AC. MY SOLUTION

Shouldn`t the order of the approach in editorial be O(n*log(n)), because initially sorting is done.

First we sort all intervals according to increasing Bi.

Hi. Can somebody tell me why my solution is wrong? I have implemented the same idea that is described here but I can’t find my mistake. Here is the link to my solution

We can take advantage of the fact that the numbers are between 0 and 2000 and use counting sort - http://en.wikipedia.org/wiki/Counting_sort in O(N)

2 Likes