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.
- Four Integers x1,y1,x2 and y2, where (x1,y1) is top-left and (x2,y2) is bottom-right corner of given region.
- 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
- ((x1,y1) (midX,midY))
- ((midX+1,y1) (x2,y2))
- ((x1,midY+1) (midX,y2))
- ((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
- red points lying above + blue points lying below line.
- 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
