This is a two-pile impartial game. After sorting each position so that \(a \le b\), a legal move subtracts a positive multiple of one of the vectors
$$ (1,0),\ (0,1),\ (1,1),\ (1,2),\ (2,1), $$
as long as both piles stay nonnegative; after the subtraction we sort again. Let \(P\)-positions be the losing positions. The target function is
$$f(M)=\sum_{\substack{(a,b)\in P\\0\lt a+b\le M}} (a+b).$$
A full dynamic program over all states with \(a+b\le 10^7\) would be far too slow, so the implementation constructs the losing positions directly.
The terminal state \((0,0)\) is the first \(P\)-position. The nonzero \(P\)-positions are then generated in increasing order of the first coordinate.
Suppose two losing positions shared a positive coordinate. For example, if \((c,d)\) and \((c,e)\) with \(d\lt e\) were both losing, then the larger one could move to the smaller one by subtracting \(e-d\) from a single pile. That is impossible for two \(P\)-positions.
So every positive integer can appear in at most one coordinate among the nonzero losing pairs. This suggests the usual Wythoff-style greedy rule:
take the smallest positive integer not used yet as the next first coordinate \(x\), then choose the smallest \(y\gt x\) that is not attacked by any earlier losing pair.
The implementations follow exactly this rule, and they verify it against brute force for small bounds.
Let \((a,b)\) be an earlier losing position with \(a\lt b\), and let \((x,y)\) be a new candidate with \(x\lt y\).
Axis moves already explain why \(x\) and \(y\) cannot reuse any earlier coordinate. The proportional moves give three more forbidden affine invariants.
If \((x,y)\) could reach \((a,b)\) by a diagonal move \((n,n)\), then
$$x-a=n,\qquad y-b=n,$$
so
$$y-x=b-a.$$
If \((x,y)\) could reach \((a,b)\) by a \((1,2)\)-type move without changing order after the subtraction, then
$$x-a=n,\qquad y-b=2n,$$
which is equivalent to
$$y-2x=b-2a.$$
If \((x,y)\) could reach \((a,b)\) by a \((2,1)\)-type move without changing order, then
$$x-a=2n,\qquad y-b=n,$$
which gives
$$2y-x=2b-a.$$
Therefore each earlier losing pair forbids one coordinate family and three affine families:
$$y\notin U,\qquad y-x\notin D,\qquad y-2x\notin T,\qquad 2y-x\notin S.$$
The two proportional moves have another possibility: after subtracting \((n,2n)\) or \((2n,n)\), the two coordinates may need to be swapped before we compare with \((a,b)\).
For a swapped \((1,2)\)-type move we must have
$$x-n=b,\qquad y-2n=a,$$
so the same candidate is forbidden when
$$y-2x=a-2b.$$
For a swapped \((2,1)\)-type move we get
$$x-2n=b,\qquad y-n=a,$$
hence
$$2y-x=2a-b.$$
These two extra affine values matter only when the new first coordinate has already passed the old second coordinate, namely when
$$x\gt b.$$
That is why the implementation does not insert them immediately. Instead it schedules them to become active starting at \(x=b+1\). This event mechanism is the key detail that keeps the greedy construction correct.
For any forbidden set \(F\), define the successor operator
$$\operatorname{next}_F(t)=\min\{u\ge t:u\notin F\}.$$
For a fixed first coordinate \(x\), the search starts at \(y=x+1\) and repeatedly pushes \(y\) upward until all constraints are satisfied:
$$y\leftarrow \operatorname{next}_U(y),$$
$$y\leftarrow x+\operatorname{next}_D(y-x),$$
$$y\leftarrow 2x+\operatorname{next}_T(y-2x),$$
and finally \(2y-x\) is pushed past the forbidden values in \(S\).
Each update only increases \(y\), so the process reaches a fixed point. That fixed point is the smallest admissible partner for \(x\), hence the next losing pair.
The quantity \(2y-x\) always has the same parity as \(x\). The implementation uses that fact to store the \(S\)-family in two parity classes, but mathematically it is still the single condition \(2y-x\notin S\).
Start from the terminal position \((0,0)\). It already forbids the affine value \(0\) in the diagonal, \((1,2)\), and \((2,1)\) families.
For \(x=1\), the first candidate is \(y=2\). This fails because
$$y-2x=2-2=0,$$
which would allow the move \((1,2)\) to \((0,0)\). The next possibility is \(y=3\), which is valid, so the first nonzero losing pair is
$$ (1,3). $$
For \(x=2\), \(y=3\) is impossible because \(3\) is already used. Then \(y=4\) fails since
$$y-x=2,$$
matching the diagonal invariant from \((1,3)\). Next \(y=5\) fails because
$$y-2x=1,$$
matching the \((1,2)\)-invariant from \((1,3)\). Therefore the next valid pair is
$$ (2,6). $$
The coordinate \(x=3\) is skipped because it is already used. Before processing \(x=4\), the delayed constraints coming from \((1,3)\) become active since now \(x\gt 3\). The smallest valid partner is \(y=5\), giving
$$ (4,5). $$
These are exactly the losing pairs with sum at most \(10\), so
$$f(10)=4+8+9=21,$$
which matches the checkpoint used by the implementation.
The C++, Python, and Java implementations all maintain the same logical state:
one successor structure for used coordinates, one for forbidden diagonal differences, one for forbidden values of \(y-2x\), and a parity-split representation of the forbidden values of \(2y-x\). They also maintain a min-priority queue of delayed affine constraints that will become active when \(x\) passes a stored threshold.
At each step, the implementation activates all events whose threshold has been reached, chooses the smallest unused \(x\), and then runs the fixed-point lifting process described above to obtain the smallest legal \(y\).
Once \((x,y)\) is accepted, both coordinates are marked as used. The immediate invariants
$$b-a,\qquad b-2a,\qquad 2b-a$$
for that new losing pair are inserted right away, and the swapped-case invariants
$$a-2b,\qquad 2a-b$$
are scheduled to activate starting at the first future step with \(x\gt b\).
If \(x+y\le M\), the pair contributes \(x+y\) to the answer. Otherwise it still matters structurally, because its coordinates and affine invariants can block later pairs whose first coordinate is still at most \(M\).
The implementations also include a small brute-force comparison against the win/lose dynamic program on tiny bounds, which is how the construction is sanity-checked.
Let \(P(M)\) be the number of losing pairs generated before the first coordinate exceeds \(M\). Every generated pair causes a constant number of successor queries, a constant number of insertions, one event insertion, and later one event removal.
The successor structures use path compression, so their operations are amortized extremely close to constant time. The priority queue contributes a logarithmic factor. Therefore the overall running time is
$$O\!\left(P(M)\log P(M)\right),$$
with near-linear practical behavior. The memory usage is
$$O\!\left(P(M)\right).$$
Because no positive coordinate is ever reused, \(P(M)\) itself grows only linearly with the search range, which is why the method scales to the required bound.
Dies ist ein unparteiisches Spiel mit zwei Haufen. Nach dem Sortieren jeder Stellung zu \(a \le b\) darf man ein positives Vielfaches eines der Vektoren
$$ (1,0),\ (0,1),\ (1,1),\ (1,2),\ (2,1) $$
abziehen, solange beide Haufen nichtnegativ bleiben; danach wird erneut sortiert. \(P\)-Positionen sind die Verluststellungen. Gesucht ist
$$f(M)=\sum_{\substack{(a,b)\in P\\0\lt a+b\le M}} (a+b).$$
Ein vollständiges dynamisches Programm über alle Zustände mit \(a+b\le 10^7\) wäre zu teuer, daher konstruiert die Implementierung die Verlustpositionen direkt.
Die Endstellung \((0,0)\) ist die erste \(P\)-Position. Die positiven \(P\)-Positionen werden anschließend in aufsteigender Reihenfolge der ersten Koordinate erzeugt.
Angenommen, zwei Verlustpositionen hätten eine positive Koordinate gemeinsam. Wären zum Beispiel \((c,d)\) und \((c,e)\) mit \(d\lt e\) beide verlierend, dann könnte man aus der größeren durch Subtraktion von \(e-d\) aus genau einem Haufen in die kleinere ziehen. Das darf zwischen zwei \(P\)-Positionen nicht passieren.
Also kann jede positive ganze Zahl in den nichttrivialen Verlustpaaren höchstens einmal als Koordinate auftreten. Daraus ergibt sich die übliche Wythoff-artige Greedy-Regel:
nimm die kleinste noch unbenutzte positive Zahl als nächste erste Koordinate \(x\), und wähle dann das kleinste \(y\gt x\), das von keiner früheren Verlustposition angegriffen wird.
Genau dieses Verfahren verwenden die Implementierungen; für kleine Schranken wird es zusätzlich per Brute Force überprüft.
Sei \((a,b)\) eine frühere Verlustposition mit \(a\lt b\), und \((x,y)\) ein neuer Kandidat mit \(x\lt y\).
Achsen-Züge erklären bereits, warum weder \(x\) noch \(y\) eine frühere Koordinate wiederverwenden dürfen. Die proportionalen Züge liefern drei weitere verbotene affine Invarianten.
Falls \((x,y)\) durch einen Diagonalzug \((n,n)\) nach \((a,b)\) gelangen könnte, gilt
$$x-a=n,\qquad y-b=n,$$
also
$$y-x=b-a.$$
Falls \((x,y)\) durch einen Zug vom Typ \((1,2)\) ohne anschließendes Vertauschen nach \((a,b)\) gelangen könnte, dann
$$x-a=n,\qquad y-b=2n,$$
und damit
$$y-2x=b-2a.$$
Für einen Zug vom Typ \((2,1)\) ohne Vertauschung erhält man
$$x-a=2n,\qquad y-b=n,$$
also
$$2y-x=2b-a.$$
Jede frühere Verlustposition verbietet damit eine Koordinatenfamilie und drei affine Familien:
$$y\notin U,\qquad y-x\notin D,\qquad y-2x\notin T,\qquad 2y-x\notin S.$$
Bei den beiden proportionalen Zügen kann nach der Subtraktion eine Vertauschung der Koordinaten nötig sein, bevor man mit \((a,b)\) vergleicht.
Für einen vertauschten Zug vom Typ \((1,2)\) muss gelten
$$x-n=b,\qquad y-2n=a,$$
also ist der Kandidat auch dann verboten, wenn
$$y-2x=a-2b.$$
Für einen vertauschten Zug vom Typ \((2,1)\) erhält man
$$x-2n=b,\qquad y-n=a,$$
und folglich
$$2y-x=2a-b.$$
Diese beiden zusätzlichen affinen Werte werden aber erst relevant, wenn die neue erste Koordinate bereits über der alten zweiten Koordinate liegt, also bei
$$x\gt b.$$
Deshalb fügt die Implementierung sie nicht sofort ein, sondern plant ihre Aktivierung erst ab \(x=b+1\). Gerade dieser Ereignismechanismus macht die greedy Konstruktion korrekt.
Für eine verbotene Menge \(F\) definieren wir den Successor-Operator
$$\operatorname{next}_F(t)=\min\{u\ge t:u\notin F\}.$$
Für festes \(x\) startet die Suche bei \(y=x+1\) und schiebt \(y\) wiederholt nach oben, bis alle Bedingungen erfüllt sind:
$$y\leftarrow \operatorname{next}_U(y),$$
$$y\leftarrow x+\operatorname{next}_D(y-x),$$
$$y\leftarrow 2x+\operatorname{next}_T(y-2x),$$
und zuletzt wird auch \(2y-x\) über die verbotenen Werte in \(S\) hinweggehoben.
Jeder Schritt erhöht \(y\), daher endet der Prozess in einem Fixpunkt. Dieser Fixpunkt ist genau der kleinste zulässige Partner zu \(x\) und damit die nächste Verlustposition.
Die Größe \(2y-x\) hat stets dieselbe Parität wie \(x\). Die Implementierung speichert die \(S\)-Familie deshalb in zwei Paritätsklassen; mathematisch bleibt es aber dieselbe Bedingung \(2y-x\notin S\).
Ausgangspunkt ist die Endstellung \((0,0)\). Sie verbietet bereits den affinen Wert \(0\) in der Diagonal-, \((1,2)\)- und \((2,1)\)-Familie.
Für \(x=1\) ist der erste Kandidat \(y=2\). Das scheitert, weil
$$y-2x=2-2=0,$$
und damit ein \((1,2)\)-Zug nach \((0,0)\) möglich wäre. Die nächste Möglichkeit ist \(y=3\), und diese ist zulässig. Also ist das erste nichttriviale Verlustpaar
$$ (1,3). $$
Für \(x=2\) scheidet \(y=3\) aus, weil \(3\) schon benutzt ist. Dann scheitert \(y=4\) wegen
$$y-x=2,$$
also wegen derselben Diagonalklasse wie bei \((1,3)\). Danach scheitert \(y=5\), weil
$$y-2x=1,$$
und damit dieselbe \((1,2)\)-Invariante wie bei \((1,3)\) getroffen wird. Folglich ist das nächste zulässige Paar
$$ (2,6). $$
Die Koordinate \(x=3\) wird übersprungen, weil sie bereits benutzt ist. Vor der Verarbeitung von \(x=4\) werden die verzögerten Nebenbedingungen von \((1,3)\) aktiv, da jetzt \(x\gt 3\) gilt. Der kleinste gültige Partner ist \(y=5\), also erhält man
$$ (4,5). $$
Das sind genau die Verlustpaare mit Summe höchstens \(10\), also
$$f(10)=4+8+9=21,$$
genau der Kontrollwert aus der Implementierung.
Die C++-, Python- und Java-Implementierungen verwalten alle denselben logischen Zustand:
eine Successor-Struktur für benutzte Koordinaten, eine für verbotene Diagonaldifferenzen, eine für verbotene Werte von \(y-2x\) sowie eine nach Parität getrennte Darstellung der verbotenen Werte von \(2y-x\). Zusätzlich gibt es eine Min-Prioritätswarteschlange für verzögerte affine Nebenbedingungen, die ab einer gespeicherten Schwelle aktiv werden.
In jedem Schritt aktiviert die Implementierung zunächst alle Ereignisse, deren Schwelle erreicht ist. Dann wählt sie das kleinste unbenutzte \(x\) und bestimmt mittels des oben beschriebenen Fixpunktverfahrens das kleinste zulässige \(y\).
Ist \((x,y)\) akzeptiert, werden beide Koordinaten als benutzt markiert. Die unmittelbaren Invarianten
$$b-a,\qquad b-2a,\qquad 2b-a$$
dieses neuen Verlustpaares werden sofort eingetragen, und die Vertauschungs-Invarianten
$$a-2b,\qquad 2a-b$$
werden so vorgemerkt, dass sie erst ab dem ersten zukünftigen Schritt mit \(x\gt b\) aktiv werden.
Falls \(x+y\le M\), trägt das Paar \(x+y\) zur Antwort bei. Liegt die Summe darüber, ist das Paar trotzdem strukturell relevant, weil seine Koordinaten und affinen Invarianten spätere Paare mit erster Koordinate höchstens \(M\) blockieren können.
Außerdem enthalten die Implementierungen einen kleinen Brute-Force-Abgleich mit dem Gewinn/Verlust-DP für sehr kleine Grenzen; so wird die Konstruktion gegengeprüft.
Sei \(P(M)\) die Anzahl der erzeugten Verlustpaare, bevor die erste Koordinate größer als \(M\) wird. Jedes erzeugte Paar verursacht nur konstant viele Successor-Abfragen, konstant viele Einfügungen, genau ein Ereignis in die Warteschlange und später genau ein Entfernen daraus.
Die Successor-Strukturen verwenden Pfadkompression, daher sind ihre Operationen amortisiert praktisch konstant. Die Prioritätswarteschlange liefert den logarithmischen Faktor. Insgesamt ergibt sich daher
$$O\!\left(P(M)\log P(M)\right)$$
Zeit bei praktisch nahezu linearem Verhalten und
$$O\!\left(P(M)\right)$$
Speicher. Da keine positive Koordinate jemals erneut benutzt wird, wächst auch \(P(M)\) nur linear mit dem Suchbereich, was die Skalierung bis zur geforderten Grenze erklärt.
Bu, iki yığınlı tarafsız bir oyundur. Her durum önce \(a \le b\) olacak şekilde sıralanır. Sonra aşağıdaki vektörlerden birinin pozitif katı çıkarılabilir:
$$ (1,0),\ (0,1),\ (1,1),\ (1,2),\ (2,1). $$
Çıkarma sonunda her iki yığın da negatif olmayacak ve ardından durum tekrar sıralanacaktır. \(P\)-pozisyonları kaybeden durumlardır. İstenen toplam
$$f(M)=\sum_{\substack{(a,b)\in P\\0\lt a+b\le M}} (a+b).$$
\(a+b\le 10^7\) sınırına kadar tüm durumlar üzerinde klasik bir dinamik program kurmak çok pahalıdır; bu yüzden uygulama kaybeden pozisyonları doğrudan inşa eder.
Terminal durum \((0,0)\) ilk \(P\)-pozisyonudur. Pozitif \(P\)-pozisyonları ise birinci koordinat artan sırada üretilir.
İki farklı kaybeden pozisyon aynı pozitif koordinatı paylaşsaydı çelişki doğardı. Örneğin \((c,d)\) ve \((c,e)\) için \(d\lt e\) ise, büyük olandan tek bir yığından \(e-d\) çıkarılarak küçüğe gidilebilir. İki \(P\)-pozisyon arasında böyle bir hamle olamaz.
Demek ki her pozitif tamsayı, sıfırdan farklı kaybeden çiftlerin koordinatları arasında en fazla bir kez görünebilir. Bu da Wythoff benzeri şu açgözlü kuralı önerir:
henüz kullanılmamış en küçük pozitif tamsayıyı yeni birinci koordinat \(x\) olarak al, sonra da \(x\)'ten büyük olup önceki hiçbir kaybeden çift tarafından saldırı almayan en küçük \(y\)'yi seç.
Uygulamalar tam olarak bunu yapar ve küçük sınırlar için brute-force sonuçlarla karşılaştırarak yaklaşımı doğrular.
\((a,b)\) daha önce bulunmuş bir kaybeden çift ve \((x,y)\) de \(x\lt y\) olacak şekilde yeni aday olsun.
Eksen boyunca yapılan hamleler zaten \(x\) ve \(y\)'nin önceki koordinatlardan herhangi birini tekrar kullanamayacağını açıklar. Oransal hamleler ise üç ek affine invariant verir.
Eğer \((x,y)\), \((n,n)\) hamlesiyle \((a,b)\)'ye gidebiliyorsa
$$x-a=n,\qquad y-b=n,$$
dolayısıyla
$$y-x=b-a.$$
Eğer \((x,y)\), çıkarma sonrası sıra bozulmadan \((1,2)\) tipinde bir hamleyle \((a,b)\)'ye gidebiliyorsa
$$x-a=n,\qquad y-b=2n,$$
ve bu da
$$y-2x=b-2a$$
anlamına gelir.
Benzer şekilde, sıra bozulmadan \((2,1)\) tipinde bir hamle için
$$x-a=2n,\qquad y-b=n,$$
yazılır ve
$$2y-x=2b-a$$
elde edilir.
Böylece her eski kaybeden çift, bir koordinat ailesi ve üç affine aile yasaklar:
$$y\notin U,\qquad y-x\notin D,\qquad y-2x\notin T,\qquad 2y-x\notin S.$$
\((1,2)\) ve \((2,1)\) hamlelerinde bir başka olasılık daha vardır: çıkarma yapıldıktan sonra iki koordinatın yer değiştirmesi gerekebilir. Bu durumda yeni affine kısıtlar ortaya çıkar.
Yer değiştirmeli \((1,2)\) hamlesi için
$$x-n=b,\qquad y-2n=a,$$
olmalıdır. Buradan
$$y-2x=a-2b$$
çıkar.
Yer değiştirmeli \((2,1)\) hamlesinde ise
$$x-2n=b,\qquad y-n=a,$$
ve dolayısıyla
$$2y-x=2a-b$$
elde edilir.
Fakat bu iki ek değer ancak yeni birinci koordinat eski ikinci koordinatı geçtiğinde anlam kazanır; yani yalnızca
$$x\gt b$$
iken aktiftir. Bu yüzden uygulama onları hemen eklemez; bunun yerine \(x=b+1\) anından itibaren etkin olacak şekilde olay olarak zamanlar. Açgözlü üretimin doğru çalışmasını sağlayan kritik ayrıntı budur.
Herhangi bir yasak küme \(F\) için
$$\operatorname{next}_F(t)=\min\{u\ge t:u\notin F\}$$
tanımını yapalım.
Sabit bir \(x\) için arama \(y=x+1\) ile başlar ve tüm kısıtlar sağlanana kadar \(y\) yukarı doğru itilir:
$$y\leftarrow \operatorname{next}_U(y),$$
$$y\leftarrow x+\operatorname{next}_D(y-x),$$
$$y\leftarrow 2x+\operatorname{next}_T(y-2x),$$
ve son olarak \(2y-x\), \(S\) içindeki yasak değerlerin ötesine taşınır.
Her güncelleme \(y\)'yi sadece artırdığı için süreç bir sabit noktada durur. Ulaşılan sabit nokta, o \(x\) için mümkün olan en küçük ortak \(y\) değeridir; yani bir sonraki kaybeden çifttir.
\(2y-x\) ifadesi her zaman \(x\) ile aynı parity'ye sahiptir. Uygulama bu yüzden \(S\) ailesini iki parity sınıfına ayırır; fakat matematiksel olarak bu hâlâ tek bir koşuldur: \(2y-x\notin S\).
Başlangıç noktası terminal durum \((0,0)\)'dır. Bu durum diagonal, \((1,2)\) ve \((2,1)\) ailelerinde affine değer olarak \(0\)'ı zaten yasaklar.
\(x=1\) için ilk aday \(y=2\)'dir. Bu aday başarısız olur çünkü
$$y-2x=2-2=0,$$
ve bu da \((0,0)\)'a bir \((1,2)\) hamlesi yapılabildiği anlamına gelir. Bir sonraki olasılık \(y=3\)'tür ve bu geçerlidir. Dolayısıyla ilk sıfır-dışı kaybeden çift
$$ (1,3) $$
olur.
\(x=2\) için \(y=3\) kullanılmış olduğu için elenir. Sonra \(y=4\),
$$y-x=2$$
olduğundan \((1,3)\) ile aynı diagonal invariantı taşır ve elenir. Ardından \(y=5\),
$$y-2x=1$$
olduğu için \((1,3)\)'ün \((1,2)\)-tipi invariantıyla çakışır. Böylece sıradaki geçerli çift
$$ (2,6) $$
olur.
\(x=3\) zaten kullanıldığı için atlanır. \(x=4\)'e gelmeden hemen önce, \((1,3)\)'ten gelen gecikmeli kısıtlar artık etkinleşir çünkü \(x\gt 3\) olmuştur. En küçük geçerli ortak \(y=5\) bulunur ve
$$ (4,5) $$
elde edilir.
Toplamı \(10\)'u aşmayan kaybeden çiftler tam olarak bunlardır. O halde
$$f(10)=4+8+9=21,$$
ki bu da uygulamadaki kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları aynı mantıksal durumu tutar:
kullanılmış koordinatlar için bir successor yapısı, diagonal farklar için bir yapı, \(y-2x\) yasakları için bir yapı ve \(2y-x\) yasaklarının parity'ye göre ayrılmış temsili. Bunlara ek olarak, belirli bir eşik geçildiğinde aktif olacak gecikmeli affine kısıtlar için minimum öncelikli bir kuyruk tutulur.
Her adımda önce eşiği gelmiş tüm olaylar aktive edilir. Sonra kullanılmamış en küçük \(x\) seçilir ve yukarıda anlatılan sabit nokta yükseltme süreci ile en küçük geçerli \(y\) bulunur.
\((x,y)\) kabul edildiğinde iki koordinat da kullanılmış olarak işaretlenir. Bu yeni kaybeden çiftin anında etkin olan invariantları
$$b-a,\qquad b-2a,\qquad 2b-a$$
hemen eklenir. Yer değiştirme durumlarından gelen
$$a-2b,\qquad 2a-b$$
invariantları ise ancak ilk koordinatın gelecekte \(b\)'yi aşacağı andan itibaren aktif olacak şekilde planlanır.
Eğer \(x+y\le M\) ise cevap toplamına \(x+y\) eklenir. Eğer toplam daha büyükse çift yine de yapısal olarak önemlidir; çünkü onun koordinatları ve affine invariantları, ilk koordinatı hâlâ \(M\)'yi geçmeyen daha sonraki çiftleri engelleyebilir.
Uygulamalar ayrıca çok küçük sınırlar için klasik kazanır/kaybeder DP ile karşılaştırma da içerir; böylece bu yapısal üretim yerel olarak doğrulanmış olur.
\(P(M)\), ilk koordinatı \(M\)'yi aşmadan önce üretilen kaybeden çift sayısı olsun. Her çift yalnızca sabit sayıda successor sorgusu, sabit sayıda ekleme, bir olay kuyruğuna ekleme ve daha sonra bir olay çıkarma işlemi üretir.
Successor yapıları path compression kullandığı için işlemler amortize olarak sabite çok yakındır. Öncelik kuyruğu logaritmik çarpanı getirir. Bu nedenle toplam süre
$$O\!\left(P(M)\log P(M)\right)$$
olur ve pratikte neredeyse lineer davranır. Bellek kullanımı ise
$$O\!\left(P(M)\right)$$
düzeyindedir. Hiçbir pozitif koordinat tekrar kullanılmadığından \(P(M)\) de arama aralığıyla lineer büyür; yöntemin gerekli üst sınıra ölçeklenebilmesinin sebebi budur.
Este es un juego imparcial con dos montones. Después de ordenar cada posición como \(a \le b\), un movimiento legal resta un múltiplo positivo de uno de los vectores
$$ (1,0),\ (0,1),\ (1,1),\ (1,2),\ (2,1), $$
siempre que ambos montones sigan siendo no negativos; después se vuelve a ordenar. Las posiciones \(P\) son las perdedoras. La función pedida es
$$f(M)=\sum_{\substack{(a,b)\in P\\0\lt a+b\le M}} (a+b).$$
Un programa dinámico completo sobre todos los estados con \(a+b\le 10^7\) sería demasiado lento, así que la implementación construye directamente las posiciones perdedoras.
La posición terminal \((0,0)\) es la primera posición \(P\). A partir de ahí, las posiciones \(P\) no triviales se generan en orden creciente de la primera coordenada.
Supongamos que dos posiciones perdedoras compartieran una coordenada positiva. Si \((c,d)\) y \((c,e)\) con \(d\lt e\) fueran ambas perdedoras, desde la mayor se podría llegar a la menor restando \(e-d\) de un solo montón. Eso no puede ocurrir entre dos posiciones \(P\).
Por tanto, cada entero positivo puede aparecer como coordenada a lo sumo una vez entre los pares perdedores no nulos. Eso sugiere la regla codiciosa clásica tipo Wythoff:
tomar como nueva primera coordenada \(x\) al menor entero positivo aún no usado, y después elegir el menor \(y\gt x\) que no sea atacado por ninguna posición perdedora anterior.
Las implementaciones siguen exactamente esa regla y la contrastan con fuerza bruta para cotas pequeñas.
Sea \((a,b)\) una posición perdedora anterior con \(a\lt b\), y \((x,y)\) un nuevo candidato con \(x\lt y\).
Los movimientos sobre un solo eje ya explican por qué ni \(x\) ni \(y\) pueden reutilizar una coordenada antigua. Los movimientos proporcionales añaden tres invariantes afines prohibidos.
Si \((x,y)\) pudiera llegar a \((a,b)\) mediante un movimiento diagonal \((n,n)\), entonces
$$x-a=n,\qquad y-b=n,$$
y por tanto
$$y-x=b-a.$$
Si \((x,y)\) pudiera llegar a \((a,b)\) mediante un movimiento de tipo \((1,2)\) sin cambiar el orden después de restar, entonces
$$x-a=n,\qquad y-b=2n,$$
lo que equivale a
$$y-2x=b-2a.$$
Para un movimiento de tipo \((2,1)\) sin intercambio, tenemos
$$x-a=2n,\qquad y-b=n,$$
y de ahí
$$2y-x=2b-a.$$
Así, cada par perdedor anterior prohíbe una familia de coordenadas y tres familias afines:
$$y\notin U,\qquad y-x\notin D,\qquad y-2x\notin T,\qquad 2y-x\notin S.$$
En los dos movimientos proporcionales aparece otra posibilidad: después de restar \((n,2n)\) o \((2n,n)\), puede hacer falta reordenar las coordenadas antes de comparar con \((a,b)\).
Para un movimiento de tipo \((1,2)\) con intercambio debe cumplirse
$$x-n=b,\qquad y-2n=a,$$
de donde sale otra condición prohibida:
$$y-2x=a-2b.$$
Para un movimiento de tipo \((2,1)\) con intercambio obtenemos
$$x-2n=b,\qquad y-n=a,$$
y por tanto
$$2y-x=2a-b.$$
Estas dos nuevas cantidades solo importan cuando la nueva primera coordenada ya ha sobrepasado la antigua segunda coordenada, es decir, cuando
$$x\gt b.$$
Por eso la implementación no las activa de inmediato. En su lugar las programa para activarse a partir de \(x=b+1\). Ese mecanismo de eventos es el detalle central que mantiene correcta la construcción codiciosa.
Para cualquier conjunto prohibido \(F\), definimos
$$\operatorname{next}_F(t)=\min\{u\ge t:u\notin F\}.$$
Con un \(x\) fijo, la búsqueda empieza en \(y=x+1\) y va empujando \(y\) hacia arriba hasta satisfacer todas las restricciones:
$$y\leftarrow \operatorname{next}_U(y),$$
$$y\leftarrow x+\operatorname{next}_D(y-x),$$
$$y\leftarrow 2x+\operatorname{next}_T(y-2x),$$
y finalmente \(2y-x\) se empuja más allá de los valores prohibidos de \(S\).
Cada actualización solo puede aumentar \(y\), así que el proceso termina en un punto fijo. Ese punto fijo es el menor compañero admisible para \(x\), y por tanto la siguiente posición perdedora.
La cantidad \(2y-x\) siempre tiene la misma paridad que \(x\). La implementación usa esa observación para guardar la familia \(S\) en dos clases de paridad, aunque matemáticamente sigue siendo una sola condición: \(2y-x\notin S\).
Se parte de la posición terminal \((0,0)\). Esa posición ya prohíbe el valor afín \(0\) en las familias diagonal, \((1,2)\) y \((2,1)\).
Para \(x=1\), el primer candidato es \(y=2\). Falla porque
$$y-2x=2-2=0,$$
lo que permitiría un movimiento \((1,2)\) hacia \((0,0)\). La siguiente opción es \(y=3\), que sí es válida. Así, el primer par perdedor no trivial es
$$ (1,3). $$
Para \(x=2\), \(y=3\) no sirve porque \(3\) ya está usado. Luego \(y=4\) falla ya que
$$y-x=2,$$
que coincide con la invariante diagonal de \((1,3)\). Después \(y=5\) falla porque
$$y-2x=1,$$
que coincide con la invariante de tipo \((1,2)\) de \((1,3)\). Por tanto, el siguiente par válido es
$$ (2,6). $$
La coordenada \(x=3\) se salta porque ya está usada. Antes de procesar \(x=4\), se activan las restricciones diferidas procedentes de \((1,3)\), ya que ahora \(x\gt 3\). El menor compañero válido resulta ser \(y=5\), y obtenemos
$$ (4,5). $$
Esos son exactamente los pares perdedores con suma a lo sumo \(10\), así que
$$f(10)=4+8+9=21,$$
en perfecto acuerdo con el valor de verificación de la implementación.
Las implementaciones en C++, Python y Java mantienen el mismo estado lógico:
una estructura sucesor para coordenadas usadas, otra para diferencias diagonales prohibidas, otra para los valores prohibidos de \(y-2x\), y una representación separada por paridad para los valores prohibidos de \(2y-x\). Además, mantienen una cola de prioridad mínima con restricciones afines diferidas que se activan al superar cierto umbral de \(x\).
En cada paso, la implementación activa todos los eventos cuyo umbral ya se alcanzó, toma el menor \(x\) aún no usado y ejecuta el proceso de elevación hasta punto fijo para obtener el menor \(y\) permitido.
Cuando \((x,y)\) queda aceptado, ambas coordenadas se marcan como usadas. Las invariantes inmediatas
$$b-a,\qquad b-2a,\qquad 2b-a$$
se insertan al instante, mientras que las invariantes del caso con intercambio
$$a-2b,\qquad 2a-b$$
se programan para activarse a partir del primer paso futuro con \(x\gt b\).
Si \(x+y\le M\), el par aporta \(x+y\) a la respuesta. Si la suma es mayor, el par sigue siendo estructuralmente relevante porque sus coordenadas e invariantes afines pueden bloquear pares posteriores cuya primera coordenada todavía no supera \(M\).
Las implementaciones también incluyen una comparación de control con el programa dinámico completo de ganar/perder en límites muy pequeños, que sirve como verificación local.
Sea \(P(M)\) el número de pares perdedores generados antes de que la primera coordenada supere \(M\). Cada par generado provoca solo un número constante de consultas sucesor, un número constante de inserciones, una inserción de evento y más tarde una extracción de evento.
Las estructuras sucesor usan compresión de caminos, así que sus operaciones son amortizadas casi constantes. La cola de prioridad aporta el factor logarítmico. En consecuencia, el tiempo total es
$$O\!\left(P(M)\log P(M)\right),$$
con comportamiento práctico casi lineal, y la memoria es
$$O\!\left(P(M)\right).$$
Como ninguna coordenada positiva se reutiliza, \(P(M)\) crece linealmente con el rango explorado, lo que explica por qué el método escala hasta el límite pedido.
这是一个两堆的无偏博弈。每个状态先排成 \(a \le b\) 的形式。合法操作是在保持两堆都非负的前提下，减去下面某个向量的正整数倍：
$$ (1,0),\ (0,1),\ (1,1),\ (1,2),\ (2,1). $$
减完以后再重新排序。\(P\)-位置表示必败态。题目要求的函数是
$$f(M)=\sum_{\substack{(a,b)\in P\\0\lt a+b\le M}} (a+b).$$
如果对所有满足 \(a+b\le 10^7\) 的状态直接做完整动态规划，状态数和转移数都会过大，因此实现不是“先判所有状态”，而是“直接构造所有必败态”。
终止状态 \((0,0)\) 是第一个 \(P\)-位置。其余非零 \(P\)-位置按第一坐标递增的顺序逐个构造出来。
先看一个基本事实：两个不同的必败态不可能共享某个正坐标。因为如果 \((c,d)\) 和 \((c,e)\) 且 \(d\lt e\) 都是必败态，那么较大的那个可以通过从单个堆里减去 \(e-d\) 直接走到较小的那个，这与 \(P\)-位置之间不能互相到达相矛盾。
因此，在所有非零必败对中，每个正整数至多作为一个坐标出现一次。于是就会自然得到类似 Wythoff 游戏中的贪心构造：
把当前还没有出现过的最小正整数作为新的第一坐标 \(x\)，然后寻找最小的 \(y\gt x\)，使得这个新对 \((x,y)\) 不会被任何先前的必败态攻击到。
三种语言实现都严格遵循这个思路，并且在很小的边界上用暴力赢输表做交叉验证。
设 \((a,b)\) 是一个已经构造出的必败态，满足 \(a\lt b\)。现在考虑新的候选对 \((x,y)\)，其中 \(x\lt y\)。
单轴移动已经说明 \(x\) 和 \(y\) 不能重复使用任何旧坐标。除此之外，比例移动还会带来三类仿射不变量约束。
如果 \((x,y)\) 可以通过对角移动 \((n,n)\) 到达 \((a,b)\)，那么
$$x-a=n,\qquad y-b=n,$$
于是得到
$$y-x=b-a.$$
如果 \((x,y)\) 可以通过 \((1,2)\) 型移动并且减完以后仍保持原来的坐标顺序到达 \((a,b)\)，则
$$x-a=n,\qquad y-b=2n,$$
等价于
$$y-2x=b-2a.$$
如果 \((x,y)\) 可以通过 \((2,1)\) 型移动且不需要交换顺序到达 \((a,b)\)，则
$$x-a=2n,\qquad y-b=n,$$
从而
$$2y-x=2b-a.$$
所以每个旧的必败态都会产生四类禁止条件：坐标不能重用，以及三个仿射族不能撞值：
$$y\notin U,\qquad y-x\notin D,\qquad y-2x\notin T,\qquad 2y-x\notin S.$$
比例移动还有另一种情况：减去 \((n,2n)\) 或 \((2n,n)\) 之后，两个坐标的大小关系可能翻转，此时必须先交换，再与旧的 \((a,b)\) 比较。这样会出现额外的仿射值。
对交换后的 \((1,2)\) 型移动，有
$$x-n=b,\qquad y-2n=a,$$
因此还要排除
$$y-2x=a-2b.$$
对交换后的 \((2,1)\) 型移动，则有
$$x-2n=b,\qquad y-n=a,$$
于是还要排除
$$2y-x=2a-b.$$
但这两条约束并不是一开始就有效。它们只有在新的第一坐标已经越过旧的第二坐标时才可能发生，也就是只有当
$$x\gt b$$
时才需要考虑。
这正是实现里“事件延迟激活”的原因：旧的必败态会把这两条交换型约束挂起，等到未来第一次满足 \(x=b+1\) 时再加入禁止集合。这个细节非常关键，因为如果过早加入，会错误地排除本来合法的候选；如果过晚加入，又会漏掉真实攻击关系。
对于任意禁止集合 \(F\)，定义 successor 算子
$$\operatorname{next}_F(t)=\min\{u\ge t:u\notin F\}.$$
固定某个第一坐标 \(x\) 之后，先从 \(y=x+1\) 开始，然后不断把 \(y\) 往上“抬”，直到所有约束同时满足：
$$y\leftarrow \operatorname{next}_U(y),$$
$$y\leftarrow x+\operatorname{next}_D(y-x),$$
$$y\leftarrow 2x+\operatorname{next}_T(y-2x),$$
最后再把 \(2y-x\) 推到不落入 \(S\) 的最小位置。
每一步都只会让 \(y\) 变大，不会变小，所以这个过程一定会停在一个固定点上。这个固定点就是满足所有限制的最小 \(y\)，也就是与当前 \(x\) 配对的下一个必败态。
实现里对 \(2y-x\) 这一族还做了按奇偶性的拆分。原因是 \(2y-x\) 与 \(x\) 总有相同的奇偶性，因此可以把这个仿射族压缩到两个独立的 successor 结构里；但在数学上，它仍然只是同一条约束 \(2y-x\notin S\)。
从终止状态 \((0,0)\) 开始。它已经让对角族、\((1,2)\) 族和 \((2,1)\) 族中的仿射值 \(0\) 变成禁值。
当 \(x=1\) 时，最先尝试的是 \(y=2\)。但这不合法，因为
$$y-2x=2-2=0,$$
这意味着可以通过一次 \((1,2)\) 型移动走到 \((0,0)\)。所以下一个候选 \(y=3\) 才是可行的，于是第一个非零必败态是
$$ (1,3). $$
当 \(x=2\) 时，\(y=3\) 不行，因为坐标 \(3\) 已经被用过。接着 \(y=4\) 也不行，因为
$$y-x=2,$$
与 \((1,3)\) 的对角差相同，说明可以通过 \((n,n)\) 走回去。然后 \(y=5\) 仍然不行，因为
$$y-2x=1,$$
与 \((1,3)\) 的 \((1,2)\) 仿射不变量相同。于是最小可行值变成 \(y=6\)，得到第二个必败态
$$ (2,6). $$
\(x=3\) 会被直接跳过，因为 \(3\) 已经作为坐标出现过。等到处理 \(x=4\) 之前，来自 \((1,3)\) 的延迟约束开始生效，因为现在已经满足 \(x\gt 3\)。此时最小可行配对是 \(y=5\)，所以得到
$$ (4,5). $$
这三个就是所有满足和不超过 \(10\) 的非零必败态，因此
$$f(10)=4+8+9=21,$$
与实现中的校验值完全一致。
C++、Python 和 Java 实现维护的是同一套逻辑状态：
一个 successor 结构记录已经用过的坐标，一个记录被禁止的对角差，一个记录被禁止的 \(y-2x\) 值，另有两个按奇偶拆分的结构表示被禁止的 \(2y-x\) 值。同时还维护一个最小优先队列，用来保存未来才会生效的延迟约束。
每一步先激活所有阈值已经达到的事件，然后取当前最小的未使用正整数作为 \(x\)，再通过上面的固定点抬升过程求出最小合法 \(y\)。
当 \((x,y)\) 被接受后，这两个坐标立即标记为已使用。与这个新必败态对应的即时不变量
$$b-a,\qquad b-2a,\qquad 2b-a$$
会立刻加入相应集合；而交换情形产生的不变量
$$a-2b,\qquad 2a-b$$
则会被挂到事件队列中，等未来第一次满足 \(x\gt b\) 时再激活。
如果 \(x+y\le M\)，这个必败态就把 \(x+y\) 加入答案；如果和已经大于 \(M\)，它仍然必须被保留，因为它的坐标和仿射禁值可能会阻止后面那些第一坐标仍不超过 \(M\) 的候选。
三份实现还都带有一个小规模的暴力赢输判定作为对照，用来验证这种构造式算法在小边界上的正确性。
记 \(P(M)\) 为“第一坐标尚未超过 \(M\)”之前生成的必败态数量。每生成一个必败态，只会产生常数次 successor 查询、常数次插入、一次事件入队以及稍后的一次事件出队。
successor 结构依靠路径压缩实现，摊还复杂度几乎可以看作常数；优先队列则带来对数因子。因此总时间复杂度可以写成
$$O\!\left(P(M)\log P(M)\right),$$
实际表现接近线性。空间复杂度为
$$O\!\left(P(M)\right).$$
由于任何正坐标都不会重复使用，\(P(M)\) 本身也只会随搜索范围线性增长，这就是该方法能够扩展到题目所需规模的原因。
Это беспристрастная игра с двумя кучами. Каждое состояние сначала упорядочивается так, чтобы \(a \le b\). Затем разрешается вычесть положительный кратный одного из векторов
$$ (1,0),\ (0,1),\ (1,1),\ (1,2),\ (2,1), $$
если обе кучи остаются неотрицательными; после хода пара снова сортируется. \(P\)-позиции являются проигрышными. Требуется вычислить
$$f(M)=\sum_{\substack{(a,b)\in P\\0\lt a+b\le M}} (a+b).$$
Полный динамический перебор всех состояний с \(a+b\le 10^7\) был бы слишком дорогим, поэтому реализация строит проигрышные позиции напрямую.
Терминальная позиция \((0,0)\) является первой \(P\)-позицией. Все ненулевые \(P\)-позиции затем порождаются в порядке возрастания первой координаты.
Предположим, что две проигрышные позиции имеют общую положительную координату. Если бы, например, \((c,d)\) и \((c,e)\) при \(d\lt e\) обе были проигрышными, то из большей можно было бы попасть в меньшую, уменьшив один единственный кучный размер на \(e-d\). Между двумя \(P\)-позициями такого быть не может.
Значит, каждое положительное число может встречаться среди координат ненулевых проигрышных пар не более одного раза. Отсюда возникает стандартное жадное правило в стиле игры Витхоффа:
в качестве новой первой координаты \(x\) берётся наименьшее ещё не использованное положительное число, а затем выбирается наименьшее \(y\gt x\), которое не атакуется ни одной ранее найденной проигрышной позицией.
Именно эту схему используют реализации, а на малых границах она дополнительно сверяется с грубой проверкой по таблице выигрыш/проигрыш.
Пусть \((a,b)\) — уже найденная проигрышная позиция, где \(a\lt b\), а \((x,y)\) — новый кандидат с \(x\lt y\).
Ходы вдоль одной оси уже объясняют, почему ни \(x\), ни \(y\) не могут совпадать с ранее использованными координатами. Пропорциональные ходы добавляют ещё три запрещённых аффинных инварианта.
Если \((x,y)\) можно перевести в \((a,b)\) диагональным ходом \((n,n)\), то
$$x-a=n,\qquad y-b=n,$$
а значит
$$y-x=b-a.$$
Если \((x,y)\) можно перевести в \((a,b)\) ходом типа \((1,2)\) без смены порядка координат после вычитания, то
$$x-a=n,\qquad y-b=2n,$$
что эквивалентно условию
$$y-2x=b-2a.$$
Для хода типа \((2,1)\) без перестановки получаем
$$x-a=2n,\qquad y-b=n,$$
и, следовательно,
$$2y-x=2b-a.$$
Тем самым каждая старая проигрышная позиция запрещает одну семейство координат и три аффинных семейства:
$$y\notin U,\qquad y-x\notin D,\qquad y-2x\notin T,\qquad 2y-x\notin S.$$
У двух пропорциональных ходов есть ещё один вариант: после вычитания \((n,2n)\) или \((2n,n)\) порядок координат может нарушиться, и перед сравнением с \((a,b)\) придётся поменять их местами. Это создаёт дополнительные аффинные ограничения.
Для переставленного хода типа \((1,2)\) должны выполняться равенства
$$x-n=b,\qquad y-2n=a,$$
то есть появляется ещё одно запрещённое значение
$$y-2x=a-2b.$$
Для переставленного хода типа \((2,1)\) получаем
$$x-2n=b,\qquad y-n=a,$$
и потому
$$2y-x=2a-b.$$
Однако эти две величины имеют значение только тогда, когда новая первая координата уже больше старой второй координаты, то есть при
$$x\gt b.$$
Именно поэтому реализация не заносит их сразу, а откладывает их активацию до момента \(x=b+1\). Этот механизм событий — ключевой элемент корректности жадкой схемы.
Для любого запрещённого множества \(F\) определим
$$\operatorname{next}_F(t)=\min\{u\ge t:u\notin F\}.$$
Для фиксированного \(x\) поиск начинается с \(y=x+1\), после чего значение \(y\) последовательно увеличивается, пока не будут одновременно выполнены все ограничения:
$$y\leftarrow \operatorname{next}_U(y),$$
$$y\leftarrow x+\operatorname{next}_D(y-x),$$
$$y\leftarrow 2x+\operatorname{next}_T(y-2x),$$
а затем величина \(2y-x\) переносится за пределы запрещённых значений из \(S\).
Каждое обновление только увеличивает \(y\), поэтому процесс приходит к неподвижной точке. Эта неподвижная точка и есть минимальный допустимый партнёр для данного \(x\), то есть следующая проигрышная позиция.
Величина \(2y-x\) всегда имеет ту же чётность, что и \(x\). Поэтому реализация хранит семейство \(S\) в двух классах по чётности, хотя математически это всё та же единая проверка \(2y-x\notin S\).
Начинаем с терминальной позиции \((0,0)\). Она уже запрещает значение \(0\) в диагональном семействе, а также в семействах \((1,2)\) и \((2,1)\).
Для \(x=1\) первый кандидат — \(y=2\). Он не подходит, потому что
$$y-2x=2-2=0,$$
а значит возможен ход типа \((1,2)\) в \((0,0)\). Следующее значение \(y=3\) допустимо, поэтому первая ненулевая проигрышная пара равна
$$ (1,3). $$
Для \(x=2\) значение \(y=3\) нельзя брать, потому что координата \(3\) уже использована. Затем \(y=4\) запрещено, так как
$$y-x=2,$$
и это совпадает с диагональным инвариантом пары \((1,3)\). После этого отпадает и \(y=5\), поскольку
$$y-2x=1,$$
что совпадает с инвариантом типа \((1,2)\) от \((1,3)\). Значит, следующий допустимый партнёр —
$$ (2,6). $$
Координата \(x=3\) пропускается, потому что она уже занята. Перед обработкой \(x=4\) активируются отложенные ограничения, порождённые парой \((1,3)\), поскольку теперь выполнено \(x\gt 3\). Минимальное допустимое значение равно \(y=5\), и мы получаем
$$ (4,5). $$
Это ровно все проигрышные пары с суммой не больше \(10\), поэтому
$$f(10)=4+8+9=21,$$
что совпадает с контрольным значением реализации.
Реализации на C++, Python и Java поддерживают одно и то же логическое состояние:
одну successor-структуру для уже использованных координат, одну для запрещённых диагональных разностей, одну для запрещённых значений \(y-2x\) и разбиение по чётности для запрещённых значений \(2y-x\). Кроме того, используется минимальная очередь с приоритетом для отложенных аффинных ограничений, которые должны включиться после достижения заданного порога по \(x\).
На каждом шаге реализация сначала активирует все события, порог которых уже достигнут, затем выбирает наименьшее неиспользованное \(x\) и с помощью описанного выше процесса доведения до неподвижной точки находит минимальное допустимое \(y\).
После принятия пары \((x,y)\) обе координаты помечаются как использованные. Непосредственные инварианты
$$b-a,\qquad b-2a,\qquad 2b-a$$
добавляются сразу, а инварианты переставленного случая
$$a-2b,\qquad 2a-b$$
помещаются в очередь событий и активируются только начиная с первого будущего шага, где выполняется \(x\gt b\).
Если \(x+y\le M\), в ответ прибавляется \(x+y\). Если сумма больше, пара всё равно остаётся важной с точки зрения структуры, поскольку её координаты и аффинные запреты могут заблокировать более поздние пары, у которых первая координата ещё не превосходит \(M\).
Во всех трёх реализациях есть также маленькая сверка с прямым выигрышно-проигрышным динамическим алгоритмом на очень малых границах — это локальная проверка корректности конструкции.
Пусть \(P(M)\) — число проигрышных пар, построенных до того момента, когда первая координата впервые превышает \(M\). Каждая новая пара порождает лишь константное число successor-запросов, константное число вставок, одно добавление события и впоследствии одно извлечение события.
Successor-структуры используют сжатие путей, поэтому их амортизированная стоимость практически постоянна. Очередь с приоритетом даёт логарифмический множитель. В итоге время работы равно
$$O\!\left(P(M)\log P(M)\right),$$
а на практике поведение близко к линейному. Память составляет
$$O\!\left(P(M)\right).$$
Так как никакая положительная координата не используется повторно, сама величина \(P(M)\) растёт только линейно с диапазоном поиска, что и делает метод масштабируемым до требуемой границы.
هذه لعبة حيادية بكومتين. بعد ترتيب كل حالة بحيث \(a \le b\)، يُسمح بطرح مضاعف موجب لأحد المتجهات
$$ (1,0),\ (0,1),\ (1,1),\ (1,2),\ (2,1), $$
ما دام حجم الكومتين يبقى غير سالب، ثم تُرتَّب الحالة من جديد. حالات \(P\) هي حالات الخسارة. والمطلوب حساب
$$f(M)=\sum_{\substack{(a,b)\in P\\0\lt a+b\le M}} (a+b).$$
البرمجة الديناميكية الكاملة على جميع الحالات التي تحقق \(a+b\le 10^7\) ستكون بطيئة جدًا، لذلك تبني الشيفرة حالات الخسارة مباشرة بدل فحص كل الحالات واحدةً واحدة.
الحالة النهائية \((0,0)\) هي أول حالة من نوع \(P\). وبعدها تُنشأ بقية حالات \(P\) غير الصفرية بترتيب تصاعدي حسب الإحداثي الأول.
لو اشتركت حالتا خسارة مختلفتان في إحداثي موجب واحد لظهر تناقض مباشر. فمثلًا إذا كانت \((c,d)\) و\((c,e)\) مع \(d\lt e\) كلتاهما حالتي خسارة، لأمكن الانتقال من الأكبر إلى الأصغر بطرح \(e-d\) من كومة واحدة فقط. وهذا غير ممكن بين حالتين من نوع \(P\).
إذًا كل عدد صحيح موجب يمكن أن يظهر كإحداثي مرة واحدة على الأكثر بين الأزواج الخاسرة غير الصفرية. ومن هنا تظهر القاعدة الجشعة الشبيهة بلعبة Wythoff:
نأخذ أصغر عدد موجب لم يُستخدم بعد على أنه الإحداثي الأول الجديد \(x\)، ثم نختار أصغر \(y\gt x\) لا تتعرض معه الحالة \((x,y)\) لهجوم من أي حالة خسارة سابقة.
النسخ البرمجية الثلاث تتبع هذه الفكرة حرفيًا، ثم تقارنها مع حل brute force على حدود صغيرة للتأكد من صحتها.
لتكن \((a,b)\) حالة خسارة سابقة حيث \(a\lt b\)، ولتكن \((x,y)\) حالة مرشحة جديدة بحيث \(x\lt y\).
الحركات المحورية تفسر أصلًا لماذا لا يجوز أن يعيد \(x\) أو \(y\) استخدام أي إحداثي قديم. أما الحركات التناسبية فتضيف ثلاث عائلات أخرى من القيود الخطية.
إذا كان بالإمكان الوصول من \((x,y)\) إلى \((a,b)\) بحركة قطرية من الشكل \((n,n)\)، فلدينا
$$x-a=n,\qquad y-b=n,$$
ومن ثم
$$y-x=b-a.$$
وإذا كان الانتقال ممكنًا بحركة من النمط \((1,2)\) من دون أن تنعكس رتبة الإحداثيين بعد الطرح، فإن
$$x-a=n,\qquad y-b=2n,$$
أي
$$y-2x=b-2a.$$
وبالمثل، إذا كان الانتقال ممكنًا بحركة من النمط \((2,1)\) من دون تبديل، فسنحصل على
$$x-a=2n,\qquad y-b=n,$$
ومنها
$$2y-x=2b-a.$$
وهكذا تمنع كل حالة خسارة سابقة عائلةً من الإحداثيات وثلاث عائلات خطية:
$$y\notin U,\qquad y-x\notin D,\qquad y-2x\notin T,\qquad 2y-x\notin S.$$
في الحركتين التناسبيتين توجد حالة أخرى: بعد طرح \((n,2n)\) أو \((2n,n)\) قد يلزم تبديل ترتيب الإحداثيين قبل مقارنتهما بالحالة \((a,b)\). عندها تظهر قيم خطية إضافية يجب منعها.
في حالة حركة \((1,2)\) مع التبديل يجب أن يتحقق
$$x-n=b,\qquad y-2n=a,$$
ومن ثم يظهر القيد
$$y-2x=a-2b.$$
وفي حالة حركة \((2,1)\) مع التبديل نحصل على
$$x-2n=b,\qquad y-n=a,$$
وبالتالي
$$2y-x=2a-b.$$
لكن هذين القيدين لا يصبحان مهمين إلا حين يتجاوز الإحداثي الأول الجديد الإحداثي الثاني القديم، أي فقط عندما
$$x\gt b.$$
لهذا لا تضيفهما الشيفرة مباشرة، بل تؤجلهما حتى تبدأ فعاليتهما من اللحظة \(x=b+1\). آلية الأحداث المؤجلة هذه هي التفصيل الحاسم الذي يحافظ على صحة البناء الجشع.
لكل مجموعة ممنوعة \(F\) نعرّف مؤثر successor كما يلي:
$$\operatorname{next}_F(t)=\min\{u\ge t:u\notin F\}.$$
عند تثبيت \(x\)، تبدأ عملية البحث من \(y=x+1\)، ثم يُدفَع \(y\) إلى الأعلى مرارًا حتى تتحقق كل الشروط معًا:
$$y\leftarrow \operatorname{next}_U(y),$$
$$y\leftarrow x+\operatorname{next}_D(y-x),$$
$$y\leftarrow 2x+\operatorname{next}_T(y-2x),$$
وفي النهاية تُدفَع القيمة \(2y-x\) لتتجاوز القيم الممنوعة في \(S\).
كل تحديث يزيد \(y\) فقط ولا ينقصه، لذلك تنتهي العملية عند نقطة ثابتة. وهذه النقطة الثابتة هي أصغر شريك ممكن للإحداثي \(x\)، أي زوج الخسارة التالي.
الكمية \(2y-x\) تملك دائمًا نفس فردية \(x\)، ولذلك تخزنها الشيفرة في فئتين بحسب الفردية. لكن المعنى الرياضي يبقى واحدًا: الشرط الحقيقي هو فقط \(2y-x\notin S\).
نبدأ من الحالة النهائية \((0,0)\). هذه الحالة تمنع مسبقًا القيمة الخطية \(0\) في العائلة القطرية وفي عائلتي \((1,2)\) و\((2,1)\).
عندما يكون \(x=1\)، فإن أول مرشح هو \(y=2\). لكنه غير صالح لأن
$$y-2x=2-2=0,$$
وهذا يعني وجود حركة من نوع \((1,2)\) إلى \((0,0)\). إذن أول قيمة صالحة هي \(y=3\)، ونحصل على أول زوج خسارة غير صفري:
$$ (1,3). $$
عندما يكون \(x=2\)، تُرفض القيمة \(y=3\) لأن \(3\) استُخدمت من قبل. ثم تُرفض \(y=4\) لأن
$$y-x=2,$$
وهو نفس الفرق القطري للزوج \((1,3)\). وبعد ذلك تُرفض \(y=5\) لأن
$$y-2x=1,$$
وهو نفس الثابت الخطي من نمط \((1,2)\) الناتج عن \((1,3)\). لذلك يكون أول \(y\) صالح هو
$$ (2,6). $$
أما \(x=3\) فيُتجاوز لأنه مستعمل أصلًا. وقبل معالجة \(x=4\)، تصبح القيود المؤجلة القادمة من \((1,3)\) فعالة لأننا وصلنا الآن إلى \(x\gt 3\). عندئذ يكون أصغر شريك صالح هو \(y=5\)، ومن ثم نحصل على
$$ (4,5). $$
وهذه هي بالضبط جميع أزواج الخسارة التي لا يتجاوز مجموعها \(10\)، ولذلك
$$f(10)=4+8+9=21,$$
وهو نفس مقدار التحقق المستخدم في التنفيذ.
تنفذ نسخ C++ وPython وJava المنطق نفسه تمامًا:
بنية successor لإحداثياتٍ استُخدمت من قبل، وبنية أخرى لفروق القطر الممنوعة، وبنية ثالثة لقيم \(y-2x\) الممنوعة، وتمثيل مقسوم بحسب الفردية لقيم \(2y-x\) الممنوعة. كذلك توجد طابور أولوية صغرى للأحداث المؤجلة التي ستصبح فعالة عند تجاوز عتبة معينة من \(x\).
في كل خطوة تُفعَّل أولًا جميع الأحداث التي حان وقتها، ثم يُختار أصغر \(x\) غير مستخدم، وبعد ذلك تُنفَّذ عملية الرفع حتى النقطة الثابتة لإيجاد أصغر \(y\) قانوني.
بعد قبول الزوج \((x,y)\)، تُعلَّم القيمتان على أنهما مستعملتان. وتُدرَج مباشرة الثوابت الفورية
$$b-a,\qquad b-2a,\qquad 2b-a$$
أما ثوابت حالتي التبديل
$$a-2b,\qquad 2a-b$$
فتُحجز على شكل أحداث لتُفعَّل ابتداءً من أول خطوة مستقبلية يتحقق فيها \(x\gt b\).
إذا كان \(x+y\le M\)، يُضاف المقدار \(x+y\) إلى الجواب. وإذا تجاوز المجموع \(M\)، يبقى الزوج مهمًا بنيويًا لأن إحداثياته وثوابته الخطية قد تمنع أزواجًا لاحقة ما زال إحداثيها الأول ضمن الحد المطلوب.
كما تتضمن التطبيقات مقارنةً صغيرة مع حل brute force القائم على جدول الفوز والخسارة في الحدود الصغيرة، وبذلك يُجرى فحص صحة محلي للبناء كله.
ليكن \(P(M)\) عدد أزواج الخسارة التي تُولَّد قبل أن يتجاوز الإحداثي الأول القيمة \(M\). كل زوج يولد عددًا ثابتًا من استعلامات successor، وعددًا ثابتًا من عمليات الإدراج، وإضافة حدث واحد إلى الطابور ثم إزالة هذا الحدث لاحقًا.
بنى successor تستفيد من ضغط المسار، لذا فتكلفتها الأمورتية قريبة جدًا من الثابت. أما طابور الأولوية فيضيف العامل اللوغاريتمي. لذلك تكون الكلفة الزمنية الكلية
$$O\!\left(P(M)\log P(M)\right),$$
مع سلوك عملي قريب من الخطي، بينما تكون الذاكرة
$$O\!\left(P(M)\right).$$
وبما أن أي إحداثي موجب لا يُعاد استخدامه أبدًا، فإن \(P(M)\) نفسه ينمو خطيًا فقط مع مجال البحث، ولهذا يمكن للطريقة أن تصل إلى الحد الكبير المطلوب.