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

9 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 - CodeChef: Practical coding for everyone (Java), CodeChef: Practical coding for everyone (C++)

3 Likes

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

1 Like

As usual, link is missing :slight_smile:

2 Likes

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.

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

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 :slight_smile:

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

can anyone tell what this line mean and what is the initial value of ar[]

ar[b[i]]=max(ar[b[i]], a[i])
1 Like

Can Someone give me the proof of correctness for greedy aproach.

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 :slight_smile: my solution

Exactly similar to this spoj problem.

1 Like

i used a similar activity selector algorithm given in cormen… but i got wrong answer…
here is the link to my solution CodeChef: Practical coding for everyone
plz explain why this algorithm can’t be implemented…

The problem , is the same as ZCO 2015 . Pasted the same solution, in nlogn .Got 100 .

1 Like

if we sort set according to start time

@darkshadows I have a question regarding your approach. I think I dont have permission to comment, so added as a answer. Why is sorting necessary before any operation in your approach? The one we are using to calculate the answer is ar[] and the values in it should be same irrespective of the sorting. Please mention the mistake in my approach because i observed that the solution is not accepted when i did not sort and is accepted when i sorted the array.