We work with three heap sizes, written canonically as
$$0\le x\le y\le z.$$
A legal move chooses a positive integer \(n\) and subtracts that same \(n\) from exactly one heap, from any pair of heaps, or from all three heaps, provided no coordinate becomes negative.
A position is losing (a P-position) if there is no legal move from it to another losing position. The task is to sum
$$x+y+z$$
over all losing triples with coordinates at most a fixed limit.
This is a finite impartial normal-play game. Every move strictly decreases at least one coordinate, so the game graph is acyclic. Therefore every position is either:
1. losing: no move reaches a losing state,
2. winning: at least one move reaches a losing state.
The whole problem is therefore to characterize the losing triples efficiently.
The code stores each position in sorted order \(x\le y\le z\). After any legal move we sort again, so each game state appears exactly once.
If we move from \((x,y,z)\) to a successor and then sort, the new triple is always lexicographically smaller than \((x,y,z)\): at least one coordinate decreases, and no coordinate increases.
Hence a lexicographic scan over all canonical triples is valid: when we decide the status of the current triple, every possible losing successor has already been processed.
The number of canonical states up to limit \(N\) is
$$\#\{(x,y,z):0\le x\le y\le z\le N\}=\binom{N+3}{3},$$
which is asymptotically \(O(N^3)\).
From a canonical triple \((x,y,z)\), every legal move belongs to one of these seven families:
$$ (x-n,y,z),\quad (x,y-n,z),\quad (x,y,z-n), $$
$$ (x-n,y-n,z),\quad (x-n,y,z-n),\quad (x,y-n,z-n),\quad (x-n,y-n,z-n). $$
The key observation is that each family preserves a specific 2-dimensional signature. Those preserved quantities are exactly what the fast solver stores.
If we reduce only one heap, two heap sizes remain unchanged. If we reduce two or three heaps together, certain differences remain unchanged.
The seven relevant keys are:
$$ (y,z),\quad (x,z),\quad (x,y), $$
$$ (y-x,z),\quad (z-y,x),\quad (z-x,y),\quad (y-x,z-x). $$
More concretely:
1. reduce only \(x\): the pair \((y,z)\) is preserved,
2. reduce only \(y\): the pair \((x,z)\) is preserved,
3. reduce only \(z\): the pair \((x,y)\) is preserved,
4. reduce \(x\) and \(y\): \((y-x,z)\) is preserved,
5. reduce \(y\) and \(z\): \((z-y,x)\) is preserved,
6. reduce \(x\) and \(z\): \((z-x,y)\) is preserved,
7. reduce all three: \((y-x,z-x)\) is preserved.
These are exactly the indices used in the arrays one, two, and all.
Suppose two different losing positions shared one of the seven keys. Then the later one could move to the earlier one by subtracting the difference in the varying coordinate or coordinates.
That is impossible, because a losing position is defined to have no move to another losing position.
So for each key, at most one losing position can occupy it. This is why a Boolean occupancy table is enough; we only need to know whether some earlier losing state already used that key.
The fast algorithm scans triples in lexicographic order and applies the following rule:
1. If any of the seven keys is already occupied by an earlier losing position, then the current triple is winning.
2. If none of the seven keys is occupied, then the current triple is losing.
The reason is a clean induction on scan order.
If a key is occupied, the move family corresponding to that key gives an explicit move to an earlier losing state.
If no key is occupied, then no legal move can reach any earlier losing state, because every legal move must preserve one of those seven keys. Therefore there is no move to a losing state, so the current triple is itself losing.
This proves that the rule is not heuristic; it is exactly equivalent to the recursive P/N-position definition.
The base position
$$ (0,0,0) $$
has no legal move, so it is losing.
The position
$$ (0,0,1) $$
is winning, because we can subtract \(1\) from the third heap and reach \((0,0,0)\).
A more interesting example is
$$ (0,1,2), $$
which the code uses as a checkpoint losing state. Relative to the already known losing state \((0,0,0)\), none of its seven keys is occupied, so it is declared losing.
Another checkpoint losing state is
$$ (1,3,3). $$
For small limits, the first losing states are
$$ (0,0,0),\ (0,1,2),\ (1,1,4),\ (1,3,3),\ (0,3,5),\ (2,2,6),\dots $$
The code also checks several winning examples such as \((0,0,13)\), \((0,11,11)\), and \((5,5,5)\).
The implementation does not store seven separate structures. Instead it groups them by move type:
1. one[a,b] stores the three single-heap keys \((y,z)\), \((x,z)\), \((x,y)\),
2. two[a,b] stores the three two-heap keys \((y-x,z)\), \((z-y,x)\), \((z-x,y)\),
3. all[a,b] stores the three-heap key \((y-x,z-x)\).
Each table is only \((N+1)\times(N+1)\), so memory stays quadratic rather than cubic.
The helper solve_bruteforce_parallel recomputes losing states directly from the definition. It processes states in layers of constant
$$ x+y+z, $$
because every legal move strictly decreases that total.
For each state it explicitly asks whether some move reaches an already known losing state. This slow method is used only for checkpoint validation.
The code verifies that the fast solver matches brute force on a small limit, and it also checks the sample value
$$ S(100)=173895. $$
The function solve_fast allocates three 2D byte arrays: one, two, and all. It then scans
$$ 0\le x\le y\le z\le N $$
in nested loops.
For the current triple, it tests the seven table entries corresponding to the seven keys. If any entry is already 1, the triple is winning and contributes nothing. If all seven are 0, the triple is losing: the code adds \(x+y+z\) to the answer and marks those seven entries as occupied.
The auxiliary functions sort_triplet, has_move_to_losing_state, and solve_bruteforce_parallel exist only for validation and checkpoints. The final answer itself is produced by the projection-based scan.
The scan examines exactly
$$ \binom{N+3}{3} $$
canonical triples, so the running time is \(O(N^3)\).
Each state performs only a constant number of table lookups and writes. Memory usage is dominated by three 2D tables of size \((N+1)^2\), so space is \(O(N^2)\).
The crucial improvement over naive retrograde analysis is that we never enumerate all legal moves from every state inside the fast solver; the seven invariant keys compress that information into constant-time occupancy tests.
Wir betrachten drei Haufengrößen in kanonischer Ordnung
$$0\le x\le y\le z.$$
Ein legaler Zug wählt ein positives \(n\) und zieht dasselbe \(n\) von genau einem Haufen, von einem beliebigen Haufenpaar oder von allen drei Haufen ab, solange keine Koordinate negativ wird.
Eine Position ist verlierend (P-Position), wenn kein legaler Zug zu einer anderen verlierenden Position führt. Gesucht ist die Summe
$$x+y+z$$
über alle verlierenden Tripel unterhalb einer festen Schranke.
Das Spiel ist endlich, unparteiisch und folgt der Normal-Play-Konvention. Jeder Zug verkleinert mindestens eine Koordinate strikt, also ist der Zustandsgraph azyklisch.
Damit ist jede Position entweder:
1. verlierend: kein Zug erreicht eine verlierende Position,
2. gewinnend: mindestens ein Zug erreicht eine verlierende Position.
Die eigentliche Aufgabe ist also eine effiziente Charakterisierung der verlierenden Tripel.
Der Code speichert jeden Zustand sortiert mit \(x\le y\le z\). Nach jedem Zug würde man wieder sortieren, sodass jeder Spielzustand nur einmal dargestellt wird.
Jeder Nachfolger ist nach dem Sortieren lexikographisch kleiner als der aktuelle Zustand: mindestens eine Koordinate sinkt, keine steigt.
Deshalb ist ein lexikographischer Scan über alle kanonischen Tripel korrekt: Wenn wir den aktuellen Zustand entscheiden, wurden alle möglichen verlierenden Nachfolger bereits verarbeitet.
Die Zahl der kanonischen Zustände bis Grenze \(N\) ist
$$\#\{(x,y,z):0\le x\le y\le z\le N\}=\binom{N+3}{3},$$
also asymptotisch \(O(N^3)\).
Von \((x,y,z)\) aus gibt es genau sieben Familien legaler Züge:
$$ (x-n,y,z),\quad (x,y-n,z),\quad (x,y,z-n), $$
$$ (x-n,y-n,z),\quad (x-n,y,z-n),\quad (x,y-n,z-n),\quad (x-n,y-n,z-n). $$
Der entscheidende Punkt ist, dass jede dieser Familien eine bestimmte 2-dimensionale Signatur invariant lässt. Genau diese Invarianten speichert der schnelle Algorithmus.
Bei einer Reduktion nur eines Haufens bleiben zwei Haufengrößen unverändert. Bei einer gemeinsamen Reduktion von zwei oder drei Haufen bleiben bestimmte Differenzen erhalten.
Die sieben relevanten Schlüssel sind:
$$ (y,z),\quad (x,z),\quad (x,y), $$
$$ (y-x,z),\quad (z-y,x),\quad (z-x,y),\quad (y-x,z-x). $$
Konkret:
1. nur \(x\) reduzieren: \((y,z)\) bleibt erhalten,
2. nur \(y\) reduzieren: \((x,z)\) bleibt erhalten,
3. nur \(z\) reduzieren: \((x,y)\) bleibt erhalten,
4. \(x\) und \(y\) reduzieren: \((y-x,z)\) bleibt erhalten,
5. \(y\) und \(z\) reduzieren: \((z-y,x)\) bleibt erhalten,
6. \(x\) und \(z\) reduzieren: \((z-x,y)\) bleibt erhalten,
7. alle drei reduzieren: \((y-x,z-x)\) bleibt erhalten.
Genau diese Indizes erscheinen in den Arrays one, two und all.
Angenommen, zwei verschiedene Verlustpositionen teilten einen der sieben Schlüssel. Dann könnte die spätere durch Subtraktion in genau der zugehörigen Zugfamilie zur früheren ziehen.
Das widerspricht der Definition einer Verlustposition, die keinen Zug in eine andere Verlustposition besitzen darf.
Also kann jeder Schlüssel von höchstens einer Verlustposition belegt sein. Deshalb genügt eine boolesche Belegungstabelle; die Existenz eines früheren Verlustzustands reicht aus.
Der schnelle Scan arbeitet mit der Regel:
1. Wenn irgendeiner der sieben Schlüssel bereits von einer früheren Verlustposition belegt ist, dann ist der aktuelle Zustand gewinnend.
2. Wenn keiner der sieben Schlüssel belegt ist, dann ist der aktuelle Zustand verlierend.
Der Beweis ist eine saubere Induktion über die Scan-Reihenfolge.
Ist ein Schlüssel belegt, liefert die zugehörige Zugfamilie einen expliziten Zug in einen früheren Verlustzustand.
Ist kein Schlüssel belegt, dann kann kein legaler Zug irgendeinen früheren Verlustzustand erreichen, weil jeder legale Zug genau einen dieser sieben Schlüssel erhalten muss. Also existiert kein Zug in eine Verlustposition, und der aktuelle Zustand ist selbst verlierend.
Die Regel ist damit keine Heuristik, sondern exakt äquivalent zur rekursiven P/N-Definition.
Die Basisposition
$$ (0,0,0) $$
hat keinen legalen Zug und ist daher verlierend.
Die Position
$$ (0,0,1) $$
ist gewinnend, weil man durch Abziehen von \(1\) vom dritten Haufen \((0,0,0)\) erreicht.
Ein interessanteres Beispiel ist
$$ (0,1,2), $$
das im Code als verlierendes Beispiel geprüft wird. Relativ zur schon bekannten Verlustposition \((0,0,0)\) ist keiner seiner sieben Schlüssel belegt, also wird es als verlierend markiert.
Ein weiteres geprüftes Verlustbeispiel ist
$$ (1,3,3). $$
Für kleine Grenzen beginnen die Verlustzustände mit
$$ (0,0,0),\ (0,1,2),\ (1,1,4),\ (1,3,3),\ (0,3,5),\ (2,2,6),\dots $$
Außerdem prüft der Code mehrere Gewinnbeispiele wie \((0,0,13)\), \((0,11,11)\) und \((5,5,5)\).
Die Implementierung verwendet nicht sieben getrennte Strukturen, sondern bündelt nach Zugtyp:
1. one[a,b] für die drei Ein-Haufen-Schlüssel \((y,z)\), \((x,z)\), \((x,y)\),
2. two[a,b] für die drei Zwei-Haufen-Schlüssel \((y-x,z)\), \((z-y,x)\), \((z-x,y)\),
3. all[a,b] für den Drei-Haufen-Schlüssel \((y-x,z-x)\).
Jede Tabelle hat nur die Größe \((N+1)\times(N+1)\), also bleibt der Speicher quadratisch statt kubisch.
Die Hilfsfunktion solve_bruteforce_parallel berechnet Verlustzustände direkt aus der Definition neu. Sie verarbeitet Zustände schichtweise nach konstantem
$$ x+y+z, $$
weil jeder Zug diese Summe strikt verkleinert.
Für jeden Zustand wird explizit geprüft, ob ein Zug in einen bereits bekannten Verlustzustand führt. Diese langsame Methode dient nur der Verifikation.
Der Code bestätigt damit die Übereinstimmung von Brute Force und Schnellverfahren auf kleinen Grenzen und prüft zusätzlich den Beispielwert
$$ S(100)=173895. $$
solve_fast reserviert drei 2D-Byte-Arrays: one, two und all. Danach scannt die Funktion alle Tripel
$$ 0\le x\le y\le z\le N $$
in verschachtelten Schleifen.
Für das aktuelle Tripel werden die sieben Tabellenplätze der sieben Schlüssel geprüft. Ist einer davon bereits 1, ist der Zustand gewinnend und trägt nichts zur Summe bei. Sind alle sieben 0, ist der Zustand verlierend: Der Code addiert \(x+y+z\) und markiert diese sieben Plätze als belegt.
Die Hilfsfunktionen sort_triplet, has_move_to_losing_state und solve_bruteforce_parallel dienen nur den Checkpoints. Die eigentliche Endantwort entsteht allein durch den Projektionenscan.
Der Scan betrachtet genau
$$ \binom{N+3}{3} $$
kanonische Tripel, also beträgt die Laufzeit \(O(N^3)\).
Pro Zustand gibt es nur konstant viele Tabellenzugriffe. Der Speicherverbrauch wird von drei 2D-Tabellen der Größe \((N+1)^2\) dominiert und ist damit \(O(N^2)\).
Der entscheidende Gewinn gegenüber einer naiven Rückwärtsanalyse besteht darin, dass der schnelle Solver nicht für jeden Zustand alle legalen Züge enumeriert; die sieben invarianten Schlüssel verdichten diese Information zu konstanten Belegungstests.
Üç yığın büyüklüğünü kanonik sırada yazıyoruz:
$$0\le x\le y\le z.$$
Yasal hamle, pozitif bir \(n\) seçip aynı \(n\) değerini tam olarak bir yığından, herhangi iki yığından veya üç yığının hepsinden çıkarmaktır; hiçbir koordinat negatif olamaz.
Bir durum kaybeden durumdur (P-pozisyonu) eğer başka bir kaybeden duruma giden hiçbir yasal hamlesi yoksa. İstenen şey, sınır altındaki tüm kaybeden üçlüler için
$$x+y+z$$
toplamını hesaplamaktır.
Bu oyun sonlu, impartial ve normal-play türündedir. Her hamle en az bir koordinatı kesin olarak küçültür; dolayısıyla durum grafiği çevrimsizdir.
Bu yüzden her durum tam olarak iki tipten biridir:
1. kaybeden: hiçbir hamle kaybeden bir duruma gitmez,
2. kazanan: en az bir hamle kaybeden bir duruma gider.
Dolayısıyla asıl mesele kaybeden üçlüleri hızlı biçimde karakterize etmektir.
Kod her durumu \(x\le y\le z\) olacak şekilde sıralanmış tutar. Bir hamleden sonra da yeniden sıralarsak, her oyun durumu tam bir kez temsil edilir.
\((x,y,z)\) durumundan herhangi bir yasal hamle yapıp tekrar sıraladığımızda elde edilen üçlü her zaman leksikografik olarak daha küçüktür: en az bir koordinat azalır, hiçbir koordinat artmaz.
Bu nedenle tüm kanonik üçlüleri leksikografik sırayla taramak geçerlidir; mevcut üçlünün durumunu belirlediğimiz anda, gidebileceği tüm olası kaybeden ardıllar zaten işlenmiş olur.
Sınır \(N\) için kanonik durum sayısı
$$\#\{(x,y,z):0\le x\le y\le z\le N\}=\binom{N+3}{3},$$
olur; bu da asimptotik olarak \(O(N^3)\)'tür.
Kanonik bir \((x,y,z)\) üçlüsünden çıkan her yasal hamle şu yedi aileden birine aittir:
$$ (x-n,y,z),\quad (x,y-n,z),\quad (x,y,z-n), $$
$$ (x-n,y-n,z),\quad (x-n,y,z-n),\quad (x,y-n,z-n),\quad (x-n,y-n,z-n). $$
Kritik gözlem şu: bu ailelerin her biri belirli bir 2-boyutlu imzayı korur. Hızlı çözücü tam olarak bu korunan nicelikleri saklar.
Tek bir yığın azaltılırsa iki yığın değeri aynen kalır. İki veya üç yığın birlikte azaltılırsa bazı farklar değişmeden kalır.
İlgili yedi anahtar şunlardır:
$$ (y,z),\quad (x,z),\quad (x,y), $$
$$ (y-x,z),\quad (z-y,x),\quad (z-x,y),\quad (y-x,z-x). $$
Daha açık yazarsak:
1. yalnız \(x\) azaltılırsa \((y,z)\) korunur,
2. yalnız \(y\) azaltılırsa \((x,z)\) korunur,
3. yalnız \(z\) azaltılırsa \((x,y)\) korunur,
4. \(x\) ve \(y\) birlikte azaltılırsa \((y-x,z)\) korunur,
5. \(y\) ve \(z\) birlikte azaltılırsa \((z-y,x)\) korunur,
6. \(x\) ve \(z\) birlikte azaltılırsa \((z-x,y)\) korunur,
7. üçü birden azaltılırsa \((y-x,z-x)\) korunur.
Bunlar koddaki one, two ve all dizilerinin indekslediği şeylerin aynısıdır.
Varsayalım iki farklı kaybeden durum bu yedi anahtardan birini paylaşıyor olsun. O zaman daha geç gelen durum, değişen koordinatlardaki fark kadar çıkarma yaparak daha erken gelen kaybeden duruma tek hamlede inebilir.
Bu ise kaybeden durum tanımıyla çelişir; çünkü kaybeden durumun başka bir kaybeden duruma hamlesi olamaz.
Dolayısıyla her anahtar en fazla bir kaybeden durum tarafından işgal edilebilir. Bu yüzden tam koordinatları saklamaya gerek yoktur; "daha önce böyle bir kaybeden durum var mı?" sorusu için Boolean doluluk bilgisi yeterlidir.
Hızlı algoritma leksikografik tarama sırasında şu kuralı uygular:
1. Yedi anahtardan herhangi biri daha önce bir kaybeden durum tarafından işaretlenmişse mevcut üçlü kazanan durumdur.
2. Yedi anahtarın hiçbiri işaretli değilse mevcut üçlü kaybeden durumdur.
Bunun nedeni tarama sırası üzerinde kurulan temiz bir indüksiyondur.
Bir anahtar işaretliyse, o anahtara karşılık gelen hamle ailesi mevcut durumdan daha önceki bir kaybeden duruma açık bir geçiş verir.
Hiçbir anahtar işaretli değilse, hiçbir yasal hamle daha önceki bir kaybeden duruma gidemez; çünkü her yasal hamle mutlaka bu yedi anahtardan birini korur. O halde kaybedene giden hamle yoktur ve mevcut durumun kendisi kaybedendir.
Yani bu kural sezgisel bir kestirme değil, P/N-pozisyonlarının özyineli tanımıyla tam eşdeğerdir.
Temel durum
$$ (0,0,0) $$
hiç yasal hamle içermediği için kaybedendir.
Şu durum:
$$ (0,0,1) $$
kazanan durumdur; çünkü üçüncü yığından \(1\) çıkarıp \((0,0,0)\)'a gidilebilir.
Daha ilginç bir örnek
$$ (0,1,2) $$
durumudur; kod bunu checkpoint olarak kaybeden kabul eder. Çünkü daha önce bilinen \((0,0,0)\) kaybedenine göre onun yedi anahtarından hiçbiri dolu değildir.
Bir diğer checkpoint kaybeden durum
$$ (1,3,3) $$
şeklindedir.
Küçük limitlerde ilk kaybeden durumlar
$$ (0,0,0),\ (0,1,2),\ (1,1,4),\ (1,3,3),\ (0,3,5),\ (2,2,6),\dots $$
olarak başlar. Kod ayrıca \((0,0,13)\), \((0,11,11)\) ve \((5,5,5)\) gibi bazı kazanan örnekleri de doğrular.
İmplementasyon yedi ayrı yapı kullanmıyor; bunları hamle türüne göre gruplayıp üç tabloda tutuyor:
1. one[a,b], üç tek-yığın anahtarını saklar: \((y,z)\), \((x,z)\), \((x,y)\),
2. two[a,b], üç çift-yığın anahtarını saklar: \((y-x,z)\), \((z-y,x)\), \((z-x,y)\),
3. all[a,b], üçlü azaltma anahtarını saklar: \((y-x,z-x)\).
Her tablonun boyutu sadece \((N+1)\times(N+1)\) olduğu için bellek kübik değil karesel kalır.
solve_bruteforce_parallel yardımcı fonksiyonu kaybeden durumları doğrudan tanımdan yeniden hesaplar. Bunu sabit
$$ x+y+z $$
katmanları halinde yapar; çünkü her yasal hamle bu toplamı kesin olarak azaltır.
Her durum için açıkça "önceden bilinen bir kaybedene giden hamle var mı?" sorusu sorulur. Bu yavaş yöntem yalnızca checkpoint doğrulaması içindir.
Kod, hızlı çözücünün küçük limitlerde brute-force ile birebir uyuştuğunu doğrular ve ayrıca örnek değer olarak
$$ S(100)=173895 $$
kontrolünü yapar.
solve_fast fonksiyonu üç adet 2-boyutlu bayt dizisi ayırır: one, two ve all. Sonra
$$ 0\le x\le y\le z\le N $$
koşulunu sağlayan tüm üçlüleri iç içe döngülerle tarar.
Mevcut üçlü için yedi anahtara karşılık gelen tablo girişleri kontrol edilir. Eğer bunlardan biri bile 1 ise durum kazanan sayılır ve toplama katkı vermez. Yedisi de 0 ise durum kaybedendir: kod \(x+y+z\) değerini cevaba ekler ve bu yedi girişi işaretler.
sort_triplet, has_move_to_losing_state ve solve_bruteforce_parallel fonksiyonları yalnızca doğrulama ve checkpoint amacıyla vardır. Nihai cevap projeksiyon tabanlı hızlı taramadan gelir.
Tarama tam olarak
$$ \binom{N+3}{3} $$
adet kanonik üçlü inceler; dolayısıyla zaman karmaşıklığı \(O(N^3)\)'tür.
Her durumda sadece sabit sayıda tablo okuma ve yazma vardır. Bellek maliyeti \((N+1)^2\) boyutlu üç 2B tablonun baskın olması nedeniyle \(O(N^2)\)'dir.
Naif retrograde analize göre asıl kazanç şudur: hızlı çözücü her durumdan çıkabilecek tüm yasal hamleleri tek tek dolaşmaz; bu bilgi yedi invariant anahtar sayesinde sabit zamanlı doluluk testlerine sıkıştırılmıştır.
Trabajamos con tres montones escritos en orden canónico:
$$0\le x\le y\le z.$$
Un movimiento legal elige un entero positivo \(n\) y resta ese mismo \(n\) a exactamente un montón, a cualquier pareja de montones o a los tres montones, siempre que ninguna coordenada se vuelva negativa.
Una posición es perdedora (P-position) si no existe un movimiento legal hacia otra posición perdedora. El objetivo es sumar
$$x+y+z$$
sobre todos los tríos perdedores cuyas coordenadas no superan un límite dado.
Este es un juego imparcial, finito y de tipo normal-play. Cada movimiento disminuye estrictamente al menos una coordenada, así que el grafo de estados no tiene ciclos.
Por tanto, toda posición es:
1. perdedora: ningún movimiento llega a una perdedora,
2. ganadora: al menos un movimiento llega a una perdedora.
La tarea real es caracterizar eficientemente los tríos perdedores.
El código guarda cada estado ordenado con \(x\le y\le z\). Después de cualquier movimiento se vuelve a ordenar, de modo que cada estado del juego aparece una sola vez.
Si desde \((x,y,z)\) hacemos un movimiento legal y luego ordenamos, el nuevo trío siempre es lexicográficamente menor: al menos una coordenada baja y ninguna sube.
Por eso un barrido lexicográfico sobre todos los tríos canónicos es correcto: cuando decidimos el estado actual, todos los posibles sucesores perdedores ya fueron procesados.
El número de estados canónicos hasta \(N\) es
$$\#\{(x,y,z):0\le x\le y\le z\le N\}=\binom{N+3}{3},$$
es decir, asintóticamente \(O(N^3)\).
Desde un trío canónico \((x,y,z)\), todo movimiento legal pertenece a una de estas siete familias:
$$ (x-n,y,z),\quad (x,y-n,z),\quad (x,y,z-n), $$
$$ (x-n,y-n,z),\quad (x-n,y,z-n),\quad (x,y-n,z-n),\quad (x-n,y-n,z-n). $$
La observación clave es que cada familia preserva una firma bidimensional concreta. El solucionador rápido almacena precisamente esas cantidades invariantes.
Si reducimos un solo montón, dos tamaños permanecen iguales. Si reducimos dos o tres montones a la vez, ciertas diferencias permanecen iguales.
Las siete claves relevantes son:
$$ (y,z),\quad (x,z),\quad (x,y), $$
$$ (y-x,z),\quad (z-y,x),\quad (z-x,y),\quad (y-x,z-x). $$
En detalle:
1. reducir solo \(x\): se conserva \((y,z)\),
2. reducir solo \(y\): se conserva \((x,z)\),
3. reducir solo \(z\): se conserva \((x,y)\),
4. reducir \(x\) e \(y\): se conserva \((y-x,z)\),
5. reducir \(y\) y \(z\): se conserva \((z-y,x)\),
6. reducir \(x\) y \(z\): se conserva \((z-x,y)\),
7. reducir los tres: se conserva \((y-x,z-x)\).
Estas son exactamente las entradas indexadas por los arreglos one, two y all.
Supongamos que dos posiciones perdedoras distintas compartieran una de las siete claves. Entonces la más tardía podría moverse a la más temprana restando la diferencia correspondiente en la coordenada o coordenadas variables.
Eso contradice la definición de posición perdedora, que no puede tener jugada hacia otra perdedora.
Por lo tanto, cada clave puede estar ocupada por a lo sumo una posición perdedora. De ahí que una tabla booleana sea suficiente: solo importa saber si ya existe alguna perdedora previa con esa clave.
El algoritmo rápido recorre los estados en orden lexicográfico y aplica esta regla:
1. Si alguna de las siete claves ya está ocupada por una perdedora anterior, el estado actual es ganador.
2. Si ninguna clave está ocupada, el estado actual es perdedor.
La razón es una inducción limpia sobre el orden de recorrido.
Si una clave está ocupada, la familia de movimientos asociada produce un movimiento explícito hacia una perdedora anterior.
Si no hay ninguna clave ocupada, entonces ningún movimiento legal puede alcanzar una perdedora anterior, porque todo movimiento legal preserva una de esas siete claves. Así, no existe jugada hacia una perdedora y el estado actual debe ser perdedor.
En otras palabras, la regla no es una heurística: es exactamente equivalente a la definición recursiva de P/N-position.
La posición base
$$ (0,0,0) $$
no tiene movimientos legales, así que es perdedora.
La posición
$$ (0,0,1) $$
es ganadora, porque podemos restar \(1\) del tercer montón y llegar a \((0,0,0)\).
Un ejemplo más interesante es
$$ (0,1,2), $$
que el código usa como ejemplo perdedor. Con respecto a la perdedora conocida \((0,0,0)\), ninguna de sus siete claves está ocupada, así que se marca como perdedora.
Otro ejemplo perdedor de control es
$$ (1,3,3). $$
Para límites pequeños, las primeras posiciones perdedoras son
$$ (0,0,0),\ (0,1,2),\ (1,1,4),\ (1,3,3),\ (0,3,5),\ (2,2,6),\dots $$
El código también verifica varios ejemplos ganadores como \((0,0,13)\), \((0,11,11)\) y \((5,5,5)\).
La implementación no usa siete estructuras separadas, sino tres grupos según el tipo de movimiento:
1. one[a,b] guarda las tres claves de un solo montón: \((y,z)\), \((x,z)\), \((x,y)\),
2. two[a,b] guarda las tres claves de dos montones: \((y-x,z)\), \((z-y,x)\), \((z-x,y)\),
3. all[a,b] guarda la clave de tres montones: \((y-x,z-x)\).
Cada tabla mide solo \((N+1)\times(N+1)\), así que la memoria permanece cuadrática y no cúbica.
La función auxiliar solve_bruteforce_parallel recalcula las posiciones perdedoras directamente desde la definición. Procesa estados por capas de valor constante
$$ x+y+z, $$
porque todo movimiento legal reduce estrictamente esa suma.
Para cada estado pregunta explícitamente si existe una jugada hacia una perdedora ya conocida. Este método lento se usa solo para validar checkpoints.
El código comprueba que el método rápido coincide con brute force en un límite pequeño y además valida el valor de muestra
$$ S(100)=173895. $$
La función solve_fast reserva tres arreglos 2D de bytes: one, two y all. Luego recorre
$$ 0\le x\le y\le z\le N $$
mediante bucles anidados.
Para el trío actual se consultan las siete entradas correspondientes a las siete claves. Si alguna ya vale 1, el estado es ganador y no aporta a la suma. Si las siete valen 0, el estado es perdedor: el código suma \(x+y+z\) y marca esas siete entradas como ocupadas.
Las funciones auxiliares sort_triplet, has_move_to_losing_state y solve_bruteforce_parallel existen solo para validación. La respuesta final se obtiene con el barrido basado en proyecciones.
El barrido examina exactamente
$$ \binom{N+3}{3} $$
tríos canónicos, por lo que el tiempo total es \(O(N^3)\).
Cada estado realiza solo un número constante de lecturas y escrituras. La memoria está dominada por tres tablas 2D de tamaño \((N+1)^2\), así que el espacio es \(O(N^2)\).
La mejora crucial frente a un análisis retrogrado ingenuo es que el solucionador rápido no enumera todos los movimientos legales desde cada estado; las siete claves invariantes comprimen esa información en pruebas de ocupación de tiempo constante.
我们把三堆石子按规范顺序写成
$$0\le x\le y\le z.$$
一次合法操作选择正整数 \(n\)，并把同一个 \(n\) 从恰好一堆、任意两堆，或者三堆同时减去，只要结果没有负数坐标。
如果一个状态没有任何一步可以走到另一个必败态，那么它就是必败态（P-position）。题目要求把所有坐标不超过给定上界的必败三元组的
$$x+y+z$$
全部求和。
这是一个有限的 impartial game，并且采用 normal-play 规则。每一步都会严格减小至少一个坐标，因此状态图没有环。
所以每个状态只能是两类之一：
1. 必败态：没有一步可以到达必败态，
2. 必胜态：至少有一步可以到达必败态。
因此核心任务就是高效刻画所有必败三元组。
代码始终把状态保存为 \(x\le y\le z\) 的排序形式。任何操作之后重新排序，这样每个游戏状态只会表示一次。
从 \((x,y,z)\) 出发做任意合法操作，再重新排序，得到的新三元组一定在字典序上更小：至少一个坐标下降，而且没有坐标上升。
因此按字典序扫描所有规范三元组是成立的：当我们判定当前三元组时，它能到达的所有可能必败后继都已经处理过了。
上界为 \(N\) 时，规范状态总数是
$$\#\{(x,y,z):0\le x\le y\le z\le N\}=\binom{N+3}{3},$$
渐近上就是 \(O(N^3)\)。
从规范三元组 \((x,y,z)\) 出发，所有合法操作恰好分成七类：
$$ (x-n,y,z),\quad (x,y-n,z),\quad (x,y,z-n), $$
$$ (x-n,y-n,z),\quad (x-n,y,z-n),\quad (x,y-n,z-n),\quad (x-n,y-n,z-n). $$
关键观察是：每一类操作都会保持某个二维特征不变。快速算法保存的正是这些不变量。
只减一堆时，另外两堆的数值不变；同时减两堆或三堆时，某些差值不变。
七个关键键值为：
$$ (y,z),\quad (x,z),\quad (x,y), $$
$$ (y-x,z),\quad (z-y,x),\quad (z-x,y),\quad (y-x,z-x). $$
具体对应关系是：
1. 只减 \(x\)：保持 \((y,z)\)，
2. 只减 \(y\)：保持 \((x,z)\)，
3. 只减 \(z\)：保持 \((x,y)\)，
4. 同时减 \(x,y\)：保持 \((y-x,z)\)，
5. 同时减 \(y,z\)：保持 \((z-y,x)\)，
6. 同时减 \(x,z\)：保持 \((z-x,y)\)，
7. 三堆一起减：保持 \((y-x,z-x)\)。
这正是代码中 one、two、all 三张表索引的内容。
假设两个不同的必败态共享七个键中的某一个。那么较晚出现的那个状态，就可以通过相应的那一类减法，直接走到较早的那个必败态。
这与必败态的定义矛盾，因为必败态不能一步走到另一个必败态。
因此每个键最多只能被一个必败态占用。这也解释了为什么布尔占用表就足够了；我们只需要知道“是否已经存在某个更早的必败态占用了这个键”。
快速算法按字典序扫描，并使用下面的规则：
1. 如果七个键中有任意一个已经被更早的必败态占用，那么当前状态是必胜态。
2. 如果七个键全部未占用，那么当前状态是必败态。
原因是对扫描顺序做归纳。
如果某个键已被占用，那么与这个键对应的那一类操作就给出了一个到更早必败态的明确走法。
如果没有任何键被占用，那么任何合法操作都不可能到达更早的必败态，因为每种合法操作都必须保留这七个键中的某一个。于是当前状态没有走向必败态的步，因此它本身就是必败态。
所以这不是启发式技巧，而是与 P/N-position 的递归定义完全等价的判定。
基础状态
$$ (0,0,0) $$
没有任何合法操作，因此它是必败态。
状态
$$ (0,0,1) $$
是必胜态，因为把第三堆减去 \(1\) 就能到 \((0,0,0)\)。
更有代表性的例子是
$$ (0,1,2), $$
代码把它作为必败态检查点。相对于已知必败态 \((0,0,0)\)，它的七个键都没有被占用，所以它被判为必败。
另一个必败检查点是
$$ (1,3,3). $$
在小范围内，最开始的几个必败态是
$$ (0,0,0),\ (0,1,2),\ (1,1,4),\ (1,3,3),\ (0,3,5),\ (2,2,6),\dots $$
代码还检查了一些必胜例子，例如 \((0,0,13)\)、\((0,11,11)\) 和 \((5,5,5)\)。
实现并没有为七个键各建一张表，而是按操作类型分组：
1. one[a,b] 保存三个“减一堆”键：\((y,z)\)、\((x,z)\)、\((x,y)\)，
2. two[a,b] 保存三个“减两堆”键：\((y-x,z)\)、\((z-y,x)\)、\((z-x,y)\)，
3. all[a,b] 保存“三堆同减”键：\((y-x,z-x)\)。
每张表只有 \((N+1)\times(N+1)\) 大小，因此空间复杂度是平方级而不是立方级。
辅助函数 solve_bruteforce_parallel 直接按定义重算必败态。它按常量
$$ x+y+z $$
分层处理，因为每一步合法操作都会严格减小这个总和。
对于每个状态，它显式检查“是否存在一步走到已知必败态”。这个慢方法只用于校验。
代码验证了快速方法在小上界时与 brute force 完全一致，并且检查样例值
$$ S(100)=173895. $$
solve_fast 分配三张二维字节表：one、two 和 all。然后用三重循环枚举
$$ 0\le x\le y\le z\le N $$
的所有三元组。
对当前三元组，代码检查与七个键对应的七个表项。如果其中任何一个已经是 1，那么当前状态就是必胜态，不对答案求和。若七个表项全是 0，则当前状态是必败态：代码把 \(x+y+z\) 加入答案，并把这七个表项全部标记为已占用。
sort_triplet、has_move_to_losing_state 和 solve_bruteforce_parallel 只是为了校验和检查点。最终答案本身来自基于投影键的快速扫描。
扫描总共检查
$$ \binom{N+3}{3} $$
个规范三元组，因此时间复杂度为 \(O(N^3)\)。
每个状态只进行常数次查表和写表。空间主要由三张大小为 \((N+1)^2\) 的二维表占据，所以空间复杂度是 \(O(N^2)\)。
相对朴素 retrograde 分析，真正的改进在于：快速算法不再从每个状态显式枚举全部合法后继，而是把这些信息压缩成七个不变键上的常数时间占用测试。
Рассматриваются три кучи в каноническом порядке
$$0\le x\le y\le z.$$
Разрешенный ход выбирает положительное \(n\) и вычитает одно и то же \(n\) ровно из одной кучи, из любой пары куч или из всех трех куч, если никакая координата не становится отрицательной.
Позиция называется проигрышной (P-position), если из нее нет допустимого хода в другую проигрышную позицию. Требуется просуммировать
$$x+y+z$$
по всем проигрышным тройкам с координатами не выше заданного предела.
Это конечная беспристрастная игра в режиме normal play. Каждый ход строго уменьшает хотя бы одну координату, поэтому граф состояний ацикличен.
Значит, каждая позиция принадлежит одному из двух типов:
1. проигрышная: ни один ход не ведет в проигрышную позицию,
2. выигрышная: хотя бы один ход ведет в проигрышную позицию.
Следовательно, вся задача сводится к эффективному описанию проигрышных троек.
Код хранит каждое состояние в отсортированном виде \(x\le y\le z\). После любого хода можно снова отсортировать тройку, и тогда каждое состояние игры представлено ровно один раз.
Если из \((x,y,z)\) сделать допустимый ход и затем отсортировать результат, новая тройка всегда будет лексикографически меньше исходной: хотя бы одна координата уменьшается, а ни одна не увеличивается.
Поэтому лексикографический проход по всем каноническим тройкам корректен: когда мы решаем статус текущей тройки, все возможные проигрышные потомки уже обработаны.
Число канонических состояний до предела \(N\) равно
$$\#\{(x,y,z):0\le x\le y\le z\le N\}=\binom{N+3}{3},$$
то есть асимптотически это \(O(N^3)\).
Из канонической тройки \((x,y,z)\) любой допустимый ход относится к одному из семи семейств:
$$ (x-n,y,z),\quad (x,y-n,z),\quad (x,y,z-n), $$
$$ (x-n,y-n,z),\quad (x-n,y,z-n),\quad (x,y-n,z-n),\quad (x-n,y-n,z-n). $$
Ключевое наблюдение состоит в том, что каждое семейство сохраняет некоторую двумерную сигнатуру. Именно эти инварианты и хранит быстрый алгоритм.
Если уменьшается только одна куча, две другие величины не меняются. Если одновременно уменьшаются две или три кучи, неизменными остаются некоторые разности.
Нужные семь ключей таковы:
$$ (y,z),\quad (x,z),\quad (x,y), $$
$$ (y-x,z),\quad (z-y,x),\quad (z-x,y),\quad (y-x,z-x). $$
Подробно:
1. уменьшаем только \(x\): сохраняется \((y,z)\),
2. уменьшаем только \(y\): сохраняется \((x,z)\),
3. уменьшаем только \(z\): сохраняется \((x,y)\),
4. уменьшаем \(x\) и \(y\): сохраняется \((y-x,z)\),
5. уменьшаем \(y\) и \(z\): сохраняется \((z-y,x)\),
6. уменьшаем \(x\) и \(z\): сохраняется \((z-x,y)\),
7. уменьшаем все три: сохраняется \((y-x,z-x)\).
Именно эти индексы используются в массивах one, two и all.
Предположим, две разные проигрышные позиции имеют общий ключ из этих семи. Тогда более поздняя позиция могла бы одним ходом перейти в более раннюю, вычтя нужную разность в изменяющихся координатах.
Это противоречит определению проигрышной позиции, у которой не должно быть хода в другую проигрышную.
Следовательно, каждый ключ может быть занят не более чем одной проигрышной позицией. Поэтому достаточно булевой таблицы занятости: важно только знать, существует ли уже более ранняя проигрышная позиция с этим ключом.
Быстрый алгоритм идет по тройкам в лексикографическом порядке и использует правило:
1. Если хотя бы один из семи ключей уже занят более ранней проигрышной позицией, то текущая тройка выигрышная.
2. Если ни один ключ не занят, то текущая тройка проигрышная.
Причина - простая индукция по порядку обхода.
Если ключ занят, соответствующее семейство ходов дает явный ход в более раннюю проигрышную позицию.
Если ни один ключ не занят, то никакой допустимый ход не может привести к более ранней проигрышной позиции, потому что любой допустимый ход обязан сохранять один из этих семи ключей. Значит, хода в проигрышную позицию нет, и текущая тройка сама проигрышная.
Итак, это не эвристика, а точный эквивалент рекурсивного определения P/N-позиций.
Базовая позиция
$$ (0,0,0) $$
не имеет допустимых ходов, значит она проигрышная.
Позиция
$$ (0,0,1) $$
выигрышная, потому что можно вычесть \(1\) из третьей кучи и попасть в \((0,0,0)\).
Более интересный пример:
$$ (0,1,2), $$
который код использует как контрольную проигрышную позицию. Относительно уже известной проигрышной позиции \((0,0,0)\) ни один из его семи ключей не занят, поэтому он помечается как проигрышный.
Еще один контрольный проигрышный пример:
$$ (1,3,3). $$
При малых пределах первые проигрышные позиции таковы:
$$ (0,0,0),\ (0,1,2),\ (1,1,4),\ (1,3,3),\ (0,3,5),\ (2,2,6),\dots $$
Код также проверяет несколько выигрышных примеров: \((0,0,13)\), \((0,11,11)\), \((5,5,5)\).
Реализация не хранит семь отдельных структур, а группирует их по типу хода:
1. one[a,b] хранит три ключа для одного уменьшаемого кучи: \((y,z)\), \((x,z)\), \((x,y)\),
2. two[a,b] хранит три ключа для двух уменьшаемых куч: \((y-x,z)\), \((z-y,x)\), \((z-x,y)\),
3. all[a,b] хранит ключ для уменьшения всех трех: \((y-x,z-x)\).
Каждая таблица имеет размер всего \((N+1)\times(N+1)\), поэтому память остается квадратичной, а не кубической.
Вспомогательная функция solve_bruteforce_parallel пересчитывает проигрышные позиции напрямую по определению. Она обрабатывает состояния слоями с постоянной суммой
$$ x+y+z, $$
потому что любой допустимый ход строго уменьшает эту сумму.
Для каждого состояния она явно спрашивает, существует ли ход в уже известную проигрышную позицию. Этот медленный метод нужен только для проверки.
Код подтверждает совпадение быстрого метода с brute force на малом пределе и дополнительно проверяет образцовое значение
$$ S(100)=173895. $$
Функция solve_fast выделяет три двумерных массива байтов: one, two и all. Затем она перебирает все тройки
$$ 0\le x\le y\le z\le N $$
вложенными циклами.
Для текущей тройки проверяются семь ячеек таблиц, соответствующих семи ключам. Если хотя бы одна из них уже равна 1, позиция выигрышная и ничего не добавляет в сумму. Если все семь равны 0, позиция проигрышная: код добавляет \(x+y+z\) к ответу и помечает все семь ячеек как занятые.
Функции sort_triplet, has_move_to_losing_state и solve_bruteforce_parallel нужны только для валидации и checkpoint-проверок. Окончательный ответ вычисляется именно проекционным сканированием.
Проход рассматривает ровно
$$ \binom{N+3}{3} $$
канонических троек, поэтому время работы равно \(O(N^3)\).
На каждое состояние приходится только константное число чтений и записей. Память определяется тремя двумерными таблицами размера \((N+1)^2\), то есть это \(O(N^2)\).
Главное улучшение по сравнению с наивным ретроградным анализом состоит в том, что быстрый алгоритм не перебирает все допустимые ходы из каждого состояния; семь инвариантных ключей сжимают эту информацию до проверок занятости за постоянное время.
نكتب أحجام الأكوام الثلاثة بالترتيب المعياري
$$0\le x\le y\le z.$$
الحركة القانونية تختار عددًا موجبًا \(n\) ثم تطرح هذا العدد نفسه من كومة واحدة فقط، أو من أي زوج من الأكوام، أو من الأكوام الثلاثة معًا، بشرط ألا تصبح أي قيمة سالبة.
تكون الحالة خاسرة إذا لم توجد منها نقلة قانونية إلى حالة خاسرة أخرى. والمطلوب هو جمع
$$x+y+z$$
على جميع الثلاثيات الخاسرة التي لا تتجاوز إحداثياتها حدًا معينًا.
هذه لعبة impartial منتهية وتعمل وفق قاعدة normal play. كل نقلة تُنقص إحداثيًا واحدًا على الأقل نقصانًا صارمًا، لذلك فإن مخطط الحالات بلا دورات.
وعليه فكل حالة تكون واحدة من اثنتين:
1. خاسرة: لا توجد منها نقلة إلى حالة خاسرة،
2. رابحة: توجد منها نقلة واحدة على الأقل إلى حالة خاسرة.
إذن جوهر المسألة هو توصيف الثلاثيات الخاسرة بكفاءة.
يخزن الكود كل حالة بعد ترتيبها بحيث \(x\le y\le z\). وبعد أي نقلة نعيد الترتيب، وبذلك تُمثل كل حالة في اللعبة مرة واحدة فقط.
إذا انتقلنا من \((x,y,z)\) إلى حالة لاحقة ثم رتبناها، فإن الثلاثي الجديد يكون دائمًا أصغر معجميًا من الثلاثي الحالي: هناك إحداثي واحد على الأقل ينخفض، ولا يوجد أي إحداثي يرتفع.
لذلك فإن المسح المعجمي لجميع الثلاثيات المعيارية صحيح؛ فعندما نحدد حالة الثلاثي الحالي تكون كل الحالات الخاسرة الممكن الوصول إليها قد عولجت من قبل.
عدد الحالات المعيارية حتى الحد \(N\) هو
$$\#\{(x,y,z):0\le x\le y\le z\le N\}=\binom{N+3}{3},$$
وهو asymptotically من الرتبة \(O(N^3)\).
من الثلاثي المعياري \((x,y,z)\) تنتمي كل نقلة قانونية إلى واحدة من هذه العائلات السبع:
$$ (x-n,y,z),\quad (x,y-n,z),\quad (x,y,z-n), $$
$$ (x-n,y-n,z),\quad (x-n,y,z-n),\quad (x,y-n,z-n),\quad (x-n,y-n,z-n). $$
الملاحظة الأساسية هي أن كل عائلة تحفظ بصمة ثنائية الأبعاد معينة. والحل السريع يخزن هذه الكميات المحفوظة بالضبط.
عند إنقاص كومة واحدة فقط تبقى قيمتا الكومتين الأخريين كما هما. وعند إنقاص كومتين أو ثلاثًا معًا تبقى بعض الفروق ثابتة.
المفاتيح السبعة المهمة هي:
$$ (y,z),\quad (x,z),\quad (x,y), $$
$$ (y-x,z),\quad (z-y,x),\quad (z-x,y),\quad (y-x,z-x). $$
وبصورة مباشرة:
1. إنقاص \(x\) فقط يحفظ \((y,z)\)،
2. إنقاص \(y\) فقط يحفظ \((x,z)\)،
3. إنقاص \(z\) فقط يحفظ \((x,y)\)،
4. إنقاص \(x\) و\(y\) معًا يحفظ \((y-x,z)\)،
5. إنقاص \(y\) و\(z\) معًا يحفظ \((z-y,x)\)،
6. إنقاص \(x\) و\(z\) معًا يحفظ \((z-x,y)\)،
7. إنقاص الثلاثة معًا يحفظ \((y-x,z-x)\).
وهذه هي بالضبط الفهارس التي تستخدمها الجداول one وtwo وall.
لو افترضنا أن حالتين خاسرتين مختلفتين تشتركان في أحد هذه المفاتيح السبعة، لكان بإمكان الحالة المتأخرة أن تصل إلى الحالة الأسبق بطرحة واحدة في العائلة المناسبة.
وهذا يناقض تعريف الحالة الخاسرة، لأنها يجب ألا تملك نقلة إلى حالة خاسرة أخرى.
إذن لا يمكن أن يشغل أي مفتاح أكثر من حالة خاسرة واحدة. ولهذا تكفي جداول Boolean؛ فنحن لا نحتاج إلا إلى معرفة هل استُخدم المفتاح من قبل بواسطة حالة خاسرة أسبق أم لا.
تقوم الخوارزمية السريعة بمسح الثلاثيات ترتيبيًا وتطبق القاعدة التالية:
1. إذا كان أي مفتاح من المفاتيح السبعة مشغولًا سلفًا بواسطة حالة خاسرة أسبق، فالحالة الحالية رابحة.
2. إذا لم يكن أي مفتاح مشغولًا، فالحالة الحالية خاسرة.
وسبب ذلك برهان استقرائي مباشر على ترتيب المسح.
إذا كان مفتاح ما مشغولًا، فإن عائلة النقلات المقابلة له تعطي نقلة صريحة إلى حالة خاسرة سابقة.
أما إذا لم يكن أي مفتاح مشغولًا، فلا يمكن لأي نقلة قانونية أن تصل إلى حالة خاسرة سابقة، لأن كل نقلة قانونية لا بد أن تحفظ واحدًا من هذه المفاتيح السبعة. وعندئذ لا توجد نقلة إلى حالة خاسرة، فتكون الحالة الحالية خاسرة.
إذن هذه القاعدة ليست مجرد heuristic، بل هي مكافئة تمامًا للتعريف العودي لحالات P وN.
الحالة الأساسية
$$ (0,0,0) $$
لا تحتوي أي نقلة قانونية، لذلك فهي خاسرة.
أما الحالة
$$ (0,0,1) $$
فهي رابحة، لأننا نستطيع طرح \(1\) من الكومة الثالثة والوصول إلى \((0,0,0)\).
ومثال أكثر أهمية هو
$$ (0,1,2), $$
وهو مثال خاسر يستعمله الكود ضمن نقاط التحقق. فبالنسبة إلى الحالة الخاسرة المعروفة \((0,0,0)\) لا يكون أي من مفاتيحه السبعة مشغولًا، ولذلك يُصنف على أنه خاسر.
ومثال خاسر آخر في نقاط التحقق هو
$$ (1,3,3). $$
وعند الحدود الصغيرة تبدأ الحالات الخاسرة كما يلي:
$$ (0,0,0),\ (0,1,2),\ (1,1,4),\ (1,3,3),\ (0,3,5),\ (2,2,6),\dots $$
كما يتحقق الكود أيضًا من أمثلة رابحة مثل \((0,0,13)\) و\((0,11,11)\) و\((5,5,5)\).
لا تستعمل البنية سبعة تراكيب منفصلة، بل تجمعها بحسب نوع النقلة:
1. one[a,b] يخزن مفاتيح إنقاص كومة واحدة: \((y,z)\) و\((x,z)\) و\((x,y)\)،
2. two[a,b] يخزن مفاتيح إنقاص كومتين: \((y-x,z)\) و\((z-y,x)\) و\((z-x,y)\)،
3. all[a,b] يخزن مفتاح إنقاص الأكوام الثلاثة: \((y-x,z-x)\).
وكل جدول حجمه \((N+1)\times(N+1)\) فقط، لذلك تبقى الذاكرة من الرتبة التربيعية لا التكعيبية.
تعيد الدالة المساعدة solve_bruteforce_parallel حساب الحالات الخاسرة مباشرة من التعريف. وهي تعالج الحالات على طبقات ذات مجموع ثابت
$$ x+y+z, $$
لأن كل نقلة قانونية تُنقص هذا المجموع نقصانًا صارمًا.
ولكل حالة تفحص صراحة هل توجد نقلة إلى حالة خاسرة معروفة سابقًا. وهذه الطريقة البطيئة مخصصة للتحقق فقط.
يتأكد الكود من تطابق الحل السريع مع brute force عند حد صغير، ويتحقق أيضًا من قيمة العينة
$$ S(100)=173895. $$
تخصص الدالة solve_fast ثلاثة جداول بايت ثنائية الأبعاد: one وtwo وall. ثم تمسح جميع الثلاثيات التي تحقق
$$ 0\le x\le y\le z\le N $$
باستعمال حلقات متداخلة.
وبالنسبة إلى الثلاثي الحالي، يفحص البرنامج الخانات السبع المقابلة للمفاتيح السبعة. فإذا كانت إحداها معلَّمة مسبقًا، كانت الحالة رابحة ولا تضيف شيئًا إلى المجموع. وإذا كانت الخانات السبع كلها صفرًا، كانت الحالة خاسرة: عندها يضيف الكود \(x+y+z\) إلى الجواب ويعلّم هذه الخانات السبع.
أما الدوال sort_triplet وhas_move_to_losing_state وsolve_bruteforce_parallel فهي موجودة فقط للتحقق ونقاط الفحص. والجواب النهائي نفسه ينتج من المسح السريع المعتمد على المفاتيح الإسقاطية.
يمر المسح على
$$ \binom{N+3}{3} $$
ثلاثيات معيارية بالضبط، ولذلك يكون الزمن \(O(N^3)\).
وفي كل حالة توجد فقط قراءة وكتابة بعدد ثابت. أما الذاكرة فتسيطر عليها ثلاثة جداول ثنائية الأبعاد بحجم \((N+1)^2\)، لذا يكون التعقيد المكاني \(O(N^2)\).
والتحسين الحاسم مقارنةً بالتحليل الرجعي الساذج هو أن الحل السريع لا يعدّ جميع النقلات القانونية من كل حالة، بل يضغط هذه المعلومة في سبعة مفاتيح ثابتة يمكن اختبارها في زمن ثابت.