RED BLUE using Binary Search

My solution was similar but didn’t involve much thinking: Choose a point as centre. Then sort the rest of the points according to slope with the respect to the centre. Now join centre to any other point and radially sweep this line to count how many points of each color are there on either side of line. Same complexity since we choose centre n times and O(n\log n + n) for sorting and radial sweep.

5 Likes

A very elegant solution indeed!

2 Likes

Too nice to be a solution! Awesome editorial.

2 Likes

Very nice editorial, I was trying something like this method but I couldn’t implement it

2 Likes

That was just awesome. It’ll Be great if you make a video editorial for it. Some things are bit confusing like “extending slope to all quadrants”.

1 Like

@gear4 what do you mean radially sweep? please elaborate your solution.

Awesome thinking and implementation indeed!!

I couldn’t solve this question, i didn’t know where to start from, can you explain why the naive solution works?
I’m unable to crack it.

thanx dada:)

1 Like

extending to all quadrants means same thing can be done for all quadrants. Example for quadrant 2 , if you have a line with slope P ,then you can see all lines that come above it have slope lesser than it in 2nd quad as there slopes are -ve. 3rd quad is similar to frst and 4th to 2nd. Just try drawing on a paper. :slight_smile: Btw i will try making video editorials too :slight_smile:

1 Like

yeah! I got your point. Thanks. Good luck for videos. I’ll be the first to watch :stuck_out_tongue:

This is also my solution (as a tester for this contest). The author’s solution is a bit more complicated, but has the same time complexity.

thank you :slight_smile:

@soham1234 why did you not consider line connecting a blue point and a blue point or a line connecting a red with red point ? Also by this approach will minimum answer always be 2 because we are using points to create a line ? in some cases it might be possible that we require to delete only 1 point or none of the points.

Questions says that find a line that requires minimum deletion of points and remaining red points on one side and remaining blue on another. So does that mean we can have 2 points on the line itself ? since 3 or more are not collinear there cannot be more than 2.

Why always 2? It can be zero as well. When I am drawing a line betn 2 points I am not deleting them rather taking them as a reference to choose which side I want the red and the blue point to be on that line and finding all points on other side to that point

1 Like

And for your first qstn see that a line through red and blue point is enough.You don’t need anymore. Proof: Firstly suppose u have taken 2 blue points and drawn a line. Now rotate the line until it touches a red pt. Now no red point crossed this line so cnt of red pt. deletion remains same. In case a blue point did cross the line i.e. went to other side then you can always construct a line betn that blue point and the touching red point. If you find my argument to be faulty you can try finding a case. Anyways even if its wrong you just need a few more cases to modify :slight_smile:

But we can have 2 points on the line right ? Or the required line(for solution) does not have any red or blue point on it ?

See what I am doing is taking a red and blue point joining a line between them and assuming that our solution line is not exactly this(solution line can’t pass through points) but it lies very close to this line with both points lying on opposite side. So two cases will be there with blue and red points in opposite direction. Now we need to find how many points to be deleted i.e. how many red points will be on opposite side of the chosen side of red points and how many blue pts on other side. Do this for both cases

The line won’t have points on it. We assume solution line to be very close to the line we form i.e. rotated by a very very small angle A such that no point crosses the line due to this rotation.