tracyhenry's blog

Problem C of Beta round #60 --- interesting EPS
By tracyhenry, 14 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

14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
I've got AC with 1e-12, so it's depending
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Yes, you must use 1e-11 or smaller
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Your name is the same as the nickname of the author of this blog.
      And you are both from Nankin.
      It seems a bit strange.
      What's the story behind your nicknames?
      Did you change names in cycle? lol
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Look at the bottom of this thread and you can guess that both IDs belong to the same person.
        → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        You can find answer at the bottom of this page.
        → Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
All of my hate eps-depending probs! ]:->
→ Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
I used eps = 1e-10 and got accepted
→ Reply
14 years ago, # |
  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
14 years ago, # |
  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
  • 14 years ago, # ^ |
      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
  • 14 years ago, # ^ |
      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
14 years ago, # |
  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
14 years ago, # |
  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
14 years ago, # |
  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
  • 14 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it
    Go your sister
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      ...I just read your solution...and ..it's very unrobust.....why don't you just do binary-search in global but in local?it's more easier to make mistake and the eps-problem will arise on boundary...
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it -11 Vote: I do not like it
        Unrobust your sister. 
        Using eps is a good habit. 
        The limit of precision of this problem is too tight. 
        → Reply
14 years ago, # |
  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