Maximum circles (hb)

#1

CAN YOU TELL ME THE APPROACH OF THIS QUESTION

#2

https://hack.codingblocks.com/contests/c/588/563 - THIS IS THE URL OF THE QUESTION

#3

@Ayushi21
This is a greedy technique problem , so …just get greedy.
This problem is actually very very similar to the Activity Selection problem covered in the Greedy Technique’s video section in your course.
Take as input the centers and radii of the circles.
But as you take the centers and radii , compute their starting point i.e. the leftmost point of the circle and their ending point i.e. the rightmost point of the circle.
start = c - r;
end = c + r;
Now you need to sort the circles based on some parameter. For now I’ll leave it to you to figure out the sorting parameter. I have already given you a hint - It is very similar to Activity Selection problem.

Try it out and let me know if you need more hints or help with your approach.

#4

https://ide.codingblocks.com/s/110136 - please check my code

#5

@Ayushi21
Follow the specified input format.
First input you get is the number of circles.
Let’s store that in n.
So
int n ;
cin >> n ;
Now create your vector of pairs as you have .
Run a loop of for n times so you can take n inputs.
In each iteration , take two inputs - the center and the radius.
while(n–) {
int c,r;
cin >> c >> r;

Now compute the start and the end vertices or the left and right vertices.
int start = c - r;
int end = c + r;

Now that you have both of these points, push this pair into the vector
circles.push_back(start,end) ;

End your loop which runs for n iterations
}

Now do the sorting and the rest of the algorithm.

Kindly make these modifications and let me know if you have any further issues.

#6

please check my code. still is not working. https://ide.codingblocks.com/s/110585 — this is the url of the code.

#7

@Ayushi21

  1. Use long long int instead of int as the values are pretty large as specified in the problem constraints.
  2. While pushing start and end into the vector , you have to push back a pair. So use make_pair function to make a pair
    circles.push_back(make_pair(start,end));
  3. Your final answer will not be count but rather circles.size()-count. So change your final output statement to
    cout << ( circles.size() - count ) ;
#8

i have done the modifications to the code…but it is still not working. please check it. https://ide.codingblocks.com/s/110936 - this is the url of the code

#9

@Ayushi21
There is an extra closing bracket } before return 0; statement in Line No. 45.
Remove that since it is giving syntax error.
Your code works fine.