TRIQUERY - Editorial

Problem Link:

Practice

Contest

Difficulty:

Medium

Pre-requisites:

line-sweep, rank-query DS

Problem:

Given N points (Xi, Yi), and Q queries (x, y, d), find for each query how many of the N points lie within or on the boundary of the triangle formed by the triangle A(x+d, y), B(x,y), C(x,y+d).

Explanation:

This problem is solved by offline processing of the queries and using a line-sweep. Unlike most line-sweep problems, where you would sweep a (vertical) line across the X-axis (or a horizontal line across the Y-axis), and keep an active set etc, in this problem, you sweep a line of the form “x+y=c” across the plane. (Note that the slope of the hypotenuse of our query-triangle is parallel to such a sweep-line and hence the motivation for such a choice).

Query Triangle
In the figure shown, we want to find the number of points in or within the boundary of L2, B and G. If we are processing lattice points in the plane in order of sweep-line, and have so far seen points below L2, we just need to remove from this set of seen points, the ones that are below G or to the left of B.

This suggests that we have an active set of “seen points”, wherein at time T, their X+Y <= T (i.e. T defines our sweep-line). From this set of seen points, we want to remove those whose X <= x, or whose Y <= y. If we store the seen points in 2 Binary Indexed Trees (BIT): one for their X coordinate, one for their Y coordinate, and query for how many points <= x, or <= y, then using principle of inclusion-exclusion, we get that the required answer = Total seen points - num(points left of B) - num(points below G) + num(points left of B and below G).

How do we find num(points left of B and below G)?

The answer lies in the line L1. When our sweep-line was at L1, we have: Total number of points seen so far = points either left of B or below G. Again by Inclusion-Exclusion, we have Total points seen so far = num(points left of B) + num(points below G) - num(points left of B and below G). From this, we can calculate num(points left of B and below G).

Thus, our algorithm is as follows:

For each of the N lattice points (X, Y), associate an event “Add (X,Y) to active set at time point X+Y”.

For every query (x, y, d), associate 2 events. Event 1 is: “Find num(points having X<=x and Y<=y) at time point x+y”.

Event 2 is: “Answer required query at time point x+y+d”.

Lets call the first kind of event as “Add point” event, the second kind of event as “L1-type” event, and the third kind as “L2-type” event.

Finally, care has to be taken to ensure that we include the boundary of our triangle formed by B, G, L2. This is done by breaking ties of time-point in the manner of L1-type event comes before any Add-point event which comes before any L2-type event.

Setter’s Solution:

Can be found here

Tester’s Solution:

Can be found here

9 Likes

I tried to solve this in online mode:

i stored count of points on different lines parallel to x+y=0

on query of (x,y,d) we can find points to the left of B and below G (as used in editorial) by using two segment trees.

each segment tree is built with (level,x) and (level,y) correspondence (level is line no. with respect to x+y=0)

i couldn’t get rid of RTE in my submission but is this method good enough for this problem…??

1 Like

Could somebody please tell me what do we mean by offline processing of points?
And also why was I getting a runtime error in my code
http://www.codechef.com/viewsolution/1802839

Why TLE? CodeChef: Practical coding for everyone

Can’t this problem also be solved by doing an orthogonal range search in 3 dimensions (between (x, y, x+y) and (x+d, y+d, x+y+d)) using range trees or kd trees?

Something like this CodeChef: Practical coding for everyone (kd-tree, TLE, Complexity is q*(n^2/3))

Range trees with fractional cascading could solve this in O(q*((log(n))^2))

3 Likes

Is there any other simple to implement data structure for rank-query other than balanced BST if the range of value is 10^9 ?

2 Likes

I do not get this part in the setter’s solution, please help:

int comp_pt(pt A,pt B) // For sorting points by their diagonal
{
	return A.x+A.y<B.x+B.y;
}

sort(pts,pts+n, comp_pt);

Explain this part and I will try to understand the remaining things.

1 Like

very nice editorial :slight_smile:

Could somebody explain me the update and read functions in the tester’s solution?

I couldn’t get this line

void update(int idx,int val,int x)

{
while (idx <= maxn) tree[x][idx]=(tree[x][idx]+val),idx += (idx & -idx);
}

What is the meaning of idx&-idx?

Could somebody help me with the editorial?
Somebody explain me the update and read functions in the tester’s solution?

I couldn’t get this line

void update(int idx,int val,int x)

{ while (idx <= maxn) tree[x][idx]=(tree[x][idx]+val),idx += (idx & -idx); }

What is the meaning of idx&-idx?

Excellent editorial and tester’s solution.

Your solution has complexity O(N * Q). Obviously it will get TLE.
Did you ever try to run your solution with N=3e5 and Q=2e5?

@code_master01 I tried same logic too I am getting RTE too :(…

How to run it with N=3e5 and Q=2e5?

I meant how to manually create such a test file.

Setter nice and clear solution!

This is the code for manually creating a test file

#include<iostream>
#include<cstdio>
int main()
{printf("300000 200000\n");
for(int i=1;i<=500;i++)
{for(int j=1;j<=600;j++)
 printf("%d %d\n",i,j);}
for(int i=1;i<=200000;i++)
printf("%d %d %d\n",i,i,i);
return 0; }

then direct the output of this program to the input of ur program.
where input.txt is text file generated from the above code.
./a.out <input.txt

Hey Jas, not like this. I know the direct(./a.out < input.txt) thing, but I want huge random tests. Not in a serial order like this.

sort(pts, pts+n, comp_pt), means sort the array “pts” from pts[0] to pts[n], using comp_pt() as the compare function.

Since the sweep line is of the form x+y=d, all the points lying to the left of the sweep line have x+y < d and all points to the right have x+y > d. So having all the points sorted w.r.t “x+y”, gives a quick way to eliminate points.

1 Like