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

Binary search gives TLE :(
Автор Mohamed_Saad62, история, 4 года назад, По-английски

AT this problem https://codeforces.net/gym/102470/problem/A (short statment below)
after three days of coding to avoid runtime error I get TLE on a binary search solution can someone explain what is wrong with my solution

the short statement : You are given set of points (x,y) find point on (y = 0) which all point can go to this point in minimum time and all have the same speed which is one meter per second

my code : https://codeforces.net/contest/1445/submission/98270485 (the code has comments :)

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

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

I haven't really look at the code yet, but when I run the sample test case on my laptop it gets WA in 46ms

Here's what it printed:

1.49999986 1.50000014
-0.00000018 0.00000018
0.99999991 5.00000006
3.13636363 7.13636364

Hope this helps.

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

    I have submitted that code and I passed from the samples and got TLE on second test case the errors here are less than 10 ^ -5 that's why it passed

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

Generate a big random test and use it to measure the improvements of your code.

Here are some promising directions:

  • sqrt() is expensive, avoid calling it too often
  • You are using a flag for early exit from the last of the three inner loops. Instead you could use a single loop with early exit
  • Adjust the number of iterations of your outer loop
  • Denormal numbers are slow, be careful near zero
  • Check that input/output is fast enough
→ Ответить