You are not logged in. Please login at www.codechef.com to post your questions!

×

TRIQUERY - Editorial

9
6

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

This question is marked "community wiki".

asked 12 Feb '13, 18:20

pragrame's gravatar image

6★pragrame ♦♦
973568379
accept rate: 14%

edited 12 Feb '13, 19:16

Setter nice and clear solution!

(14 Feb '13, 18:20) prakhs1234★

I have a problem here: -->"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."<-- I think if L1 sweep means all the points below this line in the diagram then it is "not" equal to the "points on the left of B or below G" because there can be some point b/w L2 and L1 and on the left of B which are not covered by L1 sweep. same for b/w L2 and L1 and below G. please clarify. Please also clarify the definition of line-sweep.

(23 Feb '13, 12:46) ashishnegi0013★
1

got it. :) For this part of problem (refer above comment), it is a completely new BIT which is calculated from points and queries sorted by their x coordinate. see Setter's solution for clarification.

(23 Feb '13, 13:02) ashishnegi0013★

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 http://www.codechef.com/viewsolution/1809831 (kd-tree, TLE, Complexity is q*(n^2/3))

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

link

answered 13 Feb '13, 07:06

ishanbhatnagar's gravatar image

5★ishanbhatnagar
8502614
accept rate: 21%

edited 13 Feb '13, 14:35

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

link

answered 12 Feb '13, 21:47

code_master01's gravatar image

5★code_master01
1.1k132229
accept rate: 0%

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

(13 Feb '13, 12:11) amitupadhyay2★

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

link

answered 14 Feb '13, 18:56

smithinsu's gravatar image

5★smithinsu
1056
accept rate: 0%

edited 14 Feb '13, 19:24

2

One generally maps your range of 10^9 values to O(10^5) actual values. (Use a STL map or set or something). The mapping should only preserve ordering of elements.

For example, if your input (into your BST) was 5, 10, 10^7, then first make the mapping 5 -> 1 10 -> 2 10^7 -> 3 and use just these mapped values in your BIT.

(17 Feb '13, 03:51) pragrame ♦♦6★

I thought of this . but suppose we want to do online processing of queries .

(20 Feb '13, 20:56) smithinsu5★

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

link

answered 12 Feb '13, 23:12

jaskaran_1's gravatar image

3★jaskaran_1
525233550
accept rate: 0%

1

offline mode means that you "don't" calculate your answer of every input query separately but either you do some preprocesing before taking input or you take all the input and find answer to the all queries at the same time. [here same time means like you are going though the input queries and finding "half" answer to some queries and then coming back again and again]

(23 Feb '13, 12:35) ashishnegi0013★
link

answered 12 Feb '13, 23:25

bugkiller's gravatar image

3★bugkiller
8.7k194898
accept rate: 9%

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?

(13 Feb '13, 00:58) anton_lunyov ♦6★

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

(14 Feb '13, 17:39) bugkiller3★

I meant how to manually create such a test file.

(14 Feb '13, 17:54) bugkiller3★

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; }
(14 Feb '13, 21:19) jaskaran_13★

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

(14 Feb '13, 21:22) jaskaran_13★

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.

(14 Feb '13, 22:13) bugkiller3★
showing 5 of 6 show all

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.

link

answered 14 Feb '13, 23:06

bugkiller's gravatar image

3★bugkiller
8.7k194898
accept rate: 9%

1

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.

(16 Feb '13, 22:43) prakash15293★

thank you.

(16 Feb '13, 23:20) bugkiller3★

very nice editorial :)

link

answered 24 Feb '13, 10:34

selfcompiler's gravatar image

3★selfcompiler
10127
accept rate: 0%

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?

link

answered 25 Jun '13, 15:42

jaskaran_1's gravatar image

3★jaskaran_1
525233550
accept rate: 0%

edited 25 Jun '13, 15:43

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?

link

answered 25 Jun '13, 23:28

jaskaran_1's gravatar image

3★jaskaran_1
525233550
accept rate: 0%

its idx&-idx the bitwise AND operation between idx and its negation

(25 Jun '13, 23:43) sparshgunner124★

Thanx @sparshgunner12. I finally understood whats happening.

(26 Jun '13, 19:39) jaskaran_13★

Excellent editorial and tester's solution.

link

answered 26 Jun '13, 19:39

jaskaran_1's gravatar image

3★jaskaran_1
525233550
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,682
×2,595
×78
×13
×3

question asked: 12 Feb '13, 18:20

question was seen: 7,736 times

last updated: 26 Jun '13, 19:39