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

Uncertainity with doubles
Автор lordsaitama, история, 4 года назад, По-английски

I was solving the problem 198A - About Bacteria and did a submission 81944790 and got wrong answer on case 77 I saw someone's submission which was exactly same with the only difference being the handling of the log expression 81942702 I really cant understand if I have two double a,b; how is log(a) - log(b) different from log(a*1.0/b)

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

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

Auto comment: topic has been updated by lordsaitama (previous revision, new revision, compare).

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

Simple: don't use doubles. Especially for this sort of problem where there is a difference between < and <=.

You can avoid doubles in this problem with some algebra. There's also a solution that uses a particularly clever observation and thus skips most of the algebra.

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

    I couldn't comprehend how that solution worked Can you explain a bit

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

      If you mean the particular solution you gave that does use doubles, I can't tell you. Floating point error analysis is a rather narrow field of study that I'm not trained in.

      If you mean the observational solution... the editorial contains the details, though the English has some issues (as is typical of older editorials). The observation is that if you consider the sequence of the first experiment, $$$a_0 = 1$$$, $$$a_i = a_{i-1}k + b$$$ (note $$$a_n = z$$$), then every starting value in a segment denoted by $$$[a_i, a_{i+1})$$$ takes exactly $$$n-i$$$ steps to reach a value $$$\geq z$$$.

      So you only need to find out which segment $$$t$$$ belongs to by generating the first members of sequence $$$a$$$.

      → Ответить