tracyhenry's blog

Problem C of Beta round #60 --- interesting EPS
By tracyhenry, 15 years ago, In English



My program :
Eps = 1e-8, 1e-9   ---> wa on test 29
Eps = 1e-10        ---> wa on test 39
Eps = 1e-11        ---> Accepted
Eps = 1e-12        ---> Time Limit Exceeded because of binary search

Did you get wa on test #29 or #39?

Change your eps to 1e-11 and try again!~~~~


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

15 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it
I've got AC with 1e-12, so it's depending
→ Reply
15 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it
All of my hate eps-depending probs! ]:->
→ Reply
15 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it
I used eps = 1e-10 and got accepted
→ Reply
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
I also got AC with EPS = 1e-11.
I think that the analytical approach is desired.
→ Reply
15 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it
It is better to write binary search with fixed number of iterations.
50 will be enough for any case. It will save you from TLs and WAs.
→ Reply
  • 15 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it
    Hmmm i have never used such way of binary search. Is not it better to count approx lg2 of  right bound+eps?
    → Reply
  • 15 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    I beleive that 50 iterations isn't always enough. Number of iterations should be approximately log2(bounds/precision). Say, initially we search answer from -10^10 to 10^10 and we need precision 10^-10, so we will need about log2(2*10^20)~68 iterations. Well, such tight limits are quite unlikely, but the point is that the number of iterations is not limited with 64 just because double is 64-bit. I had a situation when I didn't get AC with 60 iterations, but did with 80.
    → Reply
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
I set EPS = 1E-15. Binary search can be called only once when the two curves are intersected so it wouldn't cause TLE.
→ Reply
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
I used EPS = 1e-9 during the contest and got AC. After switching to EPS = 1e-6, I still get AC. It's better to avoid EPS (as much as possible) in these problems than to choose a correct EPS :)
→ Reply
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
..actually I didn't used eps and get AC...I think your solution is not very robust
 >_<。。
the best way to use eps is not use eps >_<。。。。
→ Reply
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
...and I bs that you always use your small-id to solve CF >_<。。。。。
→ Reply