×

# URBANDEV WEAK TESTCASES

 0 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 4★yb4singh 121●5 accept rate: 0%

 10 @yb4singh 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 4★anshal21 606●8 accept rate: 7%
 4 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). answered 14 Nov '16, 19:13 7★ceilks 1.8k●9 accept rate: 36%
 0 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 6★zscoder 628●13 accept rate: 6%
 0 hey anshal go to this link , your soln is giving tle answered 14 Nov '16, 18:57 4★yb4singh 121●5 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,386
×720
×161
×17
×2

question asked: 14 Nov '16, 18:40

question was seen: 1,057 times

last updated: 14 Nov '16, 19:13