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

×

URBANDEV WEAK TESTCASES

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

4★yb4singh
1215
accept rate: 0%

edited 14 Nov '16, 19:00


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 .

link

answered 14 Nov '16, 18:54

anshal21's gravatar image

4★anshal21
6068
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

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).

link

answered 14 Nov '16, 19:13

ceilks's gravatar image

7★ceilks
1.8k9
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

link

answered 14 Nov '16, 18:52

zscoder's gravatar image

6★zscoder
62813
accept rate: 6%

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

link

answered 14 Nov '16, 18:57

yb4singh's gravatar image

4★yb4singh
1215
accept rate: 0%

edited 14 Nov '16, 18:57

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,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