Mohamed_Saad62's blog

Binary search gives TLE :(
By Mohamed_Saad62, history, 4 years ago, In English

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

  • Vote: I like it
  • +6
  • Vote: I do not like it

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

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.

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

    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

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

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
→ Reply