TRIQUERY - Editorial

editorial
, , , ,
3

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

4

Why TLE? CodeChef: Practical coding for everyone

5

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
6

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
7

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
8

very nice editorial :slight_smile:

9

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?

10

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?

11

Excellent editorial and tester’s solution.

12

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

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

14

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

15

I meant how to manually create such a test file.

16

Setter nice and clear solution!

17

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; }
18

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

19

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.

20

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
21

thank you.

22

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.

2 Likes