RED BLUE using Binary Search

general
1

PREREQUISITES: Binary search, Line equations, slope finding

Okay so here is an editorial for [REDBLUE][1] using Binary Search. Yes you heard it right. Binary search is enough to solve the 7th problem. :slight_smile: Lets start with the naive/brute force solution. Idea is pretty simple. Construct a line using a red and a blue point. The equation will be of form ax+by+c=0. Let us call this f(x,y). As you know given 2 points P1(x1,y1) and P2(x2,y2) you can find if they are in opposite side to the line by satisfying *f(x1,y1)f(x2,y2)<0. If product is >0 then they are on same side. So now we can loop over all red and blue points. Keep 2 counters cnt1=0 and cnt2=0. For a red point if f(x,y)<0 we increment cnt1 else cnt2. For blue point if f(x,y)<0 we increment cnt2 or cnt1. So for this line the minimum points to be deleted is min(cnt1,cnt2). We can do this for all lines that can be drawn for a given pair of red and blue points and find the minimum. Complexity=O(n^3)

[Here][2] is my brute force code.

Lets try improving this a bit. First fix a blue point. Consider this as the origin of a shifted coordinate system. Now when you draw a line from this blue point to a red point it becomes a line passing through origin in the shifted system. So you can easily see that this line only cuts 2 quadrants whereas 2 other remain unaffected.
![Fig:1][3]

As you can see in the figure all the other lines having slopes less than p lie on one side and greater than p lie on other. This can be extended to all quadrants. So what we do is after fixing the blue point we loop over all red points and store their slopes w.r.t the selected blue point for all 4 quadrants. Then we do the same for all blue points except the selected one. Now sort all the slopes in all 4 quadrants. Now choose a red point say r in 1st quadrant. All red points to the right of the line which is formed by joining r with the selected origin(blue point) are:

  1. all red points in quadrant 2.
  2. all red points having slope greater than r’s slope in quadrant 1
  3. all red points having slope less than r’s slope in quadrant 2.

2 and 3 can be found by using binary search in quadrant 1 and 3.
Similarly we can do the same to find all red points to the left of the line and blue points on either side.

This is to be done for all the red points in all quadrants.

So complexity is nnlog(n). n for selecting a blue point and making it origin, then for each blue point choose a red point to form a line with which incurs a cost of n more and finally finding all points on either side of the line take log(n).

Hence complexity becomes: O(n^2*log(n)).

[Here][4] is my code for 100 points.

If you have any doubts feel free to leave a comment below. :slight_smile:
[1]: CodeChef: Practical coding for everyone
[2]: CodeChef: Practical coding for everyone
[3]: https://discuss.codechef.com/upfiles/REDBLUE.jpg
[4]: CodeChef: Practical coding for everyone

25 Likes
2

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
3

A very elegant solution indeed!

2 Likes
4

Too nice to be a solution! Awesome editorial.

2 Likes
5

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

2 Likes
6

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
7

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

8

Awesome thinking and implementation indeed!!

9

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.

10

thanx dada:)

1 Like
11

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
12

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

13

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.

14

thank you :slight_smile:

15

@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.

16

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.

17

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
18

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:

19

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 ?

20

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