Probabilistic Card Game

Research note: I checked the Codeforces problem page and the official Educational Codeforces Round 187 editorial. The official page gives solution code instead of a full written proof; its core is exactly the two quantities usually named getL and getR, then a binary search over their crossing. The derivation below is original and uses the supplied statement as canonical.

Consider one fixed round with $n$ active cards, sorted as

$x_0 < x_1 < \dots < x_{n-1}.$

The random card is chosen from the $n-2$ cards not selected by Alice or Bob, so it is useful to compute the total payoff over all possible random cards first, then divide by $n-2$ at the end.

Suppose Alice chooses $x_i$ and Bob chooses $x_k$.

If $k>i$, Bob's card is to the right of Alice's. For any random card $c<x_i$, Bob is farther from $c$ than Alice, so the first zero condition triggers. For any $x_i<c<x_k$, the card is between Alice and Bob, so the second zero condition triggers. The only cards that can pay are $c>x_k$, and each contributes $c-x_k$. Thus Bob's total payoff is

$G_k = \sum_{t>k} (x_t-x_k).$

This gets worse as Bob moves farther right:

$G_k-G_{k+1} = (n-k-1)(x_{k+1}-x_k) > 0.$

So among cards to the right of Alice, Bob should choose the immediate successor $x_{i+1}$. Same story on the left, mirrored: if Bob chooses $x_k$ with $k<i$, only cards $c<x_k$ can pay, giving

$F_k = \sum_{t<k} (x_k-x_t),$

and $F_k$ increases as $k$ moves right. Therefore Bob's best left-side choice is the immediate predecessor $x_{i-1}$.

So for Alice choosing $x_i$, Bob's best total payoff is

$\max(L_i, R_i),$

where

$L_i = \sum_{j<i}(x_{i-1}-x_j) = x_{i-1}\cdot i - \sum_{j<i}x_j,$

and

$R_i = \sum_{j>i}(x_j-x_{i+1}) = \sum_{j>i}x_j - x_{i+1}\cdot(n-i-1).$

For boundary cards, the missing side contributes $0$. Alice wants

$A = \min_i \max(L_i, R_i),$

and the answer for the round is

$\frac{A}{n-2}.$

No modulo nonsense while optimizing: compare the real integer totals $L_i,R_i,A$ first, then convert $A/(n-2)$ modulo $998244353$.

Now we need find the minimum quickly after each insertion. The key shape is monotonic:

$L_{i+1}-L_i = i(x_i-x_{i-1}) \ge 0,$

so $L_i$ is nondecreasing. Also

$R_i-R_{i+1} = (n-i-2)(x_{i+2}-x_{i+1}) \ge 0,$

so $R_i$ is nonincreasing. Therefore $\max(L_i,R_i)$ decreases while $R_i$ dominates, then increases once $L_i$ dominates. The minimum is at the first index $p$ where $L_p\ge R_p$, or at $p-1$. That's the whole trick; everything else is data structures, not magic.

For dynamic prefixes, compress all values by order. Maintain:

• a Fenwick tree of active counts, so we can find the $k$-th active value;
• a Fenwick tree of active value sums, so we can query prefix sums;
• predecessor and successor links among active compressed positions, updated when inserting a new card.

For an active card at order position $k$ and compressed index id, compute:

• left count is $k$;
• left sum is the Fenwick sum before id;
• predecessor value comes from prv[id];
• right count is $n-k-1$;
• right sum is total sum minus the Fenwick sum through id;
• successor value comes from nxt[id].

This gives $L_k$ and $R_k$ in $O(\log m)$. Binary-searching the crossing costs $O(\log^2 m)$ per round. With $m\le 2\cdot10^5$, that is comfortably fine. Values fit in long long because the worst relevant total is around $2\cdot10^5\cdot10^{12}=2\cdot10^{17}$.