Phantom_Dreams's blog

Can floating-point underflow cause a WA here?
By Phantom_Dreams, history, 6 months ago, In English

I recently upsolved C. Gellyfish and Eternal Violet with this submission, which resulted in an AC verdict.

But I am concerned about this part of my code:

double ans = 0, last = 1;
for(int i = 1; i <= s; i++) last *= q;
for(int i = s; i <= r; i++) {
    ans += last * dp0[r-i][max(1,m-i+s)];
    last *= p * i / (i+1-s);
}
cout << ans << endl;

Basically, last is just a probability representing the current binomial distribution: $$$\binom{i-1}{s-1}\,p^{i-s}\,q^{s}$$$.

I initially computed the probability of last with $$$i=s$$$, which is just $$$\binom{s-1}{s-1}\,p^{0}\,q^{s}$$$, before starting the second loop and transitioning it to the next value of $$$i$$$ every iteration.

What I'm worried about here is that $$$q^s$$$ can be very small (effectively as small as $$$0.01^{4000}$$$ under the constraints of the problem).

This can be problematic since I'm working with double, which makes me question if there is a hack that can break my solution.

Assuming there is a hack that breaks my solution, how can I compute last to avoid running into problems with floating-point underflow?

Update: I think I figured it out.

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

»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Both double and long double AC here, but neither seem like they would be precise enough to be completely hack-proof for my submission.

→ Reply
»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Thanks to this blog, I figured it out.

I started by adding this flag:

#pragma GCC target("fpmath=sse,sse2") // Turns off excess precision

Then taking the same exact code I had above but using log to compute last instead, taking advantage of the fact that $$$\log(a \cdot b) = \log(a) + \log(b)$$$.

double ans = 0, last = log(1);
for(int i = 1; i <= s; i++) last += log(q);
for(int i = s; i <= r; i++) {
    ans += exp(last) * dp0[r-i][max(1,m-i+s)];
    last += log(p * i / (i+1-s));
}
cout << ans << endl;

This is the submission where I implemented the two changes I just described: 342341598

I believe it is correct and not hackable.

→ Reply