DS = QUAD TREE Unofficial editorials December Long Challenge Part 3

Hello Guys,

This is the part 3 of three posts of Unofficial editorials for December Long Challenge.

For editorials of problems GIT01, CPLAY, and VK18, [click here][1].

For editorials of problems CHEFHAM and CHEFEXQ, [click here][2].

This post has editorials for problems REDBLUE.

I have decided to dedicated this post to a single problem because I am gonna write an editorial of a Data structure Quad Tree, followed by Editorial of REDBLUE problem.

#[Quad Tree][3]

Idea:

Quad Tree is basically an extension of a segment tree. While segment tree deals with an array (or a number line), Quad Tree deals with a grid (or X-Y plane). The whole idea of Quad tree and segment tree is same, store result for a node (known as region for quad tree), combine results of children nodes to get result of current node and so on.

In Quad Tree, each region is defined as a rectangle in following two ways.

  1. Four Integers x1,y1,x2 and y2, where (x1,y1) is top-left and (x2,y2) is bottom-right corner of given region.
  2. One Point (x,y), Two Integers H and W, Point being the center of rectangle ((x1+x2)/2, (y1+y2)/2), H denote height of rectangle and W denote width of rectangle. (Or R denoting Radius, is region is circle shaped in our scenario).

Both of above can be used in different scenarios, have their own advantages and disadvantages.

First representation is easier to use, but wont work if we need quad tree in game simulation object collision if our objects are circle shaped.

I have used First representation for solving REDBLUE, and therefore, would talk about First representation only. Second representation can also be used in a similar way.

Suppose we have a region ((x1,y1) (x2,y2)) denoting top-left and bottom-right corners of region. Now, we are going to find its children regions (or sub-regions).

if midX = (x1+x2)/2 and midY = (y1+y2)/2

Four sub-regions are

  1. ((x1,y1) (midX,midY))
  2. ((midX+1,y1) (x2,y2))
  3. ((x1,midY+1) (midX,y2))
  4. ((midX+1,midY+1) (x2,y2))

Now, we can store answers for each region and solve grid queries fastly.

Talking about Time Complexity, It’s time complexity would depend upon the type of query we need to answer. For example, we need to count number of points which lie below the line. A line may pass over two or three regions. So, we can just calculate region for fourth region in O(1) because all points in that region will lie only on one side of line.

In theory, the following Recurrence will define our time complexity.

T(N) = 3T(N/4) + O(1).

Practically, Quad Tree gives better run-time if points are sparse. I don’t exactly know the exact upper bound of time complexity of query in Quad Tree, but in no case will it be worse than O(N). Read [this][4] thread about time complexity of Quad Tree.

Note: I have tried to explain Quad Tree in a simple way, and in that process, i haven’t discussed many variations for which Quad Tree may be used. I wanted to share core idea of Quad Tree, after which you can find other variants on internet easily understandable.

The version of Quad Tree discussed above is static i.e. we don’t allow insertions of new points, but its details can be easily found on internet.

Implementation:

We are basically going to use [left-right sibling representation][5] of tree, with difference that we will have 4 children instead of usual two children.

Also, we need to visualize which child hold information of which sub-region. For example, in my solution quad tree, if origin (x,y) defines center of region, child[0] region has both co-ordinates negative, child[1] has x +ve, but y -ve, child[2] has y +ve, but x -ve and child[3] has both x and y positive. It is a matter of choice.

Suppose we are given a set of points. for every Query (no of queries <= 1e5), we are given equation of line in slope-intercept form, we need to tell number of points lying above the given line.

We will use following classes (or struct)

We will build the Quad Tree beforehand.

int[][] points denote given points.

class Point{

int x,y;

}

class Node{

Point topleft, bottomright;

Node child[4];

// Additional data for region, depending upon queries asked.

ArrayList list;//storing indices of points lying in current regions, indices pointing to points array in given input.

void build(){

int midx = (x1+x2)/2, midy = (y1+y2)/2;

for(int i:list){

if(point[i][0] <= midx && point[i][0] <= midy){child[0].add(i);

//rest three inserted in same way, explained above.

for(int i = 0; i< 4; i++)child[i].build();

}

}

}

int query (//query variables){

//required query, calling child[i].query() for some regions, calculating results of queries

int count = 0.

if(check(If given ling passes through region i))count += child[i].query(slope, intercept);

else if(check(if region lies above the line))count += child[i].

return count;

}

}

That’s all above Quad Tree, so now, we will move to problem REDBLUE.

Problem [REDBLUE][6]

Problem difficulty: Medium

Prerequisites: Quad Tree

Problem Explanation

Given two set of points (red and blue), delete minimum number of points such that we can draw a line in any direction, which divides both sets into separate regions.

Solution

Naive Solution:

First thing to note, I am assuming that points may lie on that line. (If this assumption is wrong, we can always shift a line very minutely to have a dividing line which doesn’t lie on any points and also, doesn’t affect our answer, because no three points are collinear.

Set answer to N+M.

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.

Now, we see that if this pair is the optimal dividing line, we need to delete minimum of

  1. red points lying above + blue points lying below line.
  2. red points lying below + blue points lying above line.

ans = Math.min(ans, min(red_above + blue_down, red_below+blue_above));

print answer. The time complexity of above solution is O(N^3), giving us 20 points.

See this solution [here][7].

Now, See what we are doing. For every pair, we develop a line using two point form of line, and count number of points lying above and below the line. We also wee that number of points below line = Total points - number of points above line - 1 (point lying on line).

So, for every line, we just need number of red points and blue points above the line.

This is where the quad tree comes into picture. We will build two quad trees, one for red points,a one for blue points. We will just run two nested loops(one on red, one on blue), form a line for every pair of point, and use quad tree to answer queries, and print the answer.

Link to my


[8].

Please share your views about my editorial, especially about Quad Tree since this is my first tutorial of a data-structure.

Enjoy coding. 


  [1]: https://discuss.codechef.com/questions/119321/unofficial-editorial-december-long-challenge
  [2]: https://discuss.codechef.com/questions/119323/unofficial-editorials-december-long-challengr-part-2
  [3]: https://en.wikipedia.org/wiki/Quadtree
  [4]: https://stackoverflow.com/questions/39477561/complexity-of-quad-trees-range-search
  [5]: http://btechsmartclass.com/DS/U3_T2.html
  [6]: https://www.codechef.com/problems/REDBLUE
  [7]: https://www.codechef.com/viewsolution/16452230
  [8]: https://www.codechef.com/viewsolution/16462606
7 Likes

RED BLUE

I used the radial sweep + binary-search approach to solve this problem.

  1. Do a simple angular sweep from from all the points and count how many red and blue balls are on one side of the line. Once you know the count of red and blue balls on one side of the line, you can minimise the count of deletion.

  2. Sorting the points using atan2l function will create problem, so sorting the points based on the quadrants in which it lies with respect to the point.

  3. If the line passes through 1st and 3rd quadrant, then use binary search to count the number of points under the line in the first quadrant, and the number of points above the line in the 3rd quadrant, and add the add the count of red and blue balls in the 4th quadrant.

  4. Consider point (x1, y1+delta1) and point (x2, y2-delta2).

now the line (y-y1+delta1)/(x-x1) = (y2-delta2-y1)/(x2-x1) will not have integer values to satisfy the equation. So, its safe to consider that the above line passes just above the point(x1,y1) and just below the point (x2, y2), and not intersection any other integer points in the plane.

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

1 Like

@skyhavoc I used radial sweep too, but what did you binary search on? I just sorted other points about a central point using relative slopes, and then looped through the points, adding and removing them from a segment depending if they were on the right or left side of the line parallel to the x-axis passing through my central point

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

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

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.

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

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?

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

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

Nice Editorial :slight_smile:

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 )

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

Maybe we can even teach each other… :smiley:

I too implemented Quad Tree for the first time.

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

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

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.

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

see my comment there

1 Like

sure why not