Lazers Everywhere DIV2

general
1

Hey Guys, I would like to know your approaches to the problem LAZER. I solved it using merge sort tree and fenwick tree.Here is my approach:
https://www.codechef.com/viewsolution/30390799

2 Likes
2

If someone solved it using Segment tree, please share approach :slight_smile:

1 Like
3

You can have a look at above, Merge sort tree is a type of segment tree which just stores sorted intervals at its nodes instead of points/numbers as keys.

1 Like
4

I have created a video solution.
You can find it here : LAZER solution - Codechef March Long Challenge 2020 - YouTube

1 Like
5

I wrote a code using segment tree, but got TLE in one of the cases in subtask 2.
I think it is because of function calls.But Fenwick tree worked(don’t forget to use ‘\n’ instead of endl ).
Here is my code using segment tree: CodeChef: Practical coding for everyone
my code using Fenwick Tree : CodeChef: Practical coding for everyone

6

thanks mate :slight_smile:

1 Like
7

sure :slight_smile: nice approach

1 Like
8

I had the same problem using only Segment tree, Got TLE in same test case you :p. Then had to combine it with BIT to lower down time.

Only Merge Sort tree code: CodeChef: Practical coding for everyone
BIT+merge sort tree:CodeChef: Practical coding for everyone

9

i have used (using two references: https://www.geeksforgeeks.org/number-of-intersections-between-two-ranges/ and Kth smallest element in a subarray - GeeksforGeeks) but failed to score 70% … one subtask got TLE (2.01xxx) … i have seen a comment which says BIT can solve this… so i want 2 know whether it’s possible to convert every segment tree based approach to BIT?

10

Visualization: Imagine a vertical line falling from y = infinity
Precomputation: Arrange all lazers and queries in a single queue in decreasing order of y co-ordinate.
Solution: When the falling vertical line hits a lazer at x = i, y = A[i], update seg tree from (i-1, A[i-1]) to (i+1, A[i+1]) with relevant addition or subtraction.
When you hit a query, just get the solution :dancer:

1 Like
11

Welcome to the community! Yes as far as point updates are concerned (Eg: given A[L…R] count zeros/find sum) etc…BIT and segment tree can be interconverted.As far as analysis of intervals and consequent queries are concerned (Eg Merge sort tree/Interval tree/Wavelet tree) using segment tree is efficient. For example : " There is no easy way of finding minimum of range [l,r] using Fenwick tree, as Fenwick tree can only answer queries of type [0,r]".(Quoted in Fenwick Tree - Algorithms for Competitive Programming) You need to use 2 BITS here and read some research paper to solely solve it using a BIT and trust me it will be cumbersome.

13

Nice approach…You are directly storing the counter as key in the segment tree right?

14

can we use line segment orentation to solve atleast first subtask of the problem

15

For the first subtask you can use simple quadratic equation : with condition :
(y-a[i])(y-a[i+1])<=0 for i belonging from [x1,x2). This is the necessary and sufficient condition for a line y to intersect a segment between (i,a[i]) and (i+1,a[i+1]). Just think, for intersection we need both points on opposite sides of the line, so difference in heights of line segments should be negative…simple brute force approach : (y-a[i])(y-a[i+1])<=0 :slight_smile:
Here is the link: CodeChef: Practical coding for everyone

16

I used Segment Trees for solving the problem .However it was required to do small small optimizations to get AC in all tasks like using postfix operators etc.
MY C++ SOLUTION : Online Compiler and IDE - GeeksforGeeks

1 Like
17

My approach is fairly simple and I believe somewhat different than many others.

  1. Observe that # of intersection in range [x1, x2] for some y will be as equal as
    no. of intersection from [0, x2] - no. of intersection from [0, x1] for same y.
    Let first part be ans2 and second part be ans1. We will maintain both answers for each query.

  2. Now we will move from 0 to n along x-direction. For each increment in i, a new segment
    having endpoints (i-1, y1) and (i, y2) will get added.

  3. Maintain an array for y values and increment range [y1, y2] by 1, cuz for any ‘y’ belonging
    to range [y1, y2] there will be an intersection from now onwards as we are considering lazer to be fired from y-axis i.e x = 0. Calculate ans1 and ans2 for queries starting and ending at current i respectively.

  4. But, 1 <= y <= 1e9 which doesn’t allow to range increment and query on y. But their can be at most 2*n distinct values of y (n from given + n from queries). For that I compressed values of y using coordinate compression and always used mapped values of y whenever needed.
    my solution

4 Likes
18

Yes its different and more efficient I guess.

1 Like
19

Yes your approach is really awesome!

20

But can you elaborate what ans1 and ans2 does?

21

The link is not your approach but your code. If you are sharing it as your approach then at least include the comments in your code.

1 Like