Billion Players Game

The bookmaker offers look like inequalities, but the payoff is much simpler than it first seems.

If you accept offer $a$ by claiming $p\le a$:

• when $p\le a$, you gain $|p-a|=a-p$;
• when $p>a$, you lose $|p-a|=p-a$, so your payoff is $-(p-a)=a-p$.

So this action always contributes

$$a-p.$$

Similarly, claiming $p\ge a$ always contributes

$$p-a.$$

Ignoring contributes $0$. The truth of the claim does not create cases in the final formula. Nice little scam by the statement.

The total payoff is a line

Suppose we choose some offers as type upper, meaning claim $p\le a_i$, and some as type lower, meaning claim $p\ge a_i$.

The total payoff is

$$\sum_{i\in upper}(a_i-p)+\sum_{i\in lower}(p-a_i).$$

This is a linear function of $p$:

$$C+kp,$$

where

$$k=|lower|-|upper|.$$

Since $p$ can be any value in $[l,r]$, the worst case is:

• at $l$ if $k\ge 0$;
• at $r$ if $k\le 0$.

So every strategy belongs to one of two worlds:

1. Its worst case is at $l$, so we need $|lower|\ge |upper|$.
2. Its worst case is at $r$, so we need $|upper|\ge |lower|$.

We solve both and take the maximum.

Solving the left-end version

Assume the worst point is $l$, so $|lower|\ge |upper|$.

At $p=l$:

• choosing upper gives $a_i-l$;
• choosing lower gives $l-a_i=-(a_i-l)$.

Let

$$b_i=a_i-l.$$

Now each offer lets us choose one of:

• $+b_i$, counted as an upper choice;
• $-b_i$, counted as a lower choice;
• $0$, ignored.

Constraint:

$$\#lower\ge \#upper.$$

Think of every lower choice as giving one unit of balance, and every upper choice as spending one unit of balance.

Now classify values $b_i$.

If $b_i<0$, then choosing $-b_i$ gives positive profit and also increases balance. Always take it.

If $b_i=0$, choosing $-b_i=0$ gives no profit but increases balance for free. Always take it too.

If $b_i>0$, choosing $+b_i$ is profitable but spends balance. Choosing $-b_i$ loses money but creates balance. So positives are where all the actual decision-making lives.

Let balance be the number of already chosen non-positive $b_i$ values. Let ans contain the profit from negative $b_i$ values.

Sort all positive $b_i$ increasingly.

First, while we have balance, spend it on the largest positive values. This is pure profit, so obviously we want the biggest ones.

After balance is gone, the only way to take another positive as $+b$ is to also take some positive as $-b$ to pay for the count constraint. A pair gives

$$b_{large}-b_{small}.$$

To maximize this, use the smallest remaining positive as the forced negative choice and the largest remaining positive as the positive choice. If the difference is not positive, there is no point continuing.

That gives the best possible score whose worst case is $l$.

Solving the right-end version

Do the exact same thing from the right side.

For worst point $r$, the condition is $|upper|\ge |lower|$.

At $p=r$:

• choosing lower gives $r-a_i$;
• choosing upper gives $a_i-r=-(r-a_i)$.

So define

$$b_i=r-a_i$$

and run the same helper. Again, choosing $-b_i$ is the side that creates the required balance, and choosing $+b_i$ spends it.

Finally:

$$\text{answer}=\max(calc(a_i-l), calc(r-a_i)).$$

Why the greedy is correct

All non-positive $b_i$ should be taken as $-b_i$:

• for $b_i<0$, it gives positive profit and helps the constraint;
• for $b_i=0$, it gives free help to the constraint.

For positive values, every chosen $+b_i$ either uses existing balance or must be matched with some chosen $-b_j$.

Existing balance should go to the largest positives, because each such choice has no downside.

For matched positive pairs, a pair contributes $b_i-b_j$, where $b_i$ is chosen as positive and $b_j$ is chosen as negative. If two positive values are paired, the larger one should always be the positive one. Across many pairs, the best pairing is therefore smallest negatives against largest positives. Any other pairing can be swapped to not decrease the sum.

So the two-pointer greedy is optimal.

Complexity

Each test case sorts $O(n)$ values twice, so the complexity is

$$O(n\log n)$$

per test case, with total $n\le 2\cdot 10^5$. Totally fine.