DS = QUAD TREE Unofficial editorials December Long Challenge Part 3

editorial
,
4

@taran_1407 Very nice post on QUAD tree.

But I also did radial sweep + sorting with relative angles(atan2). The problem’s limit on n allowed O(n^2) soltuion.

5

I also did the same ,except i used binary search to count number of points.
For all points ,find the angle from this point to red points and store them in an array,similarly do for blue points.
Sort the array.

Then for every pair ,find angle - lets say x,binary search for x and x+180 in red array and blue array to get no. of pts.

For handling cases for which x>180,i actually store angl,angl+360,(i also save ang+720 bt its not required) in those array.

My solution:
https://www.codechef.com/viewsolution/16511611

6

Radial sweep seems like a really popular idea here, but unfortunately, I have no idea what radical sweep is. So silly of me… :slight_smile:

I think I’ll have a peek at all this solutions.

Thanks to you all for sharing your solutions.

7

@taran_1407 in the solution we are considerng only those lines which can be formed from two given points but can you please explain me how does it guarantees that our required answer will be from one of these lines?

8

So, Simple solution is to select one point from red points, select one point from blue set and for every pair of red point and blue point, form a line, count number of red points lying above the line, below the line, number of blue points above the line and below the line.

I can’t understand this. How to prove that an optimal line can be transformed(translated+rotated) to pass through exactly one red and one blue point without changing number of mismatch?

9

@taran

taran if you got some time , can you tell me how to get to the solution of second condition of (x+y)>=z
in the CHEFUNI question on which @SOHAM did the editorial , i read your comment in the section of that editorial but still not got reasoning how to get the solution to that condition . i have not got karmas to ask that in forum.

10

Nice data structure
I simply tried to convert your java code into c++ @taran_1407 but TLE occurred. Here is my


[1]. Why did it happen?


  [1]: https://www.codechef.com/viewsolution/16691675
11

Nice Editorial :slight_smile:

12

for a particular point I sorted the rest of the points for each quadrant. So, for a line( say passing from 3rd and 2st quadrant) I need two binary search on two quadrants(1st and 3rd) and adding the values(count of balls) of the quadrants which lies between the quadrant( 2nd or 4th )

13

and i didnt know about the Quad tree. thanks for the editorial

14

Maybe we can even teach each other… :smiley:

I too implemented Quad Tree for the first time.

15

I don’t understand point 2, what problem does atan2 create? If you are talking about negative angles, then you can just add 360 to the negative angles to get them in positive value. I used sliding window approach after sorting angles w.r.t each point.
My implementation : link

16

Oh, that’s smart! I should’ve thought of that.

17

i hope you understood why atan2l (more precision, but not enough) is used here - to compare the two points angular wise with rest to a given point. I have sorted the the points from [-pi to pi].

For small values of (x,y), the angles calculated with atan2 will be comparable, but with large values of x and y you will face problem.

Try finding angles of point (1e9, 1e9) and (1e9, 1e9-1) using atan2.

18

Thank you for pointing this out. Weak TCs! My solution shouldn’t have passed then.

19

see my comment there

1 Like
20

sure why not

21

First of all, try running O(N^3) solution on sample test case.You will find, that if you calculate redabove and then calculate red_below = red_above, answer wouls come out to 3 as per solution, but when excluded the point lying upon line, answer reduced to 2, which is correct. (Problem statement didn’t clarify that).

From there, i can to know that points may lie on dividkng line.

22

Suppose we have a line not passing through any red or blue points, and we have calculated answer for this line.

Now, you may try shifting/rotating or both, on this line. You will notice that as long as the line doesnt move over any point, result would remain the same. Got that?.

So this imply we can consider all possible results just by considering lines joining one red point wuth a blue one.

23

Not sure what you meant to say in the first comment. Why would the exclusion of point lying on the line make the answer any better? It would be the same/worse. Worse case will only happen when 3 points can be colinear. Which can’t happen in this question.

Yeah, I understand that you can transform the line as long it doesn’t cross a point without changing the number of mismatches. This leads to that the line can pass through 2 of the original points(red+blue), but I can’t understand why one of them needs to be red and the other blue.