Random Analysis: Direct Expectation Updates¶
The expectation recurrence from the accompanying editorial; Codex (GPT-6) uses rolling storage and makes simultaneous-update ordering explicit. Program: alternative-direct-expectation.cpp. See the main editorial for the preferred method.
Method and proof¶
Write \(M=998244353\) .
Initialize \(x_j=a_j\) and the invariant mean \(\mu=n^{-1}\sum a_j\) . In round \(i\) , save the old value \(c=x_i\) and update every \(j\ne i\) by
Finally set \(x_i=\mu\) . Independent uniform sampling makes position \(j\) receive the old value at \(i\) with probability \(1/n\) , otherwise leaving it unchanged. Position \(i\) receives a uniformly sampled position value. Thus the formulas describe the round exactly, and induction proves the final expectations.
Save \(c\) before updating. Do not use the new value of \(x_i\) for other positions in the same round. Only each position's own old value and the shared \(c\) are needed, so historical rounds need not be stored.
Complexity and applicability¶
Time is \(O(n^2+\log M)\) and space is \(O(n)\) . The formulas also work for \(n=1\) without inverting \(n-1\) . This method follows the round recurrence directly; the affine method combines its shared updates to process the rounds linearly.
This is a correct backup over the full constraints. See measurements for the current limit; a higher asymptotic time bound does not imply a timeout at this size.