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

×

URBANDEV query about the idea

2
1

What is the idea of this problem? Can anybody discuss in detail.

asked 14 Nov '16, 21:22

a____'s gravatar image

0★a____
7911
accept rate: 20%


just Iterate through every y from 1 to 10^5 and keep the record of live vertical lines for current y and find the answers for the horizontal lines whose y value is equal to current y with range query on the array keeping record of live vertical lines .
Now repeat same thing for the vertical lines , this time iterate over x and find the answers and in the end sum up all the answers.
now find the number of corner points and subtract them from total answer. you can use BIT or segment-tree for the range query , rest is simple implementation.
P.S. for reference you can see this code , I used BIT for the range query.

link

answered 14 Nov '16, 21:42

anshal21's gravatar image

4★anshal21
6068
accept rate: 7%

You don't have to repeat same thing for vertical lines, swaping (x,y) and then doing same function will do.

(14 Nov '16, 21:53) nidzulandz6★

yeah! pretty much same thing :P

(14 Nov '16, 22:04) anshal214★

You have to also keep in mind the segment thing? How are you gys coping with that?

(14 Nov '16, 22:25) a____0★

if you encounter a left endpoint of a line segment , add it to your data-structure , if you encounter a right endpoint , remove it .

(14 Nov '16, 23:04) sarvagya39434★

just as sarvagya said , keep the track of ends

(14 Nov '16, 23:22) anshal214★

and we are using 2 scan (vertical and horizontal) coz we need to get it for each of the lines. Please verify?

(15 Nov '16, 01:36) a____0★
showing 5 of 6 show all

https://www.youtube.com/watch?v=dePDHVovJlE/ You can go through this video.Then,you can see its implementation in my code(using Segment tree)https://www.codechef.com/viewsolution/12087104

link

answered 14 Nov '16, 22:12

shukrant's gravatar image

4★shukrant
1214
accept rate: 22%

edited 14 Nov '16, 22:35

2

nice video.

(14 Nov '16, 22:36) diveshuttam3★
2

@shukrant.: From vid it is clear that complexity = O(nlogn+R) ..R is O(n^2)...how come it is O(nlogn+R) ?How does hat R part come?

(15 Nov '16, 01:06) a____0★

R is used for reporting all the intersections in any segment.We does not require this.

(15 Nov '16, 18:15) shukrant4★

topcoder has a tutorial talking about this and similar problems..The basic idea is called line sweep algorithm. https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/

link

answered 14 Nov '16, 22:10

diveshuttam's gravatar image

3★diveshuttam
53718
accept rate: 27%

edited 14 Nov '16, 22:13

You can also use square root decomposition for range queries in this problem. My code: https://www.codechef.com/viewsolution/12042756

link

answered 14 Nov '16, 22:49

anupam_datta's gravatar image

4★anupam_datta
469529
accept rate: 7%

First read about sweep line algo.U can understand it from this http://www.youtube.com/watch?v=dePDHVovJlE

U can see in the video that the complexity is O(Nlog N)+R where R is the number of intersections. Suppose you have x horizontal and y vertical lines,maximum number of intersections will be x * y(This is similar to selecting 1 horizontal line and 1 vertical line).U can find maximum number of intersection using A.M>=G.M rule which will be (N * N)/4. Hence just by using Sweep Line algorithm the complexity becomes O(Nlog N)+O(N * N) which is same as O(N * N) which results in TLE.U can refer to this code which got TLEs in 2nd subtask

Code : https://www.codechef.com/viewsolution/12084739

Now what shall we do?? ;) U can easily observe that total number of intersection points is basically the sum of intersection points of each individual line divides by 2.We will use this fact to find out the answer.Basically we have to find the answer for each individual line first and then use it to find the number of intersections. Instead of iterating through all the possible values in that range we can use BIT or segment tree to find the answer in O(log N) After that we have to subtract all those points which are end points of both vertical and horizontal lines which can be done by storing those points before calculating. We have to apply sweep line algorithm once for all vertical lines and once for all horizontal lines.

This is my final code : https://www.codechef.com/viewsolution/12092468

Feel free to ask questions.Happy coding ;)

link

answered 14 Nov '16, 23:38

aloochaat1998's gravatar image

5★aloochaat1998
995
accept rate: 16%

edited 15 Nov '16, 10:45

and we are using 2 scan (vertical and horizontal) coz we need to get it for each of the lines. Please verify?

(15 Nov '16, 01:45) a____0★

Actually I am scanning once but storing the required values in a and b just after scanning the values.For calculating vertical lines I am storing the required values in struct array a and for horizontal lines in struct array b.

(15 Nov '16, 10:38) aloochaat19985★

Actually there is a almost same problem which was asked in one of the Codeforces round earlier. Just in that problem, you had to change the part regarding the cases when both the intersection occur at the boundaries. For that as per the question, we can see that at a given point maximum of 2 lines can intersect (you can prove it using contradiction: Suppose 3 lines intersect. All 3 can't be horizontal or vertical. Without loss of generality assume 2 are horizontal and 1 is vertical, then again no 2 horizontal lines also share a point. Hence, it is not possible). Thus a simply sort of all the points was enough to remove the last condition.

Here is my clean implementation of the solution. Hope the solution is clear and understandable, once the algorithm is clear.

link

answered 15 Nov '16, 00:40

likecs's gravatar image

6★likecs
3.7k2279
accept rate: 9%

edited 15 Nov '16, 00:40

and we are using 2 scan (vertical and horizontal) coz we need to get it for each of the lines. Please verify?

(15 Nov '16, 01:42) a____0★
2

Yes. You are correct.

(15 Nov '16, 02:04) likecs6★

I did the line sweep as mentioned by anshal21 but I used a modified BST instead of segment/BIT tree. Will the segment/BIT tree approach work for higher values of x and y(say 10^9) ??

link

answered 15 Nov '16, 00:42

sdssudhu's gravatar image

6★sdssudhu
1.1k310
accept rate: 15%

edited 15 Nov '16, 00:45

2

Yes, use coordinate-compression first and then it will reduce to number of points which is $2*10^5$.

(15 Nov '16, 01:00) likecs6★

yeah co-ordinate compression is a very good idea I didn't think of it initially and I thought BST was suitable as I didn't notice range of x and y.

But should we do coordinate compression twice ??

(15 Nov '16, 01:09) sdssudhu6★
2

Yes, twice.

(15 Nov '16, 02:05) likecs6★

Here is my solution with sweep line + BIT, runs in 0.25 ms, I hope this can be helpfull.

link

answered 15 Nov '16, 11:58

eteruel's gravatar image

3★eteruel
11
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:

×1,310
×66

question asked: 14 Nov '16, 21:22

question was seen: 1,712 times

last updated: 15 Nov '16, 18:16