lordsaitama's blog

Uncertainity with doubles
By lordsaitama, history, 5 years ago, In English

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)

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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.

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

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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$$$.

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

        Thanks a ton for the help I was having issues understanding the editorial

        → Reply