Блог пользователя object_oriented_program

Getting TLE in solution which should pass
Автор object_oriented_program, 9 лет назад, По-английски

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

solution

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить