There are \(N=1000000\) subscribers labeled \(0,1,\dots,999999\). The distinguished subscriber is the Prime Minister, whose number is \(524287\). Call attempts are generated by the deterministic sequence
$$S_k=(100003-200003k+300007k^3)\bmod 1000000 \qquad (1\le k\le 55),$$
$$S_k=(S_{k-24}+S_{k-55})\bmod 1000000 \qquad (k\ge 56).$$
The \(n\)-th call attempt uses the ordered pair \((S_{2n-1},S_{2n})\). If the two numbers are equal, the call is a misdial and does not count. Otherwise it is a successful call and creates an undirected connection between those two subscribers. The goal is to find the first successful-call count \(t\) for which the Prime Minister belongs to a connected component of size at least \(99\%\) of the network, namely \(990000\) subscribers.
The graph only grows: successful calls add edges, and nothing ever removes one. Because of that, the problem is really about tracking a partition of the subscriber set into connected components, not about storing the whole history of calls.
Although the story describes a pseudo-random telephone log, the data are completely determined by the recurrence for \(S_k\). Once the first 55 values are fixed, every later value follows from the lagged relation \(S_{k-24}+S_{k-55}\). So the problem is not probabilistic after the sequence definition is given: it is a fixed graph process on the vertex set
$$V=\{0,1,\dots,999999\}.$$
Every call attempt is simply one more edge candidate produced by this stream.
Let \((u_t,v_t)\) be the \(t\)-th successful call, so \(u_t\ne v_t\). After \(t\) successful calls define
$$G_t=(V,E_t),\qquad E_t=\bigl\{\{u_i,v_i\}:1\le i\le t\bigr\}.$$
If the same pair appears again, or if a new call connects two subscribers that were already linked through earlier calls, the graph \(G_t\) does not gain a new connected component structure; only the successful-call counter increases. This distinction matters because the answer is the number of successful calls, not the number of component merges.
Write \(C_t(524287)\) for the connected component containing the Prime Minister after \(t\) successful calls. Since edges are only added, connected components can merge but never split, so the size \(\lvert C_t(524287)\rvert\) is monotone nondecreasing.
Initially every subscriber is isolated, so the graph has \(1000000\) singleton components. Now process the successful calls one by one.
If a successful call joins two different components, those two components merge into one. If it joins two subscribers that are already in the same component, connectivity does not change at all. Therefore the entire state of the problem can be represented by the current partition of \(V\) into connected components together with the size of each part.
This is exactly why disjoint-set union works. The inductive invariant is simple: after every processed successful call, the disjoint-set classes are exactly the connected components of \(G_t\).
The proof is immediate from the two cases above. Because the invariant is exact, there is no need for adjacency lists, breadth-first search, or repeated graph traversals.
Consider a toy network with subscribers \(\{0,1,2,3,4,5\}\) and suppose the Prime Minister were \(0\). Process the successful calls
$$ (0,1),\ (2,3),\ (1,2),\ (0,3). $$
After the first three successful calls, the PM component is already \(\{0,1,2,3\}\), so its size is \(4\). The fourth call is still successful because \(0\ne 3\), so the successful-call counter increases by one, but the connected components do not change at all because \(0\) and \(3\) were already connected. This is the exact behavior the implementation must capture: count every non-misdial call, but merge components only when the two endpoints currently have different representatives.
For the actual Euler instance the target is
$$\left\lfloor 0.99\cdot 1000000\right\rfloor=990000.$$
So the required answer is
$$\min\bigl\{t\ge 0:\lvert C_t(524287)\rvert\ge 990000\bigr\}.$$
Because the component size is monotone, once this inequality becomes true it stays true, so a single left-to-right scan of the call stream is enough.
The C++, Python, and Java implementations all reproduce the same lagged Fibonacci stream and consume it two values at a time to form call attempts. The C++ implementation keeps only the last 55 values in a circular structure, which is sufficient for the recurrence. The Python and Java implementations instead grow a dynamic sequence as more values are requested. The C++ version also checks the published prefix \(200007,100053,600183,500439,600863,701497\) before starting the main computation.
All three implementations store, for each subscriber, a current representative and the size of the represented component. Path compression and union by size keep these operations fast. For each call attempt, a self-call is skipped immediately. Otherwise the successful-call counter is incremented, the two endpoints are merged if they belong to different components, and then the size of the component containing subscriber \(524287\) is tested against \(990000\). The first time the threshold is met, the current counter is the answer.
Let \(A\) be the number of call attempts examined before the threshold is first reached, and let \(T\le A\) be the number of successful calls among them. Producing the sequence costs \(O(A)\). The connectivity maintenance costs \(O(T\,\alpha(N))\), where \(\alpha\) is the inverse Ackermann function and \(N=1000000\). In practice \(\alpha(N)\) is tiny, so the overall running time is effectively linear in the number of processed calls.
The dominant memory usage is the disjoint-set structure, which stores one parent and one component size for each subscriber, hence \(O(N)\) space. The C++ implementation needs only \(O(1)\) extra storage for the sequence generator, while the Python and Java implementations keep a growing generated prefix in addition to the \(O(N)\) connectivity arrays.
Es gibt \(N=1000000\) Teilnehmer mit den Nummern \(0,1,\dots,999999\). Der ausgezeichnete Teilnehmer ist der Premierminister mit der Nummer \(524287\). Die Anrufversuche werden durch die deterministische Folge
$$S_k=(100003-200003k+300007k^3)\bmod 1000000 \qquad (1\le k\le 55),$$
$$S_k=(S_{k-24}+S_{k-55})\bmod 1000000 \qquad (k\ge 56)$$
erzeugt. Der \(n\)-te Anrufversuch benutzt das geordnete Paar \((S_{2n-1},S_{2n})\). Sind beide Nummern gleich, liegt eine Fehlwahl vor und der Versuch zählt nicht. Andernfalls ist es ein erfolgreicher Anruf und erzeugt eine ungerichtete Verbindung zwischen genau diesen beiden Teilnehmern. Gesucht ist der erste Zählerstand erfolgreicher Anrufe \(t\), für den der Premierminister zu einer Zusammenhangskomponente mit mindestens \(99\%\) des gesamten Netzes gehört, also zu mindestens \(990000\) Teilnehmern.
Der Graph wächst nur: Erfolgreiche Anrufe fügen Kanten hinzu, und keine Kante wird jemals entfernt. Deshalb muss man nicht die ganze Anrufhistorie speichern, sondern nur die aktuelle Zerlegung der Teilnehmermenge in Zusammenhangskomponenten verfolgen.
Obwohl der Text von einem pseudozufälligen Telefonprotokoll spricht, ist nach der Definition von \(S_k\) nichts mehr zufällig. Sobald die ersten 55 Werte feststehen, liefert die verzögerte Rekursion \(S_{k-24}+S_{k-55}\) jeden weiteren Wert eindeutig. Das Problem beschreibt also einen festen Prozess auf der Knotenmenge
$$V=\{0,1,\dots,999999\}.$$
Jeder Anrufversuch ist nur ein weiterer durch diese Folge erzeugter Kantenkandidat.
Sei \((u_t,v_t)\) der \(t\)-te erfolgreiche Anruf, also \(u_t\ne v_t\). Nach \(t\) erfolgreichen Anrufen definieren wir
$$G_t=(V,E_t),\qquad E_t=\bigl\{\{u_i,v_i\}:1\le i\le t\bigr\}.$$
Wenn dasselbe Paar später noch einmal auftaucht oder wenn ein neuer Anruf zwei Teilnehmer verbindet, die bereits über ältere Anrufe verbunden waren, ändert sich die Zusammenhangsstruktur von \(G_t\) nicht; nur der Zähler erfolgreicher Anrufe steigt weiter. Genau dieser Unterschied ist wichtig, denn gefragt ist die Anzahl erfolgreicher Anrufe und nicht die Anzahl echter Komponentenverschmelzungen.
Bezeichne mit \(C_t(524287)\) die Zusammenhangskomponente des Premierministers nach \(t\) erfolgreichen Anrufen. Da nur Kanten hinzugefügt werden, können Komponenten verschmelzen, aber nie wieder zerfallen. Also ist \(\lvert C_t(524287)\rvert\) monoton nicht fallend.
Anfangs ist jeder Teilnehmer isoliert, also besteht der Graph aus \(1000000\) Singletons. Verarbeitet man nun die erfolgreichen Anrufe nacheinander, gibt es immer nur zwei relevante Fälle.
Verbindet ein erfolgreicher Anruf zwei verschiedene Komponenten, dann verschmelzen genau diese beiden Komponenten. Verbindet er zwei Teilnehmer, die schon in derselben Komponente liegen, dann ändert sich an der Erreichbarkeit überhaupt nichts. Deshalb kann der gesamte Zustand des Problems durch die aktuelle Partition von \(V\) in Zusammenhangskomponenten und durch die Größen dieser Teile beschrieben werden.
Genau deshalb ist Union-Find die richtige Struktur. Die induktive Invariante lautet einfach: Nach jedem verarbeiteten erfolgreichen Anruf sind die Union-Find-Klassen genau die Zusammenhangskomponenten von \(G_t\).
Der Beweis folgt unmittelbar aus den beiden Fällen oben. Da die Invariante exakt ist, braucht man weder Adjazenzlisten noch Breitensuche noch wiederholte Graphdurchläufe.
Betrachte ein kleines Netz mit Teilnehmern \(\{0,1,2,3,4,5\}\) und setze den Premierminister probeweise auf \(0\). Verarbeite die erfolgreichen Anrufe
$$ (0,1),\ (2,3),\ (1,2),\ (0,3). $$
Nach den ersten drei erfolgreichen Anrufen ist die PM-Komponente bereits \(\{0,1,2,3\}\), also von Größe \(4\). Der vierte Anruf ist trotzdem erfolgreich, weil \(0\ne 3\) gilt; der Zähler erfolgreicher Anrufe steigt also um eins. Die Zusammenhangskomponenten ändern sich aber nicht mehr, weil \(0\) und \(3\) schon verbunden waren. Genau dieses Verhalten muss die Implementierung abbilden: Jeder Nicht-Fehlanruf wird gezählt, aber verschmolzen wird nur dann, wenn die beiden Endpunkte momentan verschiedene Repräsentanten besitzen.
Im eigentlichen Euler-Fall ist das Ziel
$$\left\lfloor 0.99\cdot 1000000\right\rfloor=990000.$$
Gesucht ist also
$$\min\bigl\{t\ge 0:\lvert C_t(524287)\rvert\ge 990000\bigr\}.$$
Weil die Komponentengröße monoton wächst, bleibt die Ungleichung nach dem ersten Eintreten dauerhaft wahr. Deshalb genügt ein einziger Links-nach-rechts-Durchlauf durch den Anrufstrom.
Die Implementierungen in C++, Python und Java erzeugen alle denselben Lagged-Fibonacci-Strom und lesen ihn paarweise als Anrufversuche aus. Die C++-Version speichert nur die letzten 55 Werte in einer zirkulären Struktur; das reicht für die Rekursion vollständig aus. Die Python- und Java-Versionen lassen stattdessen eine dynamische Folge mitwachsen, sobald weitere Werte benötigt werden. Die C++-Version prüft vor der Hauptrechnung zusätzlich den veröffentlichten Präfix \(200007,100053,600183,500439,600863,701497\).
Alle drei Implementierungen speichern für jeden Teilnehmer einen aktuellen Repräsentanten und die Größe der durch ihn repräsentierten Komponente. Pfadkompression und Vereinigung nach Größe halten diese Operationen schnell. Bei jedem Anrufversuch wird eine Fehlwahl sofort übersprungen. Andernfalls erhöht die Implementierung den Zähler erfolgreicher Anrufe, verschmilzt die beiden Endpunkte genau dann, wenn sie in verschiedenen Komponenten liegen, und testet anschließend die Größe der Komponente des Teilnehmers \(524287\) gegen \(990000\). Sobald der Schwellwert erreicht ist, ist der aktuelle Zähler die gesuchte Antwort.
Sei \(A\) die Anzahl betrachteter Anrufversuche bis zum ersten Erreichen des Schwellwerts und \(T\le A\) die Anzahl erfolgreicher Anrufe darunter. Das Erzeugen der Folge kostet \(O(A)\). Die Pflege der Zusammenhangskomponenten kostet \(O(T\,\alpha(N))\), wobei \(\alpha\) die inverse Ackermann-Funktion und \(N=1000000\) ist. Praktisch ist \(\alpha(N)\) winzig, daher ist die Laufzeit effektiv linear in der Zahl der verarbeiteten Anrufe.
Der Speicher wird von der Union-Find-Struktur dominiert: Für jeden Teilnehmer werden ein Elternzeiger und eine Komponentengröße gehalten, also \(O(N)\) Platz. Die C++-Version braucht darüber hinaus nur \(O(1)\) zusätzlichen Speicher für den Generator, während Python und Java zusätzlich einen wachsenden Präfix der erzeugten Folge behalten.
\(N=1000000\) abone vardır ve numaralar \(0,1,\dots,999999\) şeklindedir. Ayrıcalıklı abone Başbakan olup numarası \(524287\)'dir. Arama denemeleri şu deterministik diziyle üretilir:
$$S_k=(100003-200003k+300007k^3)\bmod 1000000 \qquad (1\le k\le 55),$$
$$S_k=(S_{k-24}+S_{k-55})\bmod 1000000 \qquad (k\ge 56).$$
\(n\). arama denemesi sıralı \((S_{2n-1},S_{2n})\) çiftidir. İki sayı eşitse bu bir yanlış aramadır ve sayılmaz. Eşit değilse bu başarılı bir aramadır ve ilgili iki abone arasında yönsüz bir bağlantı oluşturur. Amaç, Başbakanın bulunduğu bağlı bileşenin ağın en az \(99\%\)'una, yani \(990000\) aboneye ulaştığı ilk başarılı arama sayısını bulmaktır.
Graf sadece büyür: başarılı aramalar yeni kenarlar ekler, hiçbir şey mevcut bir kenarı silmez. Bu yüzden problem, tüm arama geçmişini saklama problemi değil; abonelerin o andaki bağlı bileşenlere ayrılışını izleme problemidir.
Hikaye sözde rastgele bir telefon kaydı anlatsa da, \(S_k\) tanımlandıktan sonra artık ortada olasılıksal bir belirsizlik yoktur. İlk 55 değer verildiğinde, gecikmeli bağıntı \(S_{k-24}+S_{k-55}\) sonraki tüm değerleri tekil olarak belirler. Dolayısıyla elimizdeki süreç,
$$V=\{0,1,\dots,999999\}$$
tepe kümesi üzerinde ilerleyen sabit bir kenar üretim sürecidir. Her arama denemesi, bu akıştan gelen yeni bir kenar adayından ibarettir.
\((u_t,v_t)\) ile \(t\). başarılı aramayı gösterelim; burada \(u_t\ne v_t\). O zaman \(t\) başarılı aramadan sonra
$$G_t=(V,E_t),\qquad E_t=\bigl\{\{u_i,v_i\}:1\le i\le t\bigr\}$$
tanımını yapabiliriz. Aynı çift daha sonra tekrar ortaya çıkarsa ya da yeni bir arama zaten daha önce dolaylı biçimde bağlı olan iki aboneyi birleştirirse, \(G_t\)'nin bağlılık yapısı değişmez; yalnızca başarılı arama sayacı artar. Bu ayrım kritik önemdedir, çünkü sorulan nicelik bileşen birleşmesi sayısı değil, başarılı arama sayısıdır.
Başbakanın \(t\) başarılı aramadan sonraki bağlı bileşenini \(C_t(524287)\) ile gösterelim. Kenarlar yalnızca eklendiği için bileşenler birleşebilir ama asla bölünmez; dolayısıyla \(\lvert C_t(524287)\rvert\) monoton azalmayandır.
Başlangıçta her abone tek başınadır; yani graf \(1000000\) tane tek elemanlı bileşenden oluşur. Başarılı aramaları birer birer işlerken her adımda yalnızca iki olasılık vardır.
Eğer başarılı arama iki farklı bileşeni bağlıyorsa, bu iki bileşen tek bir bileşen halinde birleşir. Eğer uçlar zaten aynı bileşendeyse erişilebilirlik hiç değişmez. Bu nedenle problemin tüm durumu, \(V\)'nin o andaki bağlı bileşenler biçimindeki partition'ı ve her parçanın büyüklüğü ile temsil edilebilir.
Union-Find yapısının tam olarak uygun olmasının nedeni budur. İndüktif invariant basittir: işlenen her başarılı aramadan sonra Union-Find sınıfları tam olarak \(G_t\)'nin bağlı bileşenleridir.
İspat yukarıdaki iki durumdan hemen çıkar. Bu invariant tam olduğu için komşuluk listelerine, genişlik öncelikli aramaya veya tekrar tekrar yapılan grafik taramalarına ihtiyaç yoktur.
Küçük bir örnek olarak abone kümesi \(\{0,1,2,3,4,5\}\) olsun ve Başbakanı geçici olarak \(0\) kabul edelim. Şu başarılı aramaları işleyelim:
$$ (0,1),\ (2,3),\ (1,2),\ (0,3). $$
İlk üç başarılı aramadan sonra PM bileşeni zaten \(\{0,1,2,3\}\) olur; yani boyutu \(4\)'tür. Dördüncü arama da başarılıdır, çünkü \(0\ne 3\); bu yüzden başarılı arama sayacı bir artar. Fakat bağlı bileşenler hiç değişmez, çünkü \(0\) ile \(3\) zaten bağlıdır. Kodun yakalaması gereken tam davranış budur: her yanlış olmayan aramayı say, ama birleşmeyi yalnızca iki uç noktanın temsilcileri farklıysa yap.
Gerçek Euler örneğinde hedef
$$\left\lfloor 0.99\cdot 1000000\right\rfloor=990000$$
olduğundan aranan değer
$$\min\bigl\{t\ge 0:\lvert C_t(524287)\rvert\ge 990000\bigr\}$$
ifadesidir. Bileşen boyutu monoton arttığı için bu eşitsizlik bir kez sağlandığında bir daha bozulmaz; dolayısıyla arama akışı üzerinde soldan sağa tek bir tarama yeterlidir.
C++, Python ve Java uygulamalarının üçü de aynı lagged Fibonacci akışını üretir ve onu ikişerli tüketerek arama denemelerine dönüştürür. C++ sürümü, bağıntı için yeterli olan son 55 değeri dairesel bir yapıda tutar. Python ve Java sürümleri ise ihtiyaç oldukça büyüyen bir dizi kullanır. C++ sürümü ana hesap başlamadan önce yayımlanan ön eki de doğrular: \(200007,100053,600183,500439,600863,701497\).
Üç uygulamanın hepsi her abone için bir temsilci ve temsil edilen bileşenin boyutunu tutar. Yol sıkıştırma ve boyuta göre birleştirme işlemleri bu yapıyı hızlı kılar. Her arama denemesinde öz-arama hemen atlanır. Aksi halde başarılı arama sayacı artırılır, iki uç nokta farklı bileşenlerdeyse birleştirilir ve sonra \(524287\) numaralı abonenin bileşen boyutu \(990000\) ile karşılaştırılır. Eşik ilk kez yakalandığında eldeki sayaç cevaptır.
\(A\), eşik ilk kez sağlanana kadar incelenen arama denemesi sayısı; \(T\le A\) ise bunların içindeki başarılı arama sayısı olsun. Diziyi üretmenin maliyeti \(O(A)\)'dır. Bağlılık yapısını güncellemenin maliyeti ise \(O(T\,\alpha(N))\)'dir; burada \(\alpha\) ters Ackermann fonksiyonu, \(N=1000000\)'dir. Pratikte \(\alpha(N)\) çok küçük olduğundan toplam çalışma süresi, işlenen arama sayısına göre neredeyse doğrusaldır.
Bellek tüketimine Union-Find yapısı hakimdir: her abone için bir ebeveyn bilgisi ve bir bileşen boyutu tutulduğu için \(O(N)\) alan gerekir. C++ sürümü üreteç için yalnızca \(O(1)\) ek alan kullanır; Python ve Java sürümleri ise buna ek olarak üretilmiş dizinin büyüyen bir ön ekini saklar.
Hay \(N=1000000\) abonados numerados \(0,1,\dots,999999\). El abonado distinguido es el Primer Ministro, cuyo número es \(524287\). Los intentos de llamada se generan mediante la sucesión determinista
$$S_k=(100003-200003k+300007k^3)\bmod 1000000 \qquad (1\le k\le 55),$$
$$S_k=(S_{k-24}+S_{k-55})\bmod 1000000 \qquad (k\ge 56).$$
El intento número \(n\) usa el par ordenado \((S_{2n-1},S_{2n})\). Si ambos valores coinciden, la llamada es un error de marcado y no cuenta. Si son distintos, la llamada es exitosa y añade una conexión no dirigida entre esos dos abonados. Se pide el primer número de llamadas exitosas \(t\) para el cual el Primer Ministro pertenece a una componente conexa de tamaño al menos \(99\%\) de la red, es decir, \(990000\) abonados.
El grafo solo crece: las llamadas exitosas añaden aristas y nada elimina una arista previa. Por eso el problema no consiste en guardar todo el historial de llamadas, sino en seguir la partición actual del conjunto de abonados en componentes conexas.
Aunque el enunciado habla de un registro pseudoaleatorio, una vez fijada la definición de \(S_k\) ya no queda ninguna incertidumbre probabilística. Después de los primeros 55 valores, la relación retardada \(S_{k-24}+S_{k-55}\) fija de forma única todos los demás. Así, el problema describe un proceso fijo sobre el conjunto de vértices
$$V=\{0,1,\dots,999999\}.$$
Cada intento de llamada no es más que un nuevo candidato a arista producido por esa corriente determinista.
Sea \((u_t,v_t)\) la \(t\)-ésima llamada exitosa, con \(u_t\ne v_t\). Tras \(t\) llamadas exitosas definimos
$$G_t=(V,E_t),\qquad E_t=\bigl\{\{u_i,v_i\}:1\le i\le t\bigr\}.$$
Si el mismo par vuelve a aparecer o si una nueva llamada une dos abonados que ya estaban conectados por llamadas anteriores, la estructura de conectividad de \(G_t\) no cambia; solo aumenta el contador de llamadas exitosas. Esa diferencia es esencial porque la respuesta es un número de llamadas exitosas, no un número de fusiones efectivas entre componentes.
Denotemos por \(C_t(524287)\) la componente conexa del Primer Ministro después de \(t\) llamadas exitosas. Como solo se añaden aristas, las componentes pueden fusionarse pero nunca separarse, de modo que \(\lvert C_t(524287)\rvert\) es monótona no decreciente.
Al principio cada abonado está aislado, así que el grafo tiene \(1000000\) componentes unitarias. Al procesar las llamadas exitosas una por una, solo pueden ocurrir dos situaciones relevantes.
Si una llamada exitosa une dos componentes distintas, esas dos componentes se funden en una sola. Si une dos abonados que ya estaban en la misma componente, la conectividad no cambia en absoluto. Por tanto, todo el estado del problema queda descrito por la partición actual de \(V\) en componentes conexas y por el tamaño de cada parte.
Esa es exactamente la razón por la que sirve una estructura de conjuntos disjuntos. La invariante inductiva es simple: después de cada llamada exitosa procesada, las clases de la estructura disjunta son exactamente las componentes conexas de \(G_t\).
La demostración sale directamente de los dos casos anteriores. Como la invariante es exacta, no hacen falta listas de adyacencia, recorridos en anchura ni búsquedas repetidas sobre el grafo.
Consideremos una red pequeña con abonados \(\{0,1,2,3,4,5\}\) y supongamos que el Primer Ministro fuera \(0\). Procesemos las llamadas exitosas
$$ (0,1),\ (2,3),\ (1,2),\ (0,3). $$
Después de las tres primeras llamadas exitosas, la componente del PM ya es \(\{0,1,2,3\}\), así que su tamaño es \(4\). La cuarta llamada sigue siendo exitosa porque \(0\ne 3\), por lo que el contador aumenta en uno, pero las componentes conexas no cambian porque \(0\) y \(3\) ya estaban conectados. Ese es exactamente el comportamiento que debe capturar la implementación: contar toda llamada que no sea un error de marcado, pero fusionar solo cuando los dos extremos tienen representantes distintos en ese momento.
En la instancia real el objetivo es
$$\left\lfloor 0.99\cdot 1000000\right\rfloor=990000.$$
Por tanto, lo que se busca es
$$\min\bigl\{t\ge 0:\lvert C_t(524287)\rvert\ge 990000\bigr\}.$$
Como el tamaño de la componente es monótono, una vez que la desigualdad se hace verdadera ya no deja de serlo. Por eso basta un único recorrido de izquierda a derecha por el flujo de llamadas.
Las implementaciones en C++, Python y Java generan exactamente el mismo flujo lagged Fibonacci y consumen dos valores por intento de llamada. La versión en C++ conserva solo los últimos 55 valores en una estructura circular, lo cual basta para la recurrencia. Las versiones en Python y Java, en cambio, amplían una secuencia dinámica a medida que se necesitan más valores. La implementación en C++ también verifica antes de empezar el prefijo publicado \(200007,100053,600183,500439,600863,701497\).
Las tres implementaciones almacenan, para cada abonado, un representante actual y el tamaño de la componente representada. La compresión de caminos y la unión por tamaño mantienen estas operaciones casi constantes. En cada intento de llamada, un autorregistro se descarta de inmediato. En caso contrario, se incrementa el contador de llamadas exitosas, se unen los extremos si pertenecen a componentes distintas y luego se comprueba si la componente que contiene al abonado \(524287\) ya alcanza \(990000\). La primera vez que eso ocurre, el contador actual es la respuesta.
Sea \(A\) el número de intentos de llamada examinados hasta alcanzar por primera vez el umbral, y sea \(T\le A\) el número de llamadas exitosas entre ellos. Generar la sucesión cuesta \(O(A)\). Mantener la conectividad cuesta \(O(T\,\alpha(N))\), donde \(\alpha\) es la función inversa de Ackermann y \(N=1000000\). En la práctica \(\alpha(N)\) es diminuta, así que el tiempo total es esencialmente lineal en el número de llamadas procesadas.
El consumo dominante de memoria es la estructura de conjuntos disjuntos, que guarda un padre y un tamaño de componente por abonado, es decir, \(O(N)\) espacio. La implementación en C++ usa solo \(O(1)\) espacio adicional para el generador, mientras que las versiones en Python y Java conservan además un prefijo creciente de la secuencia generada.
网络中有 \(N=1000000\) 个用户，编号为 \(0,1,\dots,999999\)。其中被特别关注的用户是首相，对应号码 \(524287\)。通话尝试由下面这个确定性的序列生成：
$$S_k=(100003-200003k+300007k^3)\bmod 1000000 \qquad (1\le k\le 55),$$
$$S_k=(S_{k-24}+S_{k-55})\bmod 1000000 \qquad (k\ge 56).$$
第 \(n\) 次通话尝试使用有序对 \((S_{2n-1},S_{2n})\)。如果两个号码相同，这是一通打给自己的误拨，不计入答案；如果不同，这就是一次成功通话，并在这两个用户之间加入一条无向连接。题目要求找到最小的成功通话次数 \(t\)，使得首相所在的连通分量规模至少达到整个网络的 \(99\%\)，也就是 \(990000\) 个用户。
这个图过程只有“加边”而没有“删边”。因此真正需要维护的不是完整的通话历史，而是当前所有用户被分成了哪些连通块，以及首相所在连通块的大小。
题面虽然用“伪随机”来描述电话记录，但在给出 \(S_k\) 的定义之后，整个过程就不再有任何随机性。前 55 项由显式公式给出，之后每一项都由滞后递推 \(S_{k-24}+S_{k-55}\) 唯一决定。于是这道题不是概率问题，而是在顶点集合
$$V=\{0,1,\dots,999999\}$$
上按固定顺序不断产生边候选的过程。每次通话尝试只是从这个固定序列里取出的下一个边候选。
记 \((u_t,v_t)\) 为第 \(t\) 次成功通话，其中 \(u_t\ne v_t\)。处理完前 \(t\) 次成功通话后，定义
$$G_t=(V,E_t),\qquad E_t=\bigl\{\{u_i,v_i\}:1\le i\le t\bigr\}.$$
如果同一对用户后来再次通话，或者一通新电话连接的两个人本来就能通过旧边互相到达，那么 \(G_t\) 的连通结构并不会改变，变化的只有“成功通话次数”这个计数器。这里必须把“成功通话”与“真正引发连通块合并的通话”区分开，因为题目要的前者，不是后者。
用 \(C_t(524287)\) 表示处理完前 \(t\) 次成功通话后，包含首相的连通分量。由于边只会增加不会删除，连通分量只能合并不能拆分，所以 \(\lvert C_t(524287)\rvert\) 是一个单调不减的量。
一开始每个用户都单独成一个点，所以图由 \(1000000\) 个单点连通分量组成。接下来按顺序处理成功通话，每一步只有两种真正重要的情况。
如果一通成功电话连接了两个不同的连通分量，那么这两个分量就合并成一个更大的分量。反之，如果这两个端点本来就在同一个连通分量里，那么整张图的连通性完全不变。因此，题目的全部状态都可以由“当前的连通分量划分”和“每个分量的大小”来表示。
这正是并查集适用的原因。其归纳不变量可以直接表述为：每处理完一次成功通话，并查集中的集合恰好等于 \(G_t\) 的连通分量。
这个结论直接来自上面的两种情况。因此根本不需要保存邻接表，也不需要反复做 BFS、DFS 或其他图遍历。
考虑一个玩具网络，用户集合为 \(\{0,1,2,3,4,5\}\)，并暂时把首相设为 \(0\)。依次处理下面这些成功通话：
$$ (0,1),\ (2,3),\ (1,2),\ (0,3). $$
在前三次成功通话之后，首相所在的连通分量已经是 \(\{0,1,2,3\}\)，大小为 \(4\)。第四次通话仍然算成功，因为 \(0\ne 3\)，所以成功通话计数器还要再加一；但连通分量并不会发生任何变化，因为 \(0\) 和 \(3\) 之前已经连通了。实现时必须准确反映这一点：所有非误拨通话都要计数，但只有当两个端点当前属于不同代表元时，才真的执行合并。
在本题的实际参数下，目标规模是
$$\left\lfloor 0.99\cdot 1000000\right\rfloor=990000.$$
因此我们要求的是
$$\min\bigl\{t\ge 0:\lvert C_t(524287)\rvert\ge 990000\bigr\}.$$
由于首相分量大小单调不减，一旦这个不等式第一次成立，以后就一直成立。所以只要按顺序扫描通话流，第一次达到门槛时就可以停止。
C++、Python 和 Java 三份实现都先生成同一个 lagged Fibonacci 序列，再每次取两个值组成一条通话尝试。C++ 版本只保留最近 55 个值的循环结构，这已经足够支持递推；Python 和 Java 版本则把已生成的前缀保存在会继续增长的动态序列中。C++ 版本在正式求解前还会检查公开给出的前缀 \(200007,100053,600183,500439,600863,701497\)。
三份实现都会为每个用户维护一个当前代表元，以及该代表元所对应分量的大小。路径压缩和按大小合并让这些操作非常快。对于每次通话尝试，如果是自呼叫就直接跳过；否则先把成功通话计数器加一，再在两个端点属于不同集合时执行合并，随后检查包含用户 \(524287\) 的那个集合大小是否已经达到 \(990000\)。第一次达到门槛时，当前计数器就是答案。
设 \(A\) 是首次达到门槛前检查过的通话尝试总数，\(T\le A\) 是其中成功通话的数量。生成序列的代价是 \(O(A)\)。维护并查集的代价是 \(O(T\,\alpha(N))\)，这里 \(\alpha\) 是反 Ackermann 函数，\(N=1000000\)。在实际规模下 \(\alpha(N)\) 极小，所以总时间基本可以看成与处理过的通话数线性相关。
内存的主要部分是并查集本身：每个用户需要一个父节点信息和一个分量大小，因此是 \(O(N)\) 空间。C++ 版本在生成器上只需要 \(O(1)\) 额外空间，而 Python 与 Java 版本还会额外保存一个不断增长的序列前缀。
Есть \(N=1000000\) абонентов с номерами \(0,1,\dots,999999\). Особый абонент — премьер-министр с номером \(524287\). Попытки звонков порождаются детерминированной последовательностью
$$S_k=(100003-200003k+300007k^3)\bmod 1000000 \qquad (1\le k\le 55),$$
$$S_k=(S_{k-24}+S_{k-55})\bmod 1000000 \qquad (k\ge 56).$$
\(n\)-я попытка звонка использует упорядоченную пару \((S_{2n-1},S_{2n})\). Если оба номера совпадают, это ошибочный самозвонок, и он не учитывается. Если номера различны, звонок считается успешным и добавляет неориентированное соединение между двумя абонентами. Нужно найти минимальное число успешных звонков \(t\), после которого премьер-министр окажется в компоненте связности размера не меньше \(99\%\) сети, то есть не меньше \(990000\) абонентов.
Граф только растет: успешные звонки добавляют ребра, и ни одно ребро никогда не удаляется. Поэтому задача сводится не к хранению всей истории звонков, а к отслеживанию текущего разбиения множества абонентов на компоненты связности.
Хотя в условии говорится о псевдослучайном журнале, после задания \(S_k\) никакой вероятностной неопределенности уже нет. Первые 55 членов задаются явной формулой, а все последующие однозначно определяются запаздывающей рекуррентной формулой \(S_{k-24}+S_{k-55}\). Значит, перед нами фиксированный процесс на множестве вершин
$$V=\{0,1,\dots,999999\}.$$
Каждая попытка звонка — это просто очередной кандидат на ребро, выданный этой последовательностью.
Обозначим через \((u_t,v_t)\) \(t\)-й успешный звонок, где \(u_t\ne v_t\). После \(t\) успешных звонков положим
$$G_t=(V,E_t),\qquad E_t=\bigl\{\{u_i,v_i\}:1\le i\le t\bigr\}.$$
Если та же пара появится снова или новый звонок соединит абонентов, которые уже были связаны через более ранние звонки, структура связности графа \(G_t\) не изменится; увеличится только счетчик успешных звонков. Это различие принципиально, потому что в ответе требуется число успешных звонков, а не число реальных слияний компонент.
Пусть \(C_t(524287)\) — компонента связности, содержащая премьер-министра после \(t\) успешных звонков. Поскольку ребра только добавляются, компоненты могут сливаться, но не могут распадаться, так что величина \(\lvert C_t(524287)\rvert\) монотонно не убывает.
Изначально каждый абонент изолирован, то есть граф состоит из \(1000000\) одноэлементных компонент. При последовательной обработке успешных звонков на каждом шаге существенны только два случая.
Если успешный звонок соединяет две разные компоненты, эти компоненты сливаются в одну. Если он соединяет двух абонентов, уже находящихся в одной компоненте, то связность не меняется вовсе. Значит, все состояние задачи можно описывать текущим разбиением \(V\) на компоненты связности и размерами этих частей.
Именно поэтому подходит структура непересекающихся множеств. Индуктивный инвариант формулируется так: после каждого обработанного успешного звонка классы структуры непересекающихся множеств точно совпадают с компонентами связности \(G_t\).
Доказательство непосредственно следует из двух случаев выше. Благодаря точности этого инварианта не нужны ни списки смежности, ни поиск в ширину, ни повторные обходы графа.
Рассмотрим маленькую сеть с абонентами \(\{0,1,2,3,4,5\}\) и временно положим, что премьер-министр имеет номер \(0\). Обработаем успешные звонки
$$ (0,1),\ (2,3),\ (1,2),\ (0,3). $$
После первых трех успешных звонков компонента премьер-министра уже равна \(\{0,1,2,3\}\), то есть имеет размер \(4\). Четвертый звонок все равно считается успешным, потому что \(0\ne 3\), значит счетчик успешных звонков увеличивается на единицу. Но сами компоненты связности не меняются, потому что \(0\) и \(3\) уже были связаны. Именно это и должна отражать реализация: считать каждый неошибочный звонок, но выполнять слияние только тогда, когда у концов звонка разные представители.
Для реального экземпляра Project Euler целевой размер равен
$$\left\lfloor 0.99\cdot 1000000\right\rfloor=990000.$$
Следовательно, требуется вычислить
$$\min\bigl\{t\ge 0:\lvert C_t(524287)\rvert\ge 990000\bigr\}.$$
Так как размер компоненты монотонен, после первого выполнения этого неравенства оно уже не нарушается. Значит, достаточно одного прохода слева направо по потоку звонков.
Реализации на C++, Python и Java генерируют один и тот же поток lagged Fibonacci и потребляют его по два значения на каждую попытку звонка. Версия на C++ хранит только последние 55 значений в циклической структуре, чего полностью достаточно для рекуррентной формулы. Версии на Python и Java, наоборот, наращивают динамический префикс уже сгенерированной последовательности. В реализации на C++ перед основным вычислением также проверяется опубликованный префикс \(200007,100053,600183,500439,600863,701497\).
Во всех трех реализациях для каждого абонента хранятся текущий представитель и размер соответствующей компоненты. Сжатие путей и объединение по размеру делают эти операции быстрыми. Для каждой попытки звонка самозвонок сразу пропускается. Иначе счетчик успешных звонков увеличивается, затем выполняется объединение двух концов звонка, если они находятся в разных компонентах, а после этого проверяется размер компоненты, содержащей абонента \(524287\). В первый момент, когда эта величина достигает \(990000\), текущий счетчик и есть ответ.
Пусть \(A\) — число просмотренных попыток звонка до первого достижения порога, а \(T\le A\) — число успешных звонков среди них. Генерация последовательности требует \(O(A)\). Поддержание структуры компонент требует \(O(T\,\alpha(N))\), где \(\alpha\) — обратная функция Аккермана, а \(N=1000000\). На практике \(\alpha(N)\) чрезвычайно мала, поэтому итоговое время практически линейно по числу обработанных звонков.
Память доминируется структурой компонент: по одному родителю и одному размеру компоненты на каждого абонента, то есть \(O(N)\) памяти. Реализация на C++ использует только \(O(1)\) дополнительной памяти для генератора, тогда как версии на Python и Java дополнительно хранят растущий префикс сгенерированной последовательности.
لدينا \(N=1000000\) مشترك مرقّمين من \(0\) إلى \(999999\). المشترك المميّز هو رئيس الوزراء ورقمه \(524287\). تُولَّد محاولات الاتصال بواسطة المتتالية الحتمية
$$S_k=(100003-200003k+300007k^3)\bmod 1000000 \qquad (1\le k\le 55),$$
$$S_k=(S_{k-24}+S_{k-55})\bmod 1000000 \qquad (k\ge 56).$$
المحاولة رقم \(n\) تستعمل الزوج المرتب \((S_{2n-1},S_{2n})\). إذا كان الرقمان متساويين فهذه مكالمة إلى النفس وتُهمل ولا تُحتسب. أمّا إذا كانا مختلفين فهي مكالمة ناجحة وتضيف وصلة غير موجهة بين هذين المشتركين. المطلوب هو إيجاد أصغر عدد من المكالمات الناجحة \(t\) بحيث يصبح رئيس الوزراء ضمن مكوّن متصل حجمه على الأقل \(99\%\) من الشبكة، أي \(990000\) مشتركًا.
الرسم البياني هنا لا يفعل إلا النمو: كل مكالمة ناجحة تضيف ضلعًا، ولا يوجد أي حذف لاحق. لذلك فالمسألة ليست مسألة الاحتفاظ بسجل الاتصالات كاملًا، بل مسألة تتبّع التقسيم الحالي للمشتركين إلى مكوّنات متصلة.
على الرغم من أن صياغة المسألة تتحدث عن سجل شبه عشوائي، فإن تعريف \(S_k\) يجعل العملية كلها حتمية تمامًا. بعد تثبيت القيم الخمس والخمسين الأولى، تحدد العلاقة المتأخرة \(S_{k-24}+S_{k-55}\) جميع القيم اللاحقة تحديدًا وحيدًا. إذن نحن أمام عملية ثابتة على مجموعة الرؤوس
$$V=\{0,1,\dots,999999\}.$$
وكل محاولة اتصال ليست إلا ضلعًا مرشحًا جديدًا يخرج من هذا التيار المحدد سلفًا.
لنرمز إلى المكالمة الناجحة رقم \(t\) بالزوج \((u_t,v_t)\) حيث \(u_t\ne v_t\). بعد \(t\) مكالمة ناجحة نعرّف
$$G_t=(V,E_t),\qquad E_t=\bigl\{\{u_i,v_i\}:1\le i\le t\bigr\}.$$
إذا تكرر الزوج نفسه لاحقًا، أو إذا وصلت مكالمة جديدة بين مشتركين كانا أصلًا متصلين عبر مكالمات سابقة، فإن بنية الاتصال في \(G_t\) لا تتغير؛ الذي يتغير فقط هو عدّاد المكالمات الناجحة. وهذه نقطة أساسية لأن المطلوب هو عدد المكالمات الناجحة لا عدد مرات اندماج المكوّنات فعليًا.
ولنكتب \(C_t(524287)\) للمكوّن المتصل الذي يحتوي على رئيس الوزراء بعد \(t\) مكالمة ناجحة. وبما أن الأضلاع تُضاف فقط ولا تُحذف، فإن المكوّنات قد تندمج ولكنها لا تنقسم، ومن ثم فإن \(\lvert C_t(524287)\rvert\) دالة رتيبة غير متناقصة.
في البداية يكون كل مشترك معزولًا، أي إن الرسم البياني يتكون من \(1000000\) مكوّن منفرد. وعند معالجة المكالمات الناجحة واحدة بعد أخرى لا توجد إلا حالتان مهمتان فعليًا.
إذا وصلت مكالمة ناجحة بين مكوّنين مختلفين فإن هذين المكوّنين يندمجان في مكوّن واحد أكبر. وإذا وصلت بين مشتركين موجودين سلفًا في المكوّن نفسه فإن الاتصال لا يتغير إطلاقًا. لذلك يمكن تمثيل حالة المسألة كلها بواسطة التقسيم الحالي لـ \(V\) إلى مكوّنات متصلة، مع حجم كل جزء.
ولهذا بالضبط تنجح بنية المجموعات المنفصلة. والثابت الاستقرائي يمكن صياغته ببساطة هكذا: بعد كل مكالمة ناجحة مُعالجة تكون أصناف بنية المجموعات المنفصلة مساوية تمامًا للمكوّنات المتصلة في \(G_t\).
وبرهان ذلك مباشر من الحالتين السابقتين. وبسبب دقة هذا الثابت لا حاجة إلى قوائم تجاور ولا إلى BFS أو DFS ولا إلى أي إعادة فحص شاملة للرسم البياني.
لنأخذ شبكة صغيرة من المشتركين \(\{0,1,2,3,4,5\}\)، ولنفترض مؤقتًا أن رئيس الوزراء هو \(0\). نعالج المكالمات الناجحة التالية:
$$ (0,1),\ (2,3),\ (1,2),\ (0,3). $$
بعد أول ثلاث مكالمات ناجحة يصبح مكوّن رئيس الوزراء هو \(\{0,1,2,3\}\) وحجمه \(4\). المكالمة الرابعة ما زالت ناجحة لأن \(0\ne 3\)، ولذلك يزداد عدّاد المكالمات الناجحة بواحد. لكن المكوّنات المتصلة نفسها لا تتغير لأن \(0\) و\(3\) كانا متصلين مسبقًا. هذا هو السلوك الذي يجب أن تلتقطه الخوارزمية بدقة: كل مكالمة ليست إلى النفس تُحسب، لكن الدمج الحقيقي لا يحدث إلا إذا كان للطرفين ممثلان مختلفان حاليًا.
في الحالة الأصلية للمسألة يكون الحجم الهدف هو
$$\left\lfloor 0.99\cdot 1000000\right\rfloor=990000.$$
إذًا المطلوب هو حساب
$$\min\bigl\{t\ge 0:\lvert C_t(524287)\rvert\ge 990000\bigr\}.$$
ولأن حجم مكوّن رئيس الوزراء غير متناقص، فبمجرد تحقق هذا الشرط لأول مرة سيبقى متحققًا بعدها. لذلك تكفي عملية مسح واحدة من اليسار إلى اليمين على تيار المكالمات.
تولّد تطبيقات C++ وPython وJava جميعها تيار lagged Fibonacci نفسه، ثم تستهلك قيمتين في كل مرة لتكوين محاولة اتصال. نسخة C++ تحتفظ فقط بآخر 55 قيمة ضمن بنية دائرية، وهذا يكفي تمامًا للعلاقة العودية. أما نسختا Python وJava فتحتفظان ببادئة متنامية من القيم المولدة. كما أن نسخة C++ تتحقق قبل البدء من البادئة المنشورة \(200007,100053,600183,500439,600863,701497\).
النسخ الثلاث كلها تحتفظ لكل مشترك بممثل حالي وبحجم المكوّن الذي يمثله. ضغط المسار والدمج حسب الحجم يجعلان هذه العمليات سريعة جدًا. عند كل محاولة اتصال، تُهمل مكالمة النفس مباشرة. وإلا يُزاد عدّاد المكالمات الناجحة، ثم يُدمج الطرفان إذا كانا في مجموعتين مختلفتين، ثم يُفحص حجم المجموعة التي تحتوي على المشترك \(524287\). وعند أول مرة يبلغ فيها الحجم \(990000\) يكون العداد الحالي هو الجواب.
ليكن \(A\) عدد محاولات الاتصال التي جرى فحصها حتى الوصول إلى العتبة لأول مرة، وليكن \(T\le A\) عدد المكالمات الناجحة بينها. توليد المتتالية يكلف \(O(A)\). أما صيانة بنية الاتصال فتكلف \(O(T\,\alpha(N))\)، حيث \(\alpha\) هي دالة آكرمان العكسية و\(N=1000000\). عمليًا تكون \(\alpha(N)\) صغيرة جدًا، لذا فالزمن الكلي شبه خطي في عدد المكالمات المعالجة.
أما الذاكرة فتسيطر عليها بنية المجموعات المنفصلة التي تخزن أبًا واحدًا وحجم مكوّن واحدًا لكل مشترك، أي \(O(N)\) مساحة. وتحتاج نسخة C++ فقط إلى \(O(1)\) مساحة إضافية للمولد، بينما تحتفظ نسختا Python وJava أيضًا ببادئة متنامية من المتتالية المولدة.