GrizzlyGunner's blog

Weird Floating Point Behaviour in #730 Div. 2's Problem C (Need for Pink Slips)?
By GrizzlyGunner, history, 3 years ago, In English

Doubt in #730 Div. 2's Problem C (Need for Pink Slips):
Can someone please explain why 1e-10 works in the below line of a solution to Problem C, but 1e-9 doesn't?
Shouldn't they both work?

if(p * level * prob <= 1e-9) return;

The submissions: 1e-9, 1e-10.
Thanks.

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

Comments Comments (5)
| Write comment?
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Since that line of code rejects any probabilities <= to your specified value, it may cause an incremental error that causes the final answer to differ from the machine answer by 1e-6. The error seems to be large enough in the 1e-9 case for that to occur.

Btw, you don't need to reject any probabilities, since the number of possible cases is small enough for a brute force solution.

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

    Since both the values are in the safe epsilon range of 1e-6 and lower (as specified by the author), if values lower than or equal to 1e-9 led to incremental errors, shouldn't the use of an epsilon greater than 1e-9 also possibly lead to incremental errors?
    I am a total novice and error management at this level seems a bit fuzzy and arbitrary.
    My eps for all the statements other than the first one is 1e-7 for both the codes (9 and 10).

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

      I just ran your code with 1e-7 and it doesn't seem to work. 1e-7

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

        No, I meant that I am using 1e-7 as the actual eps for both the codes (1e-9 and 1e-10). In both the submissions, I am using 1e-7 in the part below the statement. it is the choice of epsilon (1e-9 and 1e-10) for the first statement that completely changes the answer.
        So, if incremental errors at the level of 1e-9 sometimes lead to a change in the answer, how is it that an epsilon of 1e-7 or even 1e-6 is able to work?

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

          Oh, ok. Sorry for misunderstanding. The epsilon used in the part below is necessary because you are comparing whether c or m values are equal to v. Because of floating point error, situations may arise where you have c — min(v, c) = 1e-16 instead of 0 and create a false positive. So that epsilon (which can be between 1e-6 to 1e-12) is needed to perform the equality operation, which does not contribute to the final answer.

          The first statement, however, causes an incremental error because it outright rejects some probabilities, which is incorrect. There are many sequences that have probability < 1e-9 due to their length, and these cumulatively added up to an error over 1e-6.

          → Reply