object_oriented_program's blog

Getting TLE in solution which should pass
By object_oriented_program, 9 years ago, In English

I tried this sum and implemented a O(n2) solution, which should pass given n < 2000 , but it doesnt.. any explanations why ?

solution

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Range is working slow. So for solution on python requre more advanced approaches. Also you can reduce search diapason, enough iterate one coordinate quartal for each vertex.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    or just replace cpython with pypy, because in this case (lots of arithmetic operations) pypy is much faster. Tried to launch object_oriented_program's solution with test 935 938:

    python 2.7 — 1500 ms
    pypy 2.5 — 77 ms

    i.e. 20 times faster.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Greetings. Your solution is 2000**2 + 2000*2 which is 8*10^6 operations. Python can hardly make more than 7*10^6 operations per second, so your solution must be just above the threshold of 1 second.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can simply iterate over  < 0, a >  not  <  - a, a >  and if you get match, add (i, j) and (i,  - j) Also, count once and keep a * a, i * iandb * b in separate variables.

→ Reply