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.
I’m quite sure my solution works in O(n\log n) and does not depend on k. I also used a sweep line.
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 .
5 Likes
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
N=100000
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).
2 Likes