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

Problem C of Beta round #60 --- interesting EPS
Автор tracyhenry, 14 лет назад, По-английски



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!~~~~


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

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I've got AC with 1e-12, so it's depending
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
I've got AC with 1e-12, so it's depending
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Yes, you must use 1e-11 or smaller
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      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
      → Ответить
14 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
:( http://cforces.reformal.ru/proj/?ia=135999

А ещё было предложение - сделать возможность быстро изменить язык комментария (и всей ветки за ним) в течении 5 секунд.

Или хотя бы предупреждение, что если весь комментарий на англ. - может язык комментария то английский?
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
All of my hate eps-depending probs! ]:->
→ Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

→ Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
I used eps = 1e-10 and got accepted
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
It depends on where you use EPS. In fact, you can write binary search without EPS in the most of geometry tasks, just make constant number of iterations.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I also got AC with EPS = 1e-11.
I think that the analytical approach is desired.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
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.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Hmmm i have never used such way of binary search. Is not it better to count approx lg2 of  right bound+eps?
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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.
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
If you compare time with eps, than you have to use 1e-11 or smaller epsilon because of following:
s = t * v;
In this problem you need to know s accurate up to 1e-6, so if v can be 10^4 (was said in statement) you need to know t with more than 1e-10 accuracy.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I set EPS = 1E-15. Binary search can be called only once when the two curves are intersected so it wouldn't cause TLE.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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 :)
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
How to avoid EPS in this problem?
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I got AC with eps 1e-6, 1e-5 and 1e-4 :)
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
..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 >_<。。。。
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится
    Go your sister
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      ...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...
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится -11 Проголосовать: не нравится
        Unrobust your sister. 
        Using eps is a good habit. 
        The limit of precision of this problem is too tight. 
        → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
...and I bs that you always use your small-id to solve CF >_<。。。。。
→ Ответить