Detailed mathematical approach

Problem Summary

Let \(v_1,\dots,v_n\) be the generated sequence of bean counts, where

$v_1=290797,\qquad v_{k+1}\equiv v_k^2 \pmod{50515093}.$

Think of \(v_i\) as the number of beans in bowl \(i\). Beans may be moved to the right across adjacent boundaries until the final counts \(y_1,\dots,y_n\) become nondecreasing:

$y_1\le y_2\le \cdots \le y_n,\qquad \sum_{i=1}^{n} y_i=\sum_{i=1}^{n} v_i.$

The required quantity is the minimum total rightward transport. Equivalently, if

$P_k=\sum_{i=1}^{k} v_i,\qquad Q_k=\sum_{i=1}^{k} y_i,$

then the answer is

$B(n)=\sum_{k=1}^{n}(P_k-Q_k).$

The algorithm in the implementations finds the optimal nondecreasing integer sequence \(y\) without simulating individual bean moves.

Mathematical Approach

The problem is an integer form of isotonic regression on a very long sequence. The key is to work with contiguous blocks instead of individual bowls.

Step 1: Rephrase the Objective with Prefix Sums

If one bean is moved from bowl \(i\) to bowl \(j>i\), then every prefix ending at positions \(i,i+1,\dots,j-1\) loses exactly \(1\). Therefore that single bean contributes

$j-i$

to the total transportation cost, and also decreases

$\sum_{k=1}^{n} Q_k$

by exactly the same amount. Hence minimizing movement is equivalent to maximizing the final total of prefix sums. So we must find a nondecreasing integer sequence \(y\) with the same total sum as \(v\) that maximizes

$S_{\mathrm{final}}=\sum_{k=1}^{n} Q_k,$

because then

$B(n)=S_{\mathrm{orig}}-S_{\mathrm{final}},\qquad S_{\mathrm{orig}}=\sum_{k=1}^{n} P_k.$

Step 2: Optimal Structure Inside One Block

Suppose a contiguous block of \(\ell\) bowls has total sum \(\Sigma\). Among all nondecreasing integer sequences on that block with that fixed sum, the best one is as flat as possible. Write

$\Sigma=q\ell+r,\qquad 0\le r<\ell,\qquad q=\left\lfloor \frac{\Sigma}{\ell}\right\rfloor.$

Then the optimal block realization is

$\underbrace{q,\dots,q}_{\ell-r},\underbrace{q+1,\dots,q+1}_{r}.$

Why must this be true? If some earlier entry were at least \(2\) smaller than a later one, moving one unit from the later entry to the earlier entry would preserve the block sum, preserve nondecreasing order, and increase one or more prefix sums. So any optimum must differ by at most \(1\) inside each flat region.

Step 3: The Feasibility Test for Two Neighboring Blocks

Take two adjacent candidate blocks with sums and lengths \((\Sigma_1,\ell_1)\) and \((\Sigma_2,\ell_2)\). If they stay separate, the left block can do no better than ending at

$\left\lceil \frac{\Sigma_1}{\ell_1}\right\rceil,$

while the right block can do no better than starting at

$\left\lfloor \frac{\Sigma_2}{\ell_2}\right\rfloor.$

Therefore the two blocks can coexist in one global nondecreasing sequence if and only if

$\left\lceil \frac{\Sigma_1}{\ell_1}\right\rceil \le \left\lfloor \frac{\Sigma_2}{\ell_2}\right\rfloor.$

If this inequality fails, then every admissible integer realization of the left block ends too high, or every admissible integer realization of the right block starts too low, so the boundary order is impossible. In that case the two blocks must be merged.

Step 4: Forced Merging and the Integer PAV Rule

Start with each value \(v_i\) as a block of length \(1\) and sum \(v_i\). Scan from left to right. Whenever the last two blocks violate

$\left\lceil \frac{\Sigma_1}{\ell_1}\right\rceil \le \left\lfloor \frac{\Sigma_2}{\ell_2}\right\rfloor,$

replace them by their union \((\Sigma_1+\Sigma_2,\ell_1+\ell_2)\). Repeat until the last boundary becomes feasible again.

This is the pool-adjacent-violators idea adapted to integer values. Every merge is forced by the previous step, so the final partition is exactly the coarsest partition whose block realizations can be concatenated into a nondecreasing integer sequence.

Step 5: Compute the Final Prefix-Sum Total Block by Block

For a final block \((\Sigma,\ell)\), write

$\Sigma=q\ell+r,\qquad a=\ell-r,\qquad b=r.$

So the block expands to \(a\) copies of \(q\), then \(b\) copies of \(q+1\). If the prefix sum before this block begins is \(R\), then this block contributes

$aR+q\frac{a(a+1)}{2}+b(R+aq)+(q+1)\frac{b(b+1)}{2}$

to \(S_{\mathrm{final}}\). After that block, the running prefix becomes

$R+\Sigma.$

Summing this over all final blocks yields \(S_{\mathrm{final}}\), and then

$\boxed{B(n)=S_{\mathrm{orig}}-S_{\mathrm{final}}.}$

Worked Example: The First Six Generated Values

The first six terms are

$290797,\ 629527,\ 13339144,\ 15552512,\ 17939732,\ 3034546.$

The first five are already nondecreasing, but the sixth value is too small. The merge process combines the last four bowls into one block with

$\Sigma=13339144+15552512+17939732+3034546=49865934,\qquad \ell=4.$

Now

$q=\left\lfloor\frac{49865934}{4}\right\rfloor=12466483,\qquad r=2,$

so that block becomes

$12466483,\ 12466483,\ 12466484,\ 12466484.$

The optimal final sequence is therefore

$290797,\ 629527,\ 12466483,\ 12466483,\ 12466484,\ 12466484.$

The original prefix sums are

$290797,\ 920324,\ 14259468,\ 29811980,\ 47751712,\ 50786258,$

while the final prefix sums are

$290797,\ 920324,\ 13386807,\ 25853290,\ 38319774,\ 50786258.$

The difference of their totals is

$B(6)=14263289,$

which matches the checkpoint in the implementations.

How the Code Works

The C++, Python, and Java implementations all follow the same two-pass strategy.

In the first pass they generate the pseudo-random sequence on the fly, accumulate the original prefix sums, and maintain a stack of blocks. Each new value starts as a one-element block. While the last two blocks fail the integer feasibility test, they are merged by adding their sums and lengths.

In the second pass the implementation walks through the final blocks and adds their contribution to the final prefix-sum total using the closed formulas above. It never needs to expand the whole length-\(n\) final sequence explicitly. The totals can exceed ordinary 64-bit range for the full input, so the implementations use wide integer arithmetic for the accumulated answer.

Complexity Analysis

Each generated value is pushed as a new block once, and each block can disappear through merging at most once. Therefore the total number of stack operations is linear. The second pass is also linear in the number of final blocks, which is at most \(n\). Hence the overall running time is

$O(n),$

with worst-case memory usage

$O(n).$

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=839
2. Isotonic regression: Wikipedia - Isotonic regression
3. Prefix sums: Wikipedia - Prefix sum
4. Ceiling and floor functions: Wikipedia - Floor and ceiling functions
5. Pseudorandom number generator: Wikipedia - Pseudorandom number generator