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.

Reached expert (1623) for the first time:

I came up with the following problem:

Given an array $$$A$$$ of $$$N$$$ non-negative integers, output $$$2$$$ permutations $$$X$$$ and $$$Y$$$ such that $$$|X_i - Y_i| \ge A_i$$$ for all $$$(1 \le i \le N)$$$ or report that it is impossible to do so.

For example, given this test case:
$$$N = 5$$$
$$$A = [2,2,4,2,2]$$$

The output could be:
$$$X = [5,2,1,3,4]$$$
$$$Y = [3,4,5,1,2]$$$

I have not given constraints on $$$N$$$ as I am not sure what the best possible time complexity of a solution to this problem is.

Say you wanted to calculate the floored square root of a number in C++, and you do: (int)sqrtl(x).

Or you wanted to calculate the floored base b logarithm of some number, and you do: (int)(logl(x)/logl(b)).

Could either of the 2 produce incorrect results due to precision errors?

I would assume since long double has 64 significant bits, both of the cases above should work correctly for all possible 64-bit integer values of x, but I am a bit skeptical of the logarithm, since there is an extra division step.

And if they are unreliable, what are good alternatives?

The whole point of your CF rating is to reflect your past performance in contests, which gives you a rough idea of how skilled you are as a competitive programmer.

So when your rating goes up significantly, it's usually a sign that you have improved significantly.

I would assume that people cheat for a better rating, but what is the point of increasing your rating if you know your skill hasn't increased alongside it?

It makes your rating feel meaningless... Completely removes the sense of accomplishment, which is the whole point of wanting to achieve a higher rating in the first place.

Why am I still gray?

Given $$$N$$$ integer intervals $$$[a, b]$$$, find the maximum number of pairs of overlapping intervals where each interval can belong to at most one pair.

Two intervals overlap if they share a common point, including closed endpoints.

The answer to the example above is 2. Pair the 2 black intervals and the 2 red intervals together.

What is the best time complexity that can be achieved for this problem? Currently I'm not sure if it's even solvable in polynomial time.