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



I copied some of the AC solution (anshal21) and tested on ideone with the test case n=10^5 and n/2 horizontal lines and n/2 vertical lines making a grid with all line segments of maximum possible length. All the solutions are giving TLE or Runtime Error. And when I tested those solutions for n=10^3 or n=10^4, they are working successfully. I researched about this topic on the internet and the best algorithm I found for this was Sweep Line Algorithm and it's time complexity is stated as O(nlogn+k) where k = number of intersection, which in my test case in n^2/4, so this makes it as a O(n^2). And as the constraints are n=10^5. n^2 cannot run in the given time limit.

asked 14 Nov '16, 18:40

yb4singh's gravatar image

accept rate: 0%

edited 14 Nov '16, 19:00


you are completely wrong, first of all the complexity of my solution does not depend on the number of intersections
If you copied my solution, better analyze it before testing it, the complexity of the solution is of order (nlogn +n) , get your basics clear man.
And one more thing try to solve problems by your self don't rely on internet every time , you find sweep line algorithm doesn't mean that's the only solution.
Man better invest your time in solving questions instead of blaming the testcases and searching on the net.
see other's solutions or wait for the editorial, you will get it .


answered 14 Nov '16, 18:54

anshal21's gravatar image

accept rate: 7%

My solution is $O(n\log(n))$, I guess most of the others too. Maybe the sweep line algorithm you are referring to has the intersection points as output (then you have to actually all intersections which is obviously at best linear in the number of intersection). We just have to count, which can be done in $O(\log(N)$ per segment using a BIT/Segment tree.

As to the "grid testcase": I ran my solution locally on the case generated by

print N
for i in range(N/2): print i+1,1,i+1,N/2
for i in range(N/2): print 1,i+1,N/2,i+1

It ran in 0.1s. Codechef servers are typically slower by a factor of 2 or 3, stilll way lower than 1s. I'm not arguing that my solution is optimal written wrt. runtime (is could definitely be improved) but I figured it would be fast enough for codechef. Maybe your testing enviroment is way slower (possibly concerning I/O).


answered 14 Nov '16, 19:13

ceilks's gravatar image

accept rate: 36%

edited 14 Nov '16, 19:13

I'm quite sure my solution works in $O(n\log n)$ and does not depend on $k$. I also used a sweep line.

Solution Link


answered 14 Nov '16, 18:52

zscoder's gravatar image

accept rate: 6%

hey anshal
go to this link , your soln is giving tle


answered 14 Nov '16, 18:57

yb4singh's gravatar image

accept rate: 0%

edited 14 Nov '16, 18:57

toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 14 Nov '16, 18:40

question was seen: 1,057 times

last updated: 14 Nov '16, 19:13