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.
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.
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.$$
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.
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.
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.
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}}.}$$
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.
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.
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).$$
Sei \(v_1,\dots,v_n\) die erzeugte Folge der Bohnenzahlen mit
$$v_1=290797,\qquad v_{k+1}\equiv v_k^2 \pmod{50515093}.$$
Man interpretiert \(v_i\) als die Anzahl der Bohnen in Schale \(i\). Bohnen dürfen nach rechts über benachbarte Grenzen verschoben werden, bis die Endfolge \(y_1,\dots,y_n\) monoton nicht fallend ist:
$$y_1\le y_2\le \cdots \le y_n,\qquad \sum_{i=1}^{n} y_i=\sum_{i=1}^{n} v_i.$$
Gesucht ist die minimale gesamte Rechtsbewegung. Mit den Präfixsummen
$$P_k=\sum_{i=1}^{k} v_i,\qquad Q_k=\sum_{i=1}^{k} y_i$$
ist die gesuchte Größe äquivalent zu
$$B(n)=\sum_{k=1}^{n}(P_k-Q_k).$$
Die Implementierungen berechnen also die optimale monotone ganzzahlige Umverteilung, ohne einzelne Bohnenbewegungen explizit zu simulieren.
Mathematisch ist das eine ganzzahlige Variante der isotonic regression auf einer sehr langen Folge. Statt einzelne Positionen direkt zu optimieren, arbeitet die Lösung mit zusammenhängenden Blöcken.
Wird eine Bohne von Schale \(i\) nach Schale \(j>i\) verschoben, dann verliert jede Präfixsumme mit Endposition \(i,i+1,\dots,j-1\) genau \(1\). Diese eine Bohne trägt also
$$j-i$$
zur Transportkosten bei und verringert zugleich
$$\sum_{k=1}^{n} Q_k$$
um denselben Betrag. Daher ist Minimierung der Bewegung gleichbedeutend mit Maximierung der endgültigen Präfixsummensumme. Gesucht ist also eine nicht fallende ganzzahlige Folge \(y\) mit demselben Gesamtwert wie \(v\), die
$$S_{\mathrm{final}}=\sum_{k=1}^{n} Q_k$$
maximiert. Dann gilt
$$B(n)=S_{\mathrm{orig}}-S_{\mathrm{final}},\qquad S_{\mathrm{orig}}=\sum_{k=1}^{n} P_k.$$
Betrachte einen zusammenhängenden Block mit Länge \(\ell\) und Summe \(\Sigma\). Unter allen nicht fallenden ganzzahligen Folgen mit genau dieser Blocksumme ist die beste Folge so flach wie möglich. Schreibe
$$\Sigma=q\ell+r,\qquad 0\le r<\ell,\qquad q=\left\lfloor \frac{\Sigma}{\ell}\right\rfloor.$$
Dann lautet die optimale Blockform
$$\underbrace{q,\dots,q}_{\ell-r},\underbrace{q+1,\dots,q+1}_{r}.$$
Der Grund ist einfach: Wenn ein früherer Eintrag mindestens \(2\) kleiner als ein späterer wäre, könnte man eine Einheit vom späteren zum früheren Eintrag verschieben. Die Summe des Blocks bliebe gleich, die Monotonie bliebe erhalten, aber einige Präfixsummen würden steigen. Also darf ein Optimum innerhalb eines Blocks nur Werte enthalten, die sich höchstens um \(1\) unterscheiden.
Nehmen wir zwei benachbarte Kandidatenblöcke \((\Sigma_1,\ell_1)\) und \((\Sigma_2,\ell_2)\). Wenn sie getrennt bleiben sollen, kann der linke Block im besten Fall nur mit
$$\left\lceil \frac{\Sigma_1}{\ell_1}\right\rceil$$
enden, und der rechte Block kann im besten Fall nur mit
$$\left\lfloor \frac{\Sigma_2}{\ell_2}\right\rfloor$$
beginnen. Somit sind beide Blöcke genau dann gemeinsam mit globaler Monotonie vereinbar, wenn
$$\left\lceil \frac{\Sigma_1}{\ell_1}\right\rceil \le \left\lfloor \frac{\Sigma_2}{\ell_2}\right\rfloor.$$
Falls diese Ungleichung verletzt ist, endet jede zulässige ganzzahlige Realisierung des linken Blocks zu hoch oder jede zulässige Realisierung des rechten Blocks beginnt zu niedrig. Dann ist die Grenzstelle unmöglich und die Blöcke müssen verschmolzen werden.
Man startet mit einem Block pro Wert \(v_i\), also mit Länge \(1\) und Summe \(v_i\). Beim Durchlauf von links nach rechts prüft man immer die letzten beiden Blöcke. Verletzen sie
$$\left\lceil \frac{\Sigma_1}{\ell_1}\right\rceil \le \left\lfloor \frac{\Sigma_2}{\ell_2}\right\rfloor,$$
dann werden sie durch ihren Vereinigungsblock \((\Sigma_1+\Sigma_2,\ell_1+\ell_2)\) ersetzt. Das wird wiederholt, bis die letzte Grenze wieder zulässig ist.
Das ist die Pool-Adjacent-Violators-Idee für ganzzahlige Niveaus. Jeder Merge ist durch den vorigen Schritt erzwungen, daher ist die Endpartition genau die gröbste Partition, deren Blockrealisierungen sich zu einer global nicht fallenden ganzzahligen Folge zusammensetzen lassen.
Für einen Endblock \((\Sigma,\ell)\) schreibe
$$\Sigma=q\ell+r,\qquad a=\ell-r,\qquad b=r.$$
Der Block entfaltet sich also in \(a\) Kopien von \(q\) und danach \(b\) Kopien von \(q+1\). Wenn die Präfixsumme vor diesem Block gleich \(R\) ist, trägt der Block
$$aR+q\frac{a(a+1)}{2}+b(R+aq)+(q+1)\frac{b(b+1)}{2}$$
zu \(S_{\mathrm{final}}\) bei. Danach ist die laufende Präfixsumme
$$R+\Sigma.$$
Über alle Blöcke summiert erhält man \(S_{\mathrm{final}}\), und damit
$$\boxed{B(n)=S_{\mathrm{orig}}-S_{\mathrm{final}}.}$$
Die ersten sechs Glieder lauten
$$290797,\ 629527,\ 13339144,\ 15552512,\ 17939732,\ 3034546.$$
Die ersten fünf Werte sind bereits nicht fallend, aber der sechste ist zu klein. Der Merge-Prozess fasst deshalb die letzten vier Schalen zu einem Block zusammen mit
$$\Sigma=13339144+15552512+17939732+3034546=49865934,\qquad \ell=4.$$
Es gilt
$$q=\left\lfloor\frac{49865934}{4}\right\rfloor=12466483,\qquad r=2,$$
also wird dieser Block zu
$$12466483,\ 12466483,\ 12466484,\ 12466484.$$
Die optimale Endfolge ist damit
$$290797,\ 629527,\ 12466483,\ 12466483,\ 12466484,\ 12466484.$$
Die ursprünglichen Präfixsummen sind
$$290797,\ 920324,\ 14259468,\ 29811980,\ 47751712,\ 50786258,$$
und die endgültigen Präfixsummen sind
$$290797,\ 920324,\ 13386807,\ 25853290,\ 38319774,\ 50786258.$$
Die Differenz der Totalsummen ist
$$B(6)=14263289,$$
genau wie im Kontrollwert der Implementierungen.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Strategie in zwei Durchläufen.
Im ersten Durchlauf wird die pseudozufällige Folge fortlaufend erzeugt, die Summe der ursprünglichen Präfixe akkumuliert und ein Stack von Blöcken geführt. Jeder neue Wert startet als Ein-Element-Block. Solange die letzten beiden Blöcke den ganzzahligen Machbarkeitstest verletzen, werden ihre Summen und Längen zusammengelegt.
Im zweiten Durchlauf läuft die Implementierung über die Endblöcke und addiert deren Beitrag zur endgültigen Präfixsummensumme mit den geschlossenen Formeln von oben. Die gesamte Endfolge der Länge \(n\) muss dabei nie explizit materialisiert werden. Für den vollen Input wachsen die Summen über den Bereich gewöhnlicher 64-Bit-Zahlen hinaus, daher verwenden die Implementierungen breite Ganzzahlarithmetik für das Endergebnis.
Jeder erzeugte Wert wird genau einmal als neuer Block eingefügt, und jeder Block kann durch Merging höchstens einmal wieder verschwinden. Daher ist die Gesamtzahl der Stack-Operationen linear. Auch der zweite Durchlauf ist linear in der Zahl der Endblöcke, und diese ist höchstens \(n\). Insgesamt beträgt die Laufzeit also
$$O(n),$$
bei Speicherverbrauch im Worst Case von
$$O(n).$$
\(v_1,\dots,v_n\) dizisi şu üreteçten gelir:
$$v_1=290797,\qquad v_{k+1}\equiv v_k^2 \pmod{50515093}.$$
\(v_i\) değerini \(i\). kaptaki fasulye sayısı olarak düşünelim. Fasulyeler yalnızca sağa, komşu kap sınırlarını aşacak şekilde taşınabilir ve son durumda \(y_1,\dots,y_n\) dizisinin artmayan değil, artan ya da sabit olması gerekir:
$$y_1\le y_2\le \cdots \le y_n,\qquad \sum_{i=1}^{n} y_i=\sum_{i=1}^{n} v_i.$$
İstenen değer toplam sağa taşıma maliyetinin minimumudur. Eğer
$$P_k=\sum_{i=1}^{k} v_i,\qquad Q_k=\sum_{i=1}^{k} y_i$$
olursa cevap eşdeğer olarak
$$B(n)=\sum_{k=1}^{n}(P_k-Q_k)$$
şeklinde yazılır. Dolayısıyla amaç, tek tek taşımaları simüle etmek yerine en iyi monoton tam sayı dizisini bulmaktır.
Bu problem, çok uzun bir dizi üzerinde tam sayılı izotonik regresyon olarak okunabilir. Esas fikir, tek tek kaplar yerine bitişik bloklar üzerinden düşünmektir.
Bir fasulye \(i\). kaptan \(j>i\). kaba taşınırsa, bitiş noktası \(i,i+1,\dots,j-1\) olan her prefix toplamı tam olarak \(1\) azalır. Bu yüzden o tek fasulyenin maliyeti
$$j-i$$
olur ve aynı zamanda
$$\sum_{k=1}^{n} Q_k$$
ifadesini de aynı miktarda küçültür. Demek ki toplam taşıma maliyetini minimize etmek, son prefix toplamları toplamını maksimize etmekle aynıdır. Yani toplamı \(v\) ile aynı olan, monoton artan bir tam sayı dizisi \(y\) bulup
$$S_{\mathrm{final}}=\sum_{k=1}^{n} Q_k$$
değerini büyütmemiz gerekir. O zaman
$$B(n)=S_{\mathrm{orig}}-S_{\mathrm{final}},\qquad S_{\mathrm{orig}}=\sum_{k=1}^{n} P_k.$$
Uzunluğu \(\ell\), toplamı \(\Sigma\) olan bitişik bir blok düşünelim. Bu blok üzerinde toplam sabit kalırken ve dizi artan kalırken, en iyi düzenleme olabildiğince düzdür. Şöyle yazalım:
$$\Sigma=q\ell+r,\qquad 0\le r<\ell,\qquad q=\left\lfloor \frac{\Sigma}{\ell}\right\rfloor.$$
O zaman blok içindeki optimal görünüm
$$\underbrace{q,\dots,q}_{\ell-r},\underbrace{q+1,\dots,q+1}_{r}$$
olur. Neden? Çünkü daha soldaki bir değer, daha sağdaki bir değerden en az \(2\) küçükse, sağdakinden sola \(1\) birim aktarmak toplamı bozmaz, sıralamayı bozmaz, ama bazı prefix toplamlarını artırır. Bu yüzden optimal bir blokta değerler ancak \(1\) kadar farklı olabilir.
Şimdi iki komşu aday blok alalım: \((\Sigma_1,\ell_1)\) ve \((\Sigma_2,\ell_2)\). Ayrı kalacaklarsa, sol blok en iyi durumda en fazla
$$\left\lceil \frac{\Sigma_1}{\ell_1}\right\rceil$$
ile biter; sağ blok ise en iyi durumda en az
$$\left\lfloor \frac{\Sigma_2}{\ell_2}\right\rfloor$$
ile başlar. Dolayısıyla bu iki blok ancak ve ancak
$$\left\lceil \frac{\Sigma_1}{\ell_1}\right\rceil \le \left\lfloor \frac{\Sigma_2}{\ell_2}\right\rfloor$$
ise aynı genel monoton dizinin parçaları olabilir. Bu eşitsizlik bozulursa, sol blok kaçınılmaz olarak fazla yüksek biter ya da sağ blok kaçınılmaz olarak fazla düşük başlar; sınırda sıralama imkansızdır. O halde bloklar birleştirilmek zorundadır.
Her \(v_i\) değeri başlangıçta toplamı \(v_i\), uzunluğu \(1\) olan ayrı bir bloktur. Dizi soldan sağa taranır. Son iki blok
$$\left\lceil \frac{\Sigma_1}{\ell_1}\right\rceil \le \left\lfloor \frac{\Sigma_2}{\ell_2}\right\rfloor$$
koşulunu bozuyorsa, bunlar
$$(\Sigma_1+\Sigma_2,\ell_1+\ell_2)$$
bloğunda birleştirilir. Son sınır tekrar uygun hale gelene kadar bu işlem sürer.
Bu, pool-adjacent-violators yönteminin tam sayılı sürümüdür. Her birleştirme önceki adımdan zorunlu olarak gelir. Sonunda elde edilen blok bölümü, blok içi en düzgün düzenlemeler bir araya getirildiğinde genel artan diziyi veren en kaba bölümdür.
Bir son blok için \((\Sigma,\ell)\) yazalım:
$$\Sigma=q\ell+r,\qquad a=\ell-r,\qquad b=r.$$
Bu blok \(a\) tane \(q\), ardından \(b\) tane \(q+1\) olarak açılır. Blok başlamadan önceki prefix toplamı \(R\) ise bu blok \(S_{\mathrm{final}}\)'e
$$aR+q\frac{a(a+1)}{2}+b(R+aq)+(q+1)\frac{b(b+1)}{2}$$
katkısını yapar. Blok sonrasında çalışan prefix toplamı
$$R+\Sigma$$
olur. Tüm bloklar için topladığımızda \(S_{\mathrm{final}}\) bulunur ve sonra
$$\boxed{B(n)=S_{\mathrm{orig}}-S_{\mathrm{final}}.}$$
İlk altı terim şunlardır:
$$290797,\ 629527,\ 13339144,\ 15552512,\ 17939732,\ 3034546.$$
İlk beş terim zaten artandır; sorun altıncı terimin çok küçük olmasıdır. Birleştirme süreci son dört kabı tek blokta toplar:
$$\Sigma=13339144+15552512+17939732+3034546=49865934,\qquad \ell=4.$$
Buradan
$$q=\left\lfloor\frac{49865934}{4}\right\rfloor=12466483,\qquad r=2$$
çıkar; yani blok
$$12466483,\ 12466483,\ 12466484,\ 12466484$$
şeklinde açılır. Böylece optimal son dizi
$$290797,\ 629527,\ 12466483,\ 12466483,\ 12466484,\ 12466484$$
olur. Orijinal prefix toplamları
$$290797,\ 920324,\ 14259468,\ 29811980,\ 47751712,\ 50786258,$$
son prefix toplamları ise
$$290797,\ 920324,\ 13386807,\ 25853290,\ 38319774,\ 50786258.$$
Toplam fark
$$B(6)=14263289$$
çıkar; bu da implementasyonlardaki kontrol değeriyle aynıdır.
C++, Python ve Java implementasyonlarının üçü de aynı iki geçişli yapıyı kullanır.
İlk geçişte sözde rastgele dizi akış halinde üretilir, orijinal prefix toplamları toplanır ve bloklardan oluşan bir yığın tutulur. Her yeni değer tek elemanlı blok olarak eklenir. Son iki blok tam sayılı uygunluk testini bozduğu sürece toplamları ve uzunlukları birleştirilir.
İkinci geçişte implementasyon son blokların üzerinden gider ve yukarıdaki kapalı formüllerle son prefix toplamı katkılarını ekler. Böylece uzunluğu \(n\) olan son diziyi açıkça üretmek gerekmez. Tam girişte toplamlar sıradan 64-bit aralığını aşabildiği için implementasyonlar sonuç için geniş tam sayı aritmetiği kullanır.
Üretilen her değer yeni blok olarak bir kez eklenir ve her blok birleştirme yoluyla en fazla bir kez yok olur. Bu yüzden toplam yığın işlemi sayısı lineerdir. İkinci geçiş de son blok sayısında lineerdir; bu sayı da en fazla \(n\) olur. Sonuç olarak toplam süre
$$O(n),$$
en kötü durum bellek kullanımı ise
$$O(n)$$
olur.
La secuencia \(v_1,\dots,v_n\) se genera mediante
$$v_1=290797,\qquad v_{k+1}\equiv v_k^2 \pmod{50515093}.$$
Interpretamos \(v_i\) como el número de frijoles en el cuenco \(i\). Los frijoles solo pueden moverse hacia la derecha a través de fronteras adyacentes hasta que la secuencia final \(y_1,\dots,y_n\) sea no decreciente:
$$y_1\le y_2\le \cdots \le y_n,\qquad \sum_{i=1}^{n} y_i=\sum_{i=1}^{n} v_i.$$
La cantidad pedida es el transporte total mínimo hacia la derecha. Si definimos
$$P_k=\sum_{i=1}^{k} v_i,\qquad Q_k=\sum_{i=1}^{k} y_i,$$
entonces la respuesta puede escribirse como
$$B(n)=\sum_{k=1}^{n}(P_k-Q_k).$$
Por eso el objetivo real es encontrar la mejor secuencia entera no decreciente \(y\) sin simular cada movimiento individual.
El problema es una versión entera de la regresión isotónica sobre una secuencia muy larga. La idea central consiste en agrupar posiciones contiguas en bloques y optimizar por bloques.
Si un frijol se mueve del cuenco \(i\) al cuenco \(j>i\), entonces cada prefijo que termina en \(i,i+1,\dots,j-1\) pierde exactamente \(1\). Por tanto, ese único frijol aporta
$$j-i$$
al costo total, y al mismo tiempo reduce
$$\sum_{k=1}^{n} Q_k$$
en la misma cantidad. De aquí se deduce que minimizar el movimiento equivale a maximizar la suma final de prefijos. Debemos hallar una secuencia entera no decreciente \(y\), con la misma suma total que \(v\), que maximice
$$S_{\mathrm{final}}=\sum_{k=1}^{n} Q_k,$$
porque entonces
$$B(n)=S_{\mathrm{orig}}-S_{\mathrm{final}},\qquad S_{\mathrm{orig}}=\sum_{k=1}^{n} P_k.$$
Consideremos un bloque contiguo de longitud \(\ell\) y suma total \(\Sigma\). Entre todas las secuencias enteras no decrecientes con esa suma fija, la mejor es la más plana posible. Escribimos
$$\Sigma=q\ell+r,\qquad 0\le r<\ell,\qquad q=\left\lfloor \frac{\Sigma}{\ell}\right\rfloor.$$
Entonces la realización óptima del bloque es
$$\underbrace{q,\dots,q}_{\ell-r},\underbrace{q+1,\dots,q+1}_{r}.$$
La razón es que, si una entrada anterior fuera al menos \(2\) menor que una entrada posterior, podríamos transferir \(1\) unidad desde la posterior hacia la anterior. La suma del bloque no cambiaría, el orden no decreciente seguiría valiendo y algunas sumas de prefijos aumentarían. Por eso, en un bloque óptimo, las alturas solo pueden diferir en \(1\).
Tomemos dos bloques candidatos adyacentes \((\Sigma_1,\ell_1)\) y \((\Sigma_2,\ell_2)\). Si permanecen separados, el bloque izquierdo no puede terminar por debajo de
$$\left\lceil \frac{\Sigma_1}{\ell_1}\right\rceil,$$
y el bloque derecho no puede empezar por encima de
$$\left\lfloor \frac{\Sigma_2}{\ell_2}\right\rfloor.$$
Por lo tanto, ambos bloques pueden coexistir dentro de una secuencia global no decreciente si y solo si
$$\left\lceil \frac{\Sigma_1}{\ell_1}\right\rceil \le \left\lfloor \frac{\Sigma_2}{\ell_2}\right\rfloor.$$
Si la desigualdad falla, entonces toda realización entera admisible del bloque izquierdo termina demasiado alta, o toda realización admisible del derecho empieza demasiado baja. En ese caso la frontera entre ambos es imposible y los bloques deben fusionarse.
Se empieza con cada valor \(v_i\) como un bloque de longitud \(1\) y suma \(v_i\). Al recorrer de izquierda a derecha, siempre se inspeccionan los dos últimos bloques. Si violan
$$\left\lceil \frac{\Sigma_1}{\ell_1}\right\rceil \le \left\lfloor \frac{\Sigma_2}{\ell_2}\right\rfloor,$$
se sustituyen por su unión
$$(\Sigma_1+\Sigma_2,\ell_1+\ell_2).$$
Esto se repite hasta que la frontera final vuelve a ser factible. Es exactamente la idea de pool-adjacent-violators adaptada a valores enteros. Cada fusión está forzada por el criterio del paso anterior, de modo que la partición final es la partición más gruesa cuyas realizaciones por bloques pueden concatenarse sin romper la monotonicidad.
Para un bloque final \((\Sigma,\ell)\), escribimos
$$\Sigma=q\ell+r,\qquad a=\ell-r,\qquad b=r.$$
Así, el bloque se desarrolla como \(a\) copias de \(q\) seguidas por \(b\) copias de \(q+1\). Si la suma prefijo antes de este bloque es \(R\), la contribución del bloque a \(S_{\mathrm{final}}\) es
$$aR+q\frac{a(a+1)}{2}+b(R+aq)+(q+1)\frac{b(b+1)}{2}.$$
Después del bloque, la suma prefijo acumulada pasa a ser
$$R+\Sigma.$$
Al sumar estas contribuciones sobre todos los bloques finales se obtiene \(S_{\mathrm{final}}\), y luego
$$\boxed{B(n)=S_{\mathrm{orig}}-S_{\mathrm{final}}.}$$
Los seis primeros términos son
$$290797,\ 629527,\ 13339144,\ 15552512,\ 17939732,\ 3034546.$$
Los cinco primeros ya están en orden no decreciente, pero el sexto es demasiado pequeño. El proceso de fusión agrupa los cuatro últimos cuencos en un solo bloque con
$$\Sigma=13339144+15552512+17939732+3034546=49865934,\qquad \ell=4.$$
Entonces
$$q=\left\lfloor\frac{49865934}{4}\right\rfloor=12466483,\qquad r=2,$$
y ese bloque se convierte en
$$12466483,\ 12466483,\ 12466484,\ 12466484.$$
La secuencia final óptima es
$$290797,\ 629527,\ 12466483,\ 12466483,\ 12466484,\ 12466484.$$
Las sumas prefijo originales son
$$290797,\ 920324,\ 14259468,\ 29811980,\ 47751712,\ 50786258,$$
mientras que las finales son
$$290797,\ 920324,\ 13386807,\ 25853290,\ 38319774,\ 50786258.$$
La diferencia de sus totales es
$$B(6)=14263289,$$
exactamente el valor de comprobación utilizado por las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma estrategia de dos pasadas.
En la primera pasada generan la secuencia pseudoaleatoria sobre la marcha, acumulan la suma de prefijos original y mantienen una pila de bloques. Cada nuevo valor comienza como un bloque de un solo elemento. Mientras los dos últimos bloques fallen la prueba de factibilidad entera, se fusionan sumando sus longitudes y sus sumas.
En la segunda pasada la implementación recorre los bloques finales y añade su contribución a la suma final de prefijos usando las fórmulas cerradas anteriores. No hace falta expandir explícitamente toda la secuencia final de longitud \(n\). Para la entrada completa, los acumulados superan el rango de 64 bits habitual, por lo que las implementaciones emplean aritmética entera amplia para el resultado total.
Cada valor generado se inserta una vez como bloque nuevo, y cada bloque puede desaparecer por fusión como máximo una vez. Por eso el número total de operaciones sobre la pila es lineal. La segunda pasada también es lineal en el número de bloques finales, que no supera \(n\). En consecuencia, el tiempo total es
$$O(n),$$
y la memoria en el peor caso es
$$O(n).$$
序列 \(v_1,\dots,v_n\) 由下面的递推式生成：
$$v_1=290797,\qquad v_{k+1}\equiv v_k^2 \pmod{50515093}.$$
把 \(v_i\) 看成第 \(i\) 个碗中的豆子数量。豆子只允许沿着相邻碗之间的边界向右移动，直到最终序列 \(y_1,\dots,y_n\) 变成单调不减：
$$y_1\le y_2\le \cdots \le y_n,\qquad \sum_{i=1}^{n} y_i=\sum_{i=1}^{n} v_i.$$
题目要求的是最小总右移代价。若定义前缀和
$$P_k=\sum_{i=1}^{k} v_i,\qquad Q_k=\sum_{i=1}^{k} y_i,$$
那么答案可以写成
$$B(n)=\sum_{k=1}^{n}(P_k-Q_k).$$
因此，真正要解决的问题不是逐粒模拟豆子的移动，而是构造出满足条件且代价最小的单调整数序列 \(y\)。
从数学上看，这是一类整数型保序回归问题。序列很长，所以不能直接在每个位置上做局部试探；高效做法是把相邻位置压缩成若干个连续块，再对块进行处理。
设一粒豆子从第 \(i\) 个碗移动到第 \(j\) 个碗，其中 \(j>i\)。那么所有终点位于 \(i,i+1,\dots,j-1\) 的前缀都会恰好减少 \(1\)。因此，这一粒豆子的运输成本就是
$$j-i,$$
同时它也会把
$$\sum_{k=1}^{n} Q_k$$
减少同样的数值。于是，最小化总移动距离与最大化最终前缀和总量完全等价。换句话说，我们要在所有满足总和守恒且单调不减的整数序列 \(y\) 中，最大化
$$S_{\mathrm{final}}=\sum_{k=1}^{n} Q_k.$$
一旦求出这个最大值，就有
$$B(n)=S_{\mathrm{orig}}-S_{\mathrm{final}},\qquad S_{\mathrm{orig}}=\sum_{k=1}^{n} P_k.$$
这一步把“移动多少豆子”转化成了“最终前缀和能做多大”的纯序列优化问题。
考虑一个长度为 \(\ell\)、总和为 \(\Sigma\) 的连续块。我们只要求这个块内部是单调不减的整数序列，并且总和固定为 \(\Sigma\)。在所有这样的候选序列中，最优形状一定尽量均匀。写成
$$\Sigma=q\ell+r,\qquad 0\le r<\ell,\qquad q=\left\lfloor\frac{\Sigma}{\ell}\right\rfloor.$$
那么最优块形状必然是
$$\underbrace{q,\dots,q}_{\ell-r},\underbrace{q+1,\dots,q+1}_{r}.$$
原因是：如果块中某个靠前的位置比某个靠后的位置至少小 \(2\)，那么我们可以从后者拿出 \(1\) 个单位放到前者。这样既不改变块总和，也不会破坏单调不减顺序，但会让中间一段前缀和整体增加。既然我们的目标是让最终前缀和总量尽量大，这种差值至少为 \(2\) 的情况在最优解中不可能存在。
设相邻两个候选块分别为 \((\Sigma_1,\ell_1)\) 与 \((\Sigma_2,\ell_2)\)。如果它们不合并，那么左块内部最平的整数分配，其末尾至少会达到
$$\left\lceil\frac{\Sigma_1}{\ell_1}\right\rceil,$$
而右块内部最平的整数分配，其开头至多只能降到
$$\left\lfloor\frac{\Sigma_2}{\ell_2}\right\rfloor.$$
因此，这两个块能够作为整体单调序列的一部分而共存，当且仅当
$$\left\lceil\frac{\Sigma_1}{\ell_1}\right\rceil \le \left\lfloor\frac{\Sigma_2}{\ell_2}\right\rfloor.$$
如果这个不等式不成立，那么左块无论如何都会“结束得太高”，或者右块无论如何都会“开始得太低”，它们之间的边界不可能满足单调性，唯一办法就是把两个块合并成更大的块重新平衡。
算法从左到右扫描序列，起初把每个 \(v_i\) 都看成一个长度为 \(1\)、总和为 \(v_i\) 的块。每插入一个新块后，就检查最后两个块是否满足
$$\left\lceil\frac{\Sigma_1}{\ell_1}\right\rceil \le \left\lfloor\frac{\Sigma_2}{\ell_2}\right\rfloor.$$
如果不满足，就把它们替换成一个新块
$$\bigl(\Sigma_1+\Sigma_2,\ell_1+\ell_2\bigr).$$
然后继续回看新的最后两个块，直到末端边界重新合法为止。这正是 pool-adjacent-violators 思想在整数值上的版本。前一步已经说明：一旦边界不合法，合并就是被数学上强制要求的，不是启发式选择。所以最终得到的块划分，就是能够拼接成全局单调整数序列的最粗划分。
设某个最终块为 \((\Sigma,\ell)\)，并记
$$\Sigma=q\ell+r,\qquad a=\ell-r,\qquad b=r.$$
那么这个块的展开形式就是先出现 \(a\) 个 \(q\)，再出现 \(b\) 个 \(q+1\)。假设进入该块之前的前缀和为 \(R\)，则这个块对 \(S_{\mathrm{final}}\) 的贡献为
$$aR+q\frac{a(a+1)}{2}+b(R+aq)+(q+1)\frac{b(b+1)}{2}.$$
块处理完成后，运行中的前缀和更新为
$$R+\Sigma.$$
把所有最终块的贡献相加，就得到 \(S_{\mathrm{final}}\)。最后答案就是
$$\boxed{B(n)=S_{\mathrm{orig}}-S_{\mathrm{final}}.}$$
这一步非常关键，因为它说明实现根本不需要显式构造完整的最终序列，只要按块做算术求和即可。
前六项为
$$290797,\ 629527,\ 13339144,\ 15552512,\ 17939732,\ 3034546.$$
前五项本来已经单调不减，但第六项突然变小，因此末尾出现违例。合并过程会把最后四个碗并成一个块，其总和与长度分别是
$$\Sigma=13339144+15552512+17939732+3034546=49865934,\qquad \ell=4.$$
于是
$$q=\left\lfloor\frac{49865934}{4}\right\rfloor=12466483,\qquad r=2.$$
所以这个块的最优展开为
$$12466483,\ 12466483,\ 12466484,\ 12466484.$$
整个最优最终序列因此变成
$$290797,\ 629527,\ 12466483,\ 12466483,\ 12466484,\ 12466484.$$
原始前缀和是
$$290797,\ 920324,\ 14259468,\ 29811980,\ 47751712,\ 50786258,$$
最终前缀和是
$$290797,\ 920324,\ 13386807,\ 25853290,\ 38319774,\ 50786258.$$
两者总和之差为
$$B(6)=14263289,$$
与实现中的校验值完全一致。
C++、Python 和 Java 实现都采用相同的两遍流程。
第一遍中，程序一边生成伪随机序列，一边累计原始前缀和总量，同时维护一个“块栈”。每个新值先作为长度为 \(1\) 的块压入；只要最后两个块不满足整数可行性条件，就把它们的总和与长度相加并合并成一个更大的块。
第二遍中，程序按最终块顺序扫描，用上面的封闭公式直接累计每个块对最终前缀和总量的贡献。这样就不必真的把长度为 \(n\) 的最终序列全部展开。对于完整输入，累计量会超出普通 64 位整数范围，因此实现使用了足够宽的整数类型来保存结果。
每个生成值只会作为新块入栈一次，而每个块在合并过程中至多被消去一次，所以所有栈操作的总次数是线性的。第二遍对最终块的扫描也是线性的，而最终块数不超过 \(n\)。因此总时间复杂度为
$$O(n),$$
最坏空间复杂度为
$$O(n).$$
Последовательность \(v_1,\dots,v_n\) генерируется по правилу
$$v_1=290797,\qquad v_{k+1}\equiv v_k^2 \pmod{50515093}.$$
Будем считать, что \(v_i\) — число бобов в \(i\)-й чаше. Бобы разрешено перекладывать только вправо через соседние границы, пока конечная последовательность \(y_1,\dots,y_n\) не станет неубывающей:
$$y_1\le y_2\le \cdots \le y_n,\qquad \sum_{i=1}^{n} y_i=\sum_{i=1}^{n} v_i.$$
Требуется минимальная суммарная стоимость такого переноса. Если ввести префиксные суммы
$$P_k=\sum_{i=1}^{k} v_i,\qquad Q_k=\sum_{i=1}^{k} y_i,$$
то ответ равен
$$B(n)=\sum_{k=1}^{n}(P_k-Q_k).$$
Следовательно, нужно не моделировать каждый отдельный перенос, а построить оптимальную неубывающую целочисленную последовательность \(y\).
По сути это целочисленная версия изотонной регрессии на очень длинной последовательности. Эффективное решение появляется после перехода от отдельных позиций к непрерывным блокам.
Если один боб переносится из чаши \(i\) в чашу \(j>i\), то каждый префикс с правой границей \(i,i+1,\dots,j-1\) уменьшается ровно на \(1\). Значит, этот перенос даёт стоимость
$$j-i$$
и одновременно уменьшает
$$\sum_{k=1}^{n} Q_k$$
на ту же величину. Поэтому минимизация суммарного движения эквивалентна максимизации суммы конечных префиксов. Нужно найти неубывающую целочисленную последовательность \(y\) с тем же общим количеством бобов, что и у \(v\), которая максимизирует
$$S_{\mathrm{final}}=\sum_{k=1}^{n} Q_k.$$
Тогда автоматически
$$B(n)=S_{\mathrm{orig}}-S_{\mathrm{final}},\qquad S_{\mathrm{orig}}=\sum_{k=1}^{n} P_k.$$
Рассмотрим непрерывный блок длины \(\ell\) с суммой \(\Sigma\). Среди всех неубывающих целочисленных последовательностей на этом блоке с фиксированной суммой \(\Sigma\) наилучшей будет самая ровная. Запишем
$$\Sigma=q\ell+r,\qquad 0\le r<\ell,\qquad q=\left\lfloor\frac{\Sigma}{\ell}\right\rfloor.$$
Тогда оптимальная реализация блока имеет вид
$$\underbrace{q,\dots,q}_{\ell-r},\underbrace{q+1,\dots,q+1}_{r}.$$
Почему? Если какой-то более ранний элемент меньше более позднего хотя бы на \(2\), можно перенести одну единицу от позднего к раннему. Сумма блока не изменится, неубывание сохранится, а часть префиксных сумм возрастёт. Значит, в оптимуме внутри блока значения могут отличаться максимум на \(1\).
Возьмём два соседних кандидатных блока \((\Sigma_1,\ell_1)\) и \((\Sigma_2,\ell_2)\). Если их не сливать, то левый блок в своей самой ровной допустимой форме обязательно заканчивается не ниже
$$\left\lceil\frac{\Sigma_1}{\ell_1}\right\rceil,$$
а правый блок в своей самой ровной форме обязательно начинается не выше
$$\left\lfloor\frac{\Sigma_2}{\ell_2}\right\rfloor.$$
Следовательно, они могут сосуществовать внутри одной глобально неубывающей последовательности тогда и только тогда, когда
$$\left\lceil\frac{\Sigma_1}{\ell_1}\right\rceil \le \left\lfloor\frac{\Sigma_2}{\ell_2}\right\rfloor.$$
Если это нарушено, то любой допустимый левый блок заканчивается слишком высоко или любой допустимый правый блок начинается слишком низко. Граница между ними невозможна, поэтому блоки необходимо объединить.
Сначала каждый элемент \(v_i\) рассматривается как блок длины \(1\) и суммы \(v_i\). При проходе слева направо каждый новый элемент добавляется как новый блок. Затем проверяются два последних блока. Если они нарушают условие
$$\left\lceil\frac{\Sigma_1}{\ell_1}\right\rceil \le \left\lfloor\frac{\Sigma_2}{\ell_2}\right\rfloor,$$
они заменяются объединённым блоком
$$(\Sigma_1+\Sigma_2,\ell_1+\ell_2).$$
Процедура повторяется, пока последняя граница снова не станет допустимой. Это и есть идея pool-adjacent-violators, перенесённая на целые уровни. Слияние здесь не эвристика, а математически вынужденный шаг, поэтому итоговое разбиение является именно тем самым самым грубым разбиением, которое ещё допускает глобальную неубывающую целочисленную раскладку.
Пусть конечный блок имеет вид \((\Sigma,\ell)\), и пусть
$$\Sigma=q\ell+r,\qquad a=\ell-r,\qquad b=r.$$
Тогда блок раскрывается как \(a\) копий числа \(q\), а затем \(b\) копий числа \(q+1\). Если префиксная сумма перед этим блоком равна \(R\), то вклад блока в \(S_{\mathrm{final}}\) равен
$$aR+q\frac{a(a+1)}{2}+b(R+aq)+(q+1)\frac{b(b+1)}{2}.$$
После обработки блока текущая префиксная сумма становится
$$R+\Sigma.$$
Просуммировав вклад всех конечных блоков, получаем \(S_{\mathrm{final}}\), а затем
$$\boxed{B(n)=S_{\mathrm{orig}}-S_{\mathrm{final}}.}$$
Первые шесть членов равны
$$290797,\ 629527,\ 13339144,\ 15552512,\ 17939732,\ 3034546.$$
Первые пять уже упорядочены неубывающе, но шестой элемент слишком мал. Поэтому процесс слияния объединяет последние четыре чаши в один блок с параметрами
$$\Sigma=13339144+15552512+17939732+3034546=49865934,\qquad \ell=4.$$
Отсюда
$$q=\left\lfloor\frac{49865934}{4}\right\rfloor=12466483,\qquad r=2,$$
и блок разворачивается в
$$12466483,\ 12466483,\ 12466484,\ 12466484.$$
Итак, оптимальная конечная последовательность равна
$$290797,\ 629527,\ 12466483,\ 12466483,\ 12466484,\ 12466484.$$
Исходные префиксные суммы:
$$290797,\ 920324,\ 14259468,\ 29811980,\ 47751712,\ 50786258,$$
а конечные префиксные суммы:
$$290797,\ 920324,\ 13386807,\ 25853290,\ 38319774,\ 50786258.$$
Разность их сумм равна
$$B(6)=14263289,$$
что полностью совпадает с контрольным значением в реализациях.
Реализации на C++, Python и Java используют одну и ту же двухпроходную схему.
На первом проходе программа генерирует псевдослучайную последовательность, одновременно накапливает исходную сумму префиксов и поддерживает стек блоков. Каждый новый элемент сначала образует блок из одного значения. Пока два последних блока не проходят целочисленный тест совместимости, они сливаются путём сложения длин и сумм.
На втором проходе реализация идёт по итоговым блокам и прибавляет их вклад в конечную сумму префиксов по приведённым выше закрытым формулам. Разворачивать всю итоговую последовательность длины \(n\) не требуется. Для полного входа накопленные суммы выходят за пределы обычного диапазона 64-битных целых, поэтому используется расширенная целочисленная арифметика.
Каждое сгенерированное значение один раз помещается в стек как новый блок, и каждый блок может исчезнуть в результате слияния не более одного раза. Поэтому общее число стековых операций линейно. Второй проход тоже линеен по числу итоговых блоков, а оно не превосходит \(n\). Следовательно, полная временная сложность равна
$$O(n),$$
а память в худшем случае составляет
$$O(n).$$
تُولَّد المتتالية \(v_1,\dots,v_n\) بالعلاقة
$$v_1=290797,\qquad v_{k+1}\equiv v_k^2 \pmod{50515093}.$$
نفسّر \(v_i\) على أنه عدد الفاصوليا في الوعاء رقم \(i\). يُسمح بنقل الحبات إلى اليمين فقط عبر الحدود المتجاورة حتى تصبح المتتالية النهائية \(y_1,\dots,y_n\) غير متناقصة:
$$y_1\le y_2\le \cdots \le y_n,\qquad \sum_{i=1}^{n} y_i=\sum_{i=1}^{n} v_i.$$
المطلوب هو أقل كلفة كلية لهذا النقل نحو اليمين. وإذا عرّفنا المجاميع البادئية
$$P_k=\sum_{i=1}^{k} v_i,\qquad Q_k=\sum_{i=1}^{k} y_i,$$
فإن الجواب يساوي
$$B(n)=\sum_{k=1}^{n}(P_k-Q_k).$$
لذلك فالمسألة الحقيقية هي إيجاد أفضل متتالية صحيحة غير متناقصة \(y\) من دون تتبّع كل حركة منفردة لحبات الفاصوليا.
هذه المسألة هي نسخة صحيحة من الانحدار الرتيب على متتالية طويلة جدًا. الفكرة الأساسية هي التعامل مع كتل متجاورة بدل معالجة كل وعاء على حدة.
إذا نُقلت حبة واحدة من الوعاء \(i\) إلى الوعاء \(j>i\)، فإن كل مجموع بادئي ينتهي عند المواضع \(i,i+1,\dots,j-1\) ينقص بمقدار \(1\). لذلك تسهم هذه الحبة الواحدة بمقدار
$$j-i$$
في كلفة النقل الكلية، كما أنها تُنقص المقدار
$$\sum_{k=1}^{n} Q_k$$
بالمقدار نفسه تمامًا. ومن هنا فإن تصغير كلفة النقل يعادل تكبير مجموع المجاميع البادئية النهائية. إذن يجب أن نبحث عن متتالية صحيحة غير متناقصة \(y\) لها المجموع الكلي نفسه مثل \(v\)، وتحقق أكبر قيمة ممكنة لـ
$$S_{\mathrm{final}}=\sum_{k=1}^{n} Q_k.$$
وعندئذ يصبح
$$B(n)=S_{\mathrm{orig}}-S_{\mathrm{final}},\qquad S_{\mathrm{orig}}=\sum_{k=1}^{n} P_k.$$
لنأخذ كتلة متجاورة طولها \(\ell\) ومجموعها \(\Sigma\). بين جميع المتتاليات الصحيحة غير المتناقصة داخل هذه الكتلة ذات المجموع الثابت \(\Sigma\)، يكون الشكل الأفضل هو الأكثر تسطيحًا. نكتب
$$\Sigma=q\ell+r,\qquad 0\le r<\ell,\qquad q=\left\lfloor\frac{\Sigma}{\ell}\right\rfloor.$$
وعندها تكون الصورة المثلى للكتلة هي
$$\underbrace{q,\dots,q}_{\ell-r},\underbrace{q+1,\dots,q+1}_{r}.$$
والسبب هو أنه إذا كانت قيمة مبكرة أصغر من قيمة متأخرة بما لا يقل عن \(2\)، فيمكن نقل وحدة واحدة من القيمة المتأخرة إلى المبكرة. هذا لا يغيّر مجموع الكتلة، ولا يكسر شرط عدم التناقص، لكنه يزيد بعض المجاميع البادئية. لذلك لا يمكن أن يحتوي الحل الأمثل داخل الكتلة على فروق أكبر من \(1\).
لننظر إلى كتلتين متجاورتين مرشحتين \((\Sigma_1,\ell_1)\) و\((\Sigma_2,\ell_2)\). إذا بقيتا منفصلتين، فإن أفضل ترتيب صحيح متوازن للكتلة اليسرى لا بد أن ينتهي بقيمة لا تقل عن
$$\left\lceil\frac{\Sigma_1}{\ell_1}\right\rceil,$$
وأفضل ترتيب متوازن للكتلة اليمنى لا بد أن يبدأ بقيمة لا تزيد على
$$\left\lfloor\frac{\Sigma_2}{\ell_2}\right\rfloor.$$
ومن ثم يمكن للكتلتين أن تكونا جزءًا من متتالية كلية غير متناقصة إذا وفقط إذا تحقق
$$\left\lceil\frac{\Sigma_1}{\ell_1}\right\rceil \le \left\lfloor\frac{\Sigma_2}{\ell_2}\right\rfloor.$$
إذا فشل هذا الشرط، فستكون نهاية الكتلة اليسرى مرتفعة أكثر من اللازم، أو بداية الكتلة اليمنى منخفضة أكثر من اللازم، وبالتالي تصبح حدود الفصل بينهما غير ممكنة ويجب دمجهما في كتلة أكبر.
في البداية يُعامَل كل عنصر \(v_i\) على أنه كتلة بطول \(1\) ومجموع \(v_i\). ثم نمسح المتتالية من اليسار إلى اليمين. بعد إضافة كل كتلة جديدة نفحص آخر كتلتين. فإذا خالفتا الشرط
$$\left\lceil\frac{\Sigma_1}{\ell_1}\right\rceil \le \left\lfloor\frac{\Sigma_2}{\ell_2}\right\rfloor,$$
نستبدلهما بكتلة اتحادهما
$$(\Sigma_1+\Sigma_2,\ell_1+\ell_2).$$
ثم نعيد الفحص مع الكتلة السابقة حتى تصبح النهاية صالحة من جديد. هذه هي فكرة pool-adjacent-violators لكن على مستويات صحيحة. والدمج هنا ليس خيارًا تجريبيًا، بل هو مفروض رياضيًا متى فشل شرط الإمكان على الحد الفاصل.
لنفترض أن لدينا كتلة نهائية \((\Sigma,\ell)\)، وأن
$$\Sigma=q\ell+r,\qquad a=\ell-r,\qquad b=r.$$
إذن تتوسع الكتلة إلى \(a\) نسخ من \(q\) تليها \(b\) نسخ من \(q+1\). وإذا كان المجموع البادئي قبل بداية هذه الكتلة هو \(R\)، فإن مساهمة الكتلة في \(S_{\mathrm{final}}\) تساوي
$$aR+q\frac{a(a+1)}{2}+b(R+aq)+(q+1)\frac{b(b+1)}{2}.$$
وبعد انتهاء الكتلة يصبح المجموع البادئي الجاري
$$R+\Sigma.$$
بجمع مساهمات جميع الكتل النهائية نحصل على \(S_{\mathrm{final}}\)، ثم يكون الجواب
$$\boxed{B(n)=S_{\mathrm{orig}}-S_{\mathrm{final}}.}$$
أول ستة حدود هي
$$290797,\ 629527,\ 13339144,\ 15552512,\ 17939732,\ 3034546.$$
الحدود الخمسة الأولى غير متناقصة أصلًا، لكن الحد السادس صغير جدًا فيكسر الترتيب. لذلك تدمج الخوارزمية الأوعية الأربعة الأخيرة في كتلة واحدة لها
$$\Sigma=13339144+15552512+17939732+3034546=49865934,\qquad \ell=4.$$
ومن ثم
$$q=\left\lfloor\frac{49865934}{4}\right\rfloor=12466483,\qquad r=2,$$
فتصبح هذه الكتلة
$$12466483,\ 12466483,\ 12466484,\ 12466484.$$
وبالتالي تكون المتتالية النهائية المثلى
$$290797,\ 629527,\ 12466483,\ 12466483,\ 12466484,\ 12466484.$$
المجاميع البادئية الأصلية هي
$$290797,\ 920324,\ 14259468,\ 29811980,\ 47751712,\ 50786258,$$
أما المجاميع البادئية النهائية فهي
$$290797,\ 920324,\ 13386807,\ 25853290,\ 38319774,\ 50786258.$$
والفرق بين مجموعيهما يساوي
$$B(6)=14263289,$$
وهو نفس مقدار التحقق المستخدم في التنفيذات.
تتبع تطبيقات C++ وPython وJava الخطة نفسها على مرحلتين.
في المرحلة الأولى تولّد المتتالية شبه العشوائية أثناء السير، وتجمع مجموع البوادئ الأصلي، وتحافظ على مكدس من الكتل. كل قيمة جديدة تبدأ ككتلة أحادية العنصر. وما دامت آخر كتلتين تفشلان في اختبار الإمكان الصحيح، يجري دمجهما بجمع الطولين والمجموعين.
في المرحلة الثانية تمرّ الخوارزمية على الكتل النهائية وتضيف مساهمة كل كتلة في مجموع البوادئ النهائي باستخدام الصيغ المغلقة السابقة. لذلك لا حاجة أبدًا إلى توسيع المتتالية النهائية كاملة بطول \(n\). وبما أن المجاميع الكلية في الإدخال الكامل تتجاوز المجال المعتاد لأعداد 64-بت، فإن التنفيذات تستخدم حسابًا صحيحًا واسع المدى لحفظ النتيجة.
كل قيمة مولدة تُدفع إلى المكدس مرة واحدة بوصفها كتلة جديدة، وكل كتلة يمكن أن تختفي بالدمج مرة واحدة على الأكثر. لذلك يكون العدد الإجمالي لعمليات المكدس خطيًا. كما أن المرحلة الثانية خطية في عدد الكتل النهائية، وهذا العدد لا يتجاوز \(n\). وعليه فإن التعقيد الزمني الكلي هو
$$O(n),$$
أما التعقيد المكاني في أسوأ حالة فهو
$$O(n).$$