The pipe has radius \(R=50\), and we must place one sphere of each integer radius \(30,31,\dots,50\) inside it. If the minimum possible pipe length is \(L\), the required output is \(\operatorname{round}(1000L)\).
There are \(21\) spheres, so a direct search over all \(21!\) orders is hopeless. The implementations therefore split the task into two parts: geometry, which gives the exact cost of putting two radii next to each other, and combinatorics, which chooses the best overall order.
Once an order of radii is fixed, the best placement of the sphere centers is forced by the cylinder geometry. That turns the packing problem into a shortest-path problem on the set of radii.
Take two consecutive spheres with radii \(a\) and \(b\) inside a pipe of radius \(R\). In a shortest arrangement each sphere is pushed against the wall, because moving a center farther from the axis can only increase the transverse separation and therefore reduce the required axial gap.
If the two centers sit on opposite sides of the pipe, their transverse separation is
$$d_\perp=(R-a)+(R-b)=2R-a-b.$$
The spheres are tangent, so the distance between their centers is \(a+b\). By the Pythagorean theorem, the needed separation along the pipe axis is
$$d(a,b)=\sqrt{(a+b)^2-(2R-a-b)^2}=2\sqrt{R(a+b-R)}.$$
This is exactly the quantity evaluated by the C++, Python, and Java implementations. For Problem 222, \(R=50\), so the formula becomes
$$d(a,b)=10\sqrt{2(a+b-50)}.$$
The important structural fact is that the pair cost depends only on the sum \(a+b\), and it is symmetric, increasing, and concave as that sum grows.
Suppose the radii are arranged in the axial order
$$r_1,r_2,\dots,r_n.$$
If consecutive spheres alternate from one side of the pipe to the other, then the left end of the pipe is \(r_1\) units before the first center, the right end is \(r_n\) units after the last center, and each adjacent pair contributes one gap \(d(r_i,r_{i+1})\). Therefore
$$L(r_1,\dots,r_n)=r_1+\sum_{i=1}^{n-1} d(r_i,r_{i+1})+r_n.$$
Reversing the order leaves this expression unchanged, because the endpoint term becomes \(r_n+r_1\) and the same pair distances appear in the opposite direction.
The pair cost \(d(a,b)\) is an increasing concave function of \(a+b\). That favors mixing large and small radii rather than paying two large adjacency costs next to the same interior sphere. Exchange arguments for concave pair costs push the larger radii outward, producing a pendulum-like optimal order whose two ends are the two largest radii.
This is the structural reduction used by the implementations: one optimal arrangement has \(49\) at one end and \(50\) at the other. Because reversing the entire order gives the same total length, it is enough to fix \(49\) as the first sphere and \(50\) as the final sphere, and optimize only the \(19\) radii \(30,31,\dots,48\) in between.
Let \(S\subseteq\{30,31,\dots,48\}\) be the set of interior radii that have not yet been placed, and let \(x\) be the radius of the current last sphere in the partially built chain. Define \(F(S,x)\) to be the minimum additional length needed to finish the arrangement and then append the final radius \(50\).
The terminal case is immediate:
$$F(\varnothing,x)=d(x,50)+50.$$
If \(S\neq\varnothing\), the next sphere can be any \(r\in S\), so
$$F(S,x)=\min_{r\in S}\bigl(d(x,r)+F(S\setminus\{r\},r)\bigr).$$
The full answer before the final multiplication by \(1000\) is therefore
$$L_{\min}=49+F(\{30,31,\dots,48\},49).$$
The recurrence is exact because the future depends only on two facts: which radii remain unused, and the radius currently sitting at the open end of the chain.
The C++ implementation contains a tiny exhaustive check with pipe radius \(R=8\) and sphere radii \(5,6,7,8\). For that instance, the best order is
$$7,5,6,8$$
or its reversal \(8,6,5,7\). The three pair distances are
$$d(7,5)=\sqrt{12^2-4^2}=8\sqrt{2},\qquad d(5,6)=\sqrt{11^2-5^2}=4\sqrt{6},\qquad d(6,8)=\sqrt{14^2-2^2}=8\sqrt{3}.$$
Hence the total length is
$$L=7+8+8\sqrt{2}+4\sqrt{6}+8\sqrt{3}\approx 49.9680739307.$$
This small case already shows the same pattern as the full problem: the largest two radii sit at the ends, and the interior order alternates large and small values to keep the pair sums under control.
The C++, Python, and Java implementations all evaluate the same recurrence. A state is encoded by a bitmask for the unused interior radii and by the radius currently sitting at the open end of the partial arrangement. From that state, the implementation tries every remaining radius, adds the geometric gap \(d(x,r)\), and memoizes the best continuation.
The search starts with \(49\) already fixed on the left, while \(50\) is reserved as the forced final sphere. When the mask becomes empty, the implementation closes the chain by adding the last gap to \(50\) and then the terminal contribution \(50\) itself. After the optimal real-valued length is found, each program returns \(\operatorname{round}(1000L)\).
The storage strategy differs slightly by language. The C++ and Java implementations use dense floating-point tables indexed by \((\text{mask},\text{last})\), which is efficient because removing \(49\) and \(50\) leaves a contiguous mask range of size \(2^{19}\). The Python implementation uses a dictionary keyed by the same logical state. The C++ version also compares the optimized solver against brute force on the four-sphere checkpoint instance described above.
Let \(n=21\). Fixing the two endpoint spheres leaves \(n-2=19\) radii inside the subset mask. The number of memoized states is \(O(n2^{n-2})\), and each state examines up to \(O(n)\) next choices, so the running time is
$$O(n^2 2^{n-2}).$$
For Problem 222 this is easily manageable, whereas brute force would require evaluating \(21!\) different orders. The memory usage is
$$O(n2^{n-2}),$$
which in the array-based versions corresponds to about \(21\cdot 2^{19}\) floating-point entries plus small auxiliary overhead.
Das Rohr hat den Radius \(R=50\), und es soll jeweils genau eine Kugel mit ganzzahligem Radius \(30,31,\dots,50\) darin untergebracht werden. Ist \(L\) die minimale nötige Rohrlänge, so ist gesucht \(\operatorname{round}(1000L)\).
Es gibt \(21\) Kugeln, also ist eine brute-force Suche über alle \(21!\) Reihenfolgen völlig unrealistisch. Die Implementierungen zerlegen die Aufgabe deshalb in einen geometrischen Teil, der die Kosten eines benachbarten Kugelpaares liefert, und einen kombinatorischen Teil, der die beste Reihenfolge auswählt.
Sobald die Reihenfolge der Radien feststeht, ist auch die beste Lage der Kugelmittelpunkte durch die Zylindergeometrie bestimmt. Damit wird aus dem räumlichen Packungsproblem ein Kürzeste-Wege-Problem auf der Menge der Radien.
Betrachte zwei aufeinanderfolgende Kugeln mit Radien \(a\) und \(b\) in einem Rohr mit Radius \(R\). In einer kürzesten Anordnung liegt jede Kugel an der Rohrwand an, denn ein weiter vom Zylinderzentrum entfernter Mittelpunkt vergrößert nur den Querabstand und verkleinert damit den notwendigen axialen Abstand.
Liegen die beiden Mittelpunkte auf gegenüberliegenden Seiten des Rohres, dann ist ihr Querabstand
$$d_\perp=(R-a)+(R-b)=2R-a-b.$$
Da die Kugeln sich berühren, beträgt der Abstand ihrer Mittelpunkte \(a+b\). Mit dem Satz des Pythagoras ergibt sich für den nötigen Abstand entlang der Rohrachse
$$d(a,b)=\sqrt{(a+b)^2-(2R-a-b)^2}=2\sqrt{R(a+b-R)}.$$
Genau diese Größe wird in den C++-, Python- und Java-Implementierungen berechnet. Für Problem 222 mit \(R=50\) vereinfacht sich die Formel zu
$$d(a,b)=10\sqrt{2(a+b-50)}.$$
Entscheidend ist: Die Paar-Kosten hängen nur von der Summe \(a+b\) ab, und als Funktion dieser Summe sind sie symmetrisch, monoton wachsend und konkav.
Sei die axiale Reihenfolge der Kugeln
$$r_1,r_2,\dots,r_n.$$
Wenn aufeinanderfolgende Kugeln abwechselnd auf verschiedenen Seiten des Rohres liegen, dann ist das linke Rohrende um \(r_1\) vor dem ersten Mittelpunkt, das rechte Rohrende um \(r_n\) hinter dem letzten Mittelpunkt, und jedes Nachbarpaar steuert genau einen Abstand \(d(r_i,r_{i+1})\) bei. Also gilt
$$L(r_1,\dots,r_n)=r_1+\sum_{i=1}^{n-1} d(r_i,r_{i+1})+r_n.$$
Eine Umkehrung der Reihenfolge ändert diesen Wert nicht, denn der Endpunktterm bleibt \(r_1+r_n\) und dieselben Paarabstände tauchen nur in umgekehrter Richtung auf.
Die Paar-Kosten \(d(a,b)\) sind eine wachsende konkave Funktion von \(a+b\). Dadurch ist es günstiger, große und kleine Radien zu mischen, als einen großen Innenknoten mit zwei ebenfalls großen Nachbarn zu belasten. Austauschargumente für konkave Paar-Kosten schieben die großen Radien nach außen und führen zu einer pendelartigen optimalen Reihenfolge, deren Enden die beiden größten Radien sind.
Genau diese Struktur nutzt der Code aus: Es gibt eine optimale Anordnung mit \(49\) an einem Ende und \(50\) am anderen. Weil die umgekehrte Reihenfolge dieselbe Gesamtlänge besitzt, genügt es, \(49\) als Startkugel und \(50\) als letzte Kugel festzuhalten und nur die \(19\) Radien \(30,31,\dots,48\) dazwischen zu optimieren.
Sei \(S\subseteq\{30,31,\dots,48\}\) die Menge der inneren Radien, die noch nicht gesetzt wurden, und sei \(x\) der Radius der aktuell letzten Kugel in der bereits aufgebauten Kette. Definiere \(F(S,x)\) als die minimale zusätzliche Länge, die noch nötig ist, um die Anordnung zu vollenden und am Ende die Kugel mit Radius \(50\) anzufügen.
Der Endfall ist sofort klar:
$$F(\varnothing,x)=d(x,50)+50.$$
Für \(S\neq\varnothing\) kann als nächstes jede Kugel \(r\in S\) gewählt werden, also
$$F(S,x)=\min_{r\in S}\bigl(d(x,r)+F(S\setminus\{r\},r)\bigr).$$
Damit lautet die vollständige Lösung vor der Multiplikation mit \(1000\)
$$L_{\min}=49+F(\{30,31,\dots,48\},49).$$
Die Rekurrenz ist exakt, weil die Zukunft nur von zwei Informationen abhängt: welche Radien noch unbenutzt sind und welcher Radius aktuell am offenen Ende der Kette steht.
Die C++-Implementierung enthält einen kleinen Vollständigkeitstest mit Rohr-Radius \(R=8\) und Kugelradien \(5,6,7,8\). Für diese Instanz ist die beste Reihenfolge
$$7,5,6,8$$
oder die Umkehrung \(8,6,5,7\). Die drei Paarabstände sind
$$d(7,5)=\sqrt{12^2-4^2}=8\sqrt{2},\qquad d(5,6)=\sqrt{11^2-5^2}=4\sqrt{6},\qquad d(6,8)=\sqrt{14^2-2^2}=8\sqrt{3}.$$
Damit ergibt sich die Gesamtlänge
$$L=7+8+8\sqrt{2}+4\sqrt{6}+8\sqrt{3}\approx 49.9680739307.$$
Schon dieses kleine Beispiel zeigt dasselbe Muster wie das volle Problem: Die beiden größten Radien liegen an den Enden, und im Inneren wechseln sich große und kleine Werte so ab, dass die Paar-Summen moderat bleiben.
Die C++-, Python- und Java-Implementierungen werten alle dieselbe Rekurrenz aus. Ein Zustand besteht aus einer Bitmaske für die noch unbenutzten inneren Radien und aus dem Radius der Kugel, die aktuell am offenen Ende der Teilanordnung sitzt. Von dort ausprobiert die Implementierung jeden verbleibenden Radius, addiert den geometrischen Abstand \(d(x,r)\) und memoisiert die beste Fortsetzung.
Die Suche startet mit festem \(49\) auf der linken Seite, während \(50\) als erzwungene Schlusskugel reserviert bleibt. Sobald die Maske leer ist, wird die Kette geschlossen, indem noch der letzte Abstand zu \(50\) und anschließend der Endbeitrag \(50\) addiert werden. Aus der optimalen reellen Länge gibt jedes Programm schließlich \(\operatorname{round}(1000L)\) aus.
Die Speicherstrategie unterscheidet sich leicht je nach Sprache. C++ und Java verwenden dichte Gleitkomma-Tabellen mit Indizes \((\text{Maske},\text{letzter Radius})\), was effizient ist, weil nach dem Entfernen von \(49\) und \(50\) ein zusammenhängender Maskenbereich der Größe \(2^{19}\) übrig bleibt. Python verwendet ein Dictionary mit demselben logischen Zustand. Die C++-Version vergleicht den optimierten Solver außerdem auf der oben beschriebenen Vier-Kugel-Instanz mit einer vollständigen Permutationssuche.
Sei \(n=21\). Nach dem Festlegen der beiden Endkugeln bleiben \(n-2=19\) Radien in der Teilmengen-Maske. Die Zahl der memoisierten Zustände ist \(O(n2^{n-2})\), und pro Zustand werden bis zu \(O(n)\) nächste Möglichkeiten betrachtet. Die Laufzeit ist also
$$O(n^2 2^{n-2}).$$
Für Problem 222 ist das problemlos beherrschbar, während brute force \(21!\) verschiedene Reihenfolgen prüfen müsste. Der Speicherverbrauch ist
$$O(n2^{n-2}),$$
was in den arraybasierten Versionen ungefähr \(21\cdot 2^{19}\) Gleitkomma-Einträgen plus kleinem Zusatzspeicher entspricht.
Borunun yarıçapı \(R=50\) ve içine yarıçapları \(30,31,\dots,50\) olan kürelerin her birinden bir tane yerleştiriliyor. En kısa mümkün boru uzunluğu \(L\) ise istenen çıktı \(\operatorname{round}(1000L)\) değeridir.
Toplam \(21\) küre olduğu için bütün \(21!\) sıralamayı denemek pratik değildir. Bu yüzden uygulamalar problemi ikiye ayırır: geometri kısmı, iki yarıçap yan yana geldiğinde ne kadar eksenel mesafe gerektiğini verir; kombinatorik kısım ise en iyi sırayı seçer.
Yarıçapların sırası belirlendiği anda küre merkezlerinin en iyi yerleşimi de silindir geometrisi tarafından belirlenmiş olur. Böylece üç boyutlu paketleme sorusu, yarıçaplar kümesi üzerinde bir en kısa yol problemine dönüşür.
Yarıçapları \(a\) ve \(b\) olan iki ardışık küreyi, yarıçapı \(R\) olan bir boru içinde düşünelim. En kısa yerleşimde her küre duvara yaslanır; çünkü bir merkezi eksenden daha uzağa taşımak yalnızca enine ayrımı artırır ve bu da gerekli eksenel boşluğu azaltır.
Merkezler borunun karşı taraflarında durursa enine ayrım
$$d_\perp=(R-a)+(R-b)=2R-a-b$$
olur. Küreler birbirine teğet olduğu için merkezler arası uzaklık \(a+b\)'dir. Pisagor teoremi ile eksen boyunca gereken mesafe
$$d(a,b)=\sqrt{(a+b)^2-(2R-a-b)^2}=2\sqrt{R(a+b-R)}$$
çıkar. C++, Python ve Java uygulamalarının hesapladığı temel büyüklük tam olarak budur. Problem 222 için \(R=50\) olduğundan formül
$$d(a,b)=10\sqrt{2(a+b-50)}$$
şeklini alır. Buradaki kritik nokta, ikili maliyetin sadece \(a+b\) toplamına bağlı olması ve bu toplama göre simetrik, artan ve konkav olmasıdır.
Küre yarıçaplarının eksen üzerindeki sırası
$$r_1,r_2,\dots,r_n$$
olsun. Ardışık küreler borunun bir yanından öbür yanına dönüşümlü yerleşirse sol uç ilk merkezin \(r_1\) kadar önünde, sağ uç son merkezin \(r_n\) kadar arkasındadır ve her komşu çift bir adet \(d(r_i,r_{i+1})\) katkısı yapar. Dolayısıyla
$$L(r_1,\dots,r_n)=r_1+\sum_{i=1}^{n-1} d(r_i,r_{i+1})+r_n$$
olur. Sıralamayı ters çevirmek bu ifadeyi değiştirmez; çünkü uç katkısı yine \(r_1+r_n\) olur ve aynı ikili mesafeler bu kez ters sırada görünür.
\(d(a,b)\) maliyeti \(a+b\)'nin artan ve konkav bir fonksiyonudur. Bu yapı, büyük ve küçük yarıçapları karıştırmayı; aynı büyük küreye içeride iki büyük komşu yüklemekten daha avantajlı kılar. Konkav ikili maliyetler için kullanılan değiş-tokuş argümanları büyük yarıçapları dışa iter ve uçlarında en büyük iki yarıçap bulunan sarkaç benzeri bir optimal sıra üretir.
Uygulamalar tam olarak bu yapısal indirgemeyi kullanır: optimal bir dizilimde bir uçta \(49\), diğer uçta \(50\) vardır. Tüm sırayı ters çevirmek aynı toplam uzunluğu verdiği için \(49\)'u ilk, \(50\)'yi son küre olarak sabitlemek ve aradaki \(19\) yarıçapı, yani \(30,31,\dots,48\)'i optimize etmek yeterlidir.
\(S\subseteq\{30,31,\dots,48\}\) henüz yerleştirilmemiş iç yarıçaplar kümesi olsun ve \(x\), kısmen kurulmuş zincirin açık ucundaki son kürenin yarıçapı olsun. \(F(S,x)\), dizilimi tamamlayıp en sona yarıçapı \(50\) olan küreyi eklemek için gereken en küçük ek uzunluk olarak tanımlansın.
Son durum doğrudan yazılır:
$$F(\varnothing,x)=d(x,50)+50.$$
\(S\neq\varnothing\) ise sıradaki küre herhangi bir \(r\in S\) olabilir; dolayısıyla
$$F(S,x)=\min_{r\in S}\bigl(d(x,r)+F(S\setminus\{r\},r)\bigr).$$
Buna göre, \(1000\) ile çarpılmadan önceki gerçek minimum uzunluk
$$L_{\min}=49+F(\{30,31,\dots,48\},49)$$
olur. Bu bağıntı tamdır; çünkü geleceği belirleyen tek bilgiler hangi yarıçapların kaldığı ve zincirin açık ucunda hangi yarıçapın bulunduğudur.
C++ uygulamasında, yarıçapı \(R=8\) olan bir boru ve \(5,6,7,8\) yarıçaplı küreler için küçük bir tam arama kontrolü bulunur. Bu örnekte en iyi sıra
$$7,5,6,8$$
veya bunun tersi \(8,6,5,7\)'dir. Üç komşu mesafesi
$$d(7,5)=\sqrt{12^2-4^2}=8\sqrt{2},\qquad d(5,6)=\sqrt{11^2-5^2}=4\sqrt{6},\qquad d(6,8)=\sqrt{14^2-2^2}=8\sqrt{3}$$
olduğundan toplam uzunluk
$$L=7+8+8\sqrt{2}+4\sqrt{6}+8\sqrt{3}\approx 49.9680739307$$
çıkar. Küçük örnek bile tam problemdeki yapıyı gösterir: en büyük iki yarıçap uçlara gider, iç kısımda ise büyük ve küçük değerler dönüşümlü seçilerek ikili toplamlar dengelenir.
C++, Python ve Java uygulamaları aynı bağıntıyı değerlendirir. Bir durum, henüz kullanılmamış iç yarıçapları gösteren bir bitmask ve kısmi dizilimin açık ucunda duran son yarıçap ile temsil edilir. O durumdan itibaren uygulama kalan her yarıçapı bir kez dener, geometrik boşluk \(d(x,r)\) katkısını ekler ve en iyi devamı memoize eder.
Arama, solda \(49\) sabitlenmiş halde başlar; \(50\) ise zorunlu son küre olarak saklanır. Maske boşaldığında zincir, son küreden \(50\)'ye olan mesafe ve ardından uç katkısı \(50\) eklenerek kapatılır. En iyi reel uzunluk bulunduktan sonra her program \(\operatorname{round}(1000L)\) döndürür.
Dil bazında depolama ayrıntısı biraz değişir. C++ ve Java sürümleri \((\text{mask},\text{son})\) ile indekslenen yoğun kayan nokta tabloları kullanır; çünkü \(49\) ve \(50\) çıkarıldıktan sonra etkin maskeler \(2^{19}\) büyüklüğünde bitişik bir aralık oluşturur. Python sürümü aynı mantıksal durumu anahtar yapan bir sözlük kullanır. C++ sürümü ayrıca yukarıdaki dört küreli örnekte optimize edilmiş çözücü ile tam permütasyon aramasını karşılaştırır.
\(n=21\) olsun. İki uç küre sabitlenince altküme maskesinde \(n-2=19\) yarıçap kalır. Memoize edilen durum sayısı \(O(n2^{n-2})\), her durumdaki aday geçiş sayısı ise en fazla \(O(n)\) olduğundan toplam çalışma süresi
$$O(n^2 2^{n-2})$$
olur. Bu, \(21!\) farklı sıralamayı denemek zorunda kalan brute-force yaklaşıma göre çok küçüktür. Bellek kullanımı
$$O(n2^{n-2})$$
seviyesindedir; dizi kullanan sürümlerde bu yaklaşık \(21\cdot 2^{19}\) kayan nokta girdisi ve küçük ek veri yapıları anlamına gelir.
El tubo tiene radio \(R=50\) y dentro de él debe colocarse una esfera de cada radio entero \(30,31,\dots,50\). Si \(L\) es la longitud mínima posible del tubo, la salida pedida es \(\operatorname{round}(1000L)\).
Hay \(21\) esferas, de modo que una búsqueda directa sobre las \(21!\) permutaciones es inviable. Las implementaciones separan entonces el problema en dos partes: la geometría, que determina el coste exacto de poner dos radios como vecinos, y la parte combinatoria, que elige el mejor orden global.
Una vez fijado el orden de los radios, la mejor colocación de los centros queda determinada por la geometría del cilindro. Con eso, la cuestión espacial se convierte en un problema de camino mínimo sobre el conjunto de radios.
Tomemos dos esferas consecutivas de radios \(a\) y \(b\) dentro de un tubo de radio \(R\). En una disposición mínima, cada esfera se empuja contra la pared, porque alejar un centro del eje solo puede aumentar la separación transversal y reducir la separación axial necesaria.
Si los dos centros quedan en lados opuestos del tubo, su separación transversal es
$$d_\perp=(R-a)+(R-b)=2R-a-b.$$
Las esferas son tangentes, así que la distancia entre centros es \(a+b\). Por el teorema de Pitágoras, la separación necesaria a lo largo del eje del tubo es
$$d(a,b)=\sqrt{(a+b)^2-(2R-a-b)^2}=2\sqrt{R(a+b-R)}.$$
Esa es exactamente la cantidad que evalúan las implementaciones en C++, Python y Java. En el Problema 222, con \(R=50\), la fórmula se reduce a
$$d(a,b)=10\sqrt{2(a+b-50)}.$$
El punto estructural clave es que este coste depende solo de la suma \(a+b\), y como función de esa suma es simétrico, creciente y cóncavo.
Supongamos que los radios aparecen en el orden axial
$$r_1,r_2,\dots,r_n.$$
Si las esferas consecutivas alternan de un lado del tubo al otro, entonces el extremo izquierdo del tubo queda \(r_1\) unidades antes del primer centro, el extremo derecho queda \(r_n\) unidades después del último, y cada par adyacente aporta una distancia \(d(r_i,r_{i+1})\). Por tanto,
$$L(r_1,\dots,r_n)=r_1+\sum_{i=1}^{n-1} d(r_i,r_{i+1})+r_n.$$
Invertir el orden no cambia esta expresión, porque el término de los extremos sigue siendo \(r_1+r_n\) y aparecen las mismas distancias de pares en sentido contrario.
El coste \(d(a,b)\) es una función creciente y cóncava de \(a+b\). Eso favorece mezclar radios grandes con pequeños, en vez de hacer que una esfera grande interior pague dos costes grandes con sus vecinos. Los argumentos de intercambio para costes cóncavos empujan los radios mayores hacia afuera y producen un orden óptimo tipo péndulo, cuyos dos extremos son precisamente los dos radios más grandes.
Ese es el recorte estructural utilizado por las implementaciones: existe una disposición óptima con \(49\) en un extremo y \(50\) en el otro. Como invertir todo el orden produce la misma longitud total, basta fijar \(49\) como primera esfera y \(50\) como esfera final, y optimizar solo los \(19\) radios intermedios \(30,31,\dots,48\).
Sea \(S\subseteq\{30,31,\dots,48\}\) el conjunto de radios interiores que todavía no se han colocado, y sea \(x\) el radio de la esfera que está actualmente al final abierto de la cadena parcial. Definimos \(F(S,x)\) como la longitud adicional mínima necesaria para completar la disposición y luego añadir la esfera final de radio \(50\).
El caso terminal es inmediato:
$$F(\varnothing,x)=d(x,50)+50.$$
Si \(S\neq\varnothing\), la siguiente esfera puede ser cualquier \(r\in S\), así que
$$F(S,x)=\min_{r\in S}\bigl(d(x,r)+F(S\setminus\{r\},r)\bigr).$$
La respuesta completa antes de multiplicar por \(1000\) es entonces
$$L_{\min}=49+F(\{30,31,\dots,48\},49).$$
La recurrencia es exacta porque el futuro depende solo de dos objetos: qué radios siguen sin usarse y cuál es el radio de la esfera situada en el extremo abierto actual.
La implementación en C++ incluye una comprobación exhaustiva pequeña con radio de tubo \(R=8\) y radios \(5,6,7,8\). En ese caso, el mejor orden es
$$7,5,6,8$$
o su reverso \(8,6,5,7\). Las tres distancias entre vecinos son
$$d(7,5)=\sqrt{12^2-4^2}=8\sqrt{2},\qquad d(5,6)=\sqrt{11^2-5^2}=4\sqrt{6},\qquad d(6,8)=\sqrt{14^2-2^2}=8\sqrt{3}.$$
Por tanto, la longitud total es
$$L=7+8+8\sqrt{2}+4\sqrt{6}+8\sqrt{3}\approx 49.9680739307.$$
Incluso esta instancia pequeña muestra el mismo comportamiento que el problema completo: los dos radios mayores terminan en los extremos y el interior alterna valores grandes y pequeños para mantener controladas las sumas de cada par.
Las implementaciones en C++, Python y Java evalúan exactamente la misma recurrencia. Un estado se representa con una máscara de bits para los radios interiores aún no usados y con el radio de la esfera que se encuentra en el extremo abierto de la disposición parcial. Desde ahí, la implementación prueba cada radio restante, suma el hueco geométrico \(d(x,r)\) y memoriza la mejor continuación.
La búsqueda comienza con \(49\) ya fijado a la izquierda, mientras que \(50\) se reserva como esfera final obligatoria. Cuando la máscara queda vacía, la cadena se cierra añadiendo la última distancia hasta \(50\) y después la contribución terminal \(50\). Una vez obtenida la longitud real óptima, cada programa devuelve \(\operatorname{round}(1000L)\).
La estrategia de almacenamiento cambia un poco según el lenguaje. Las versiones de C++ y Java usan tablas densas de coma flotante indexadas por \((\text{máscara},\text{último})\), lo cual es eficiente porque al retirar \(49\) y \(50\) queda un rango contiguo de máscaras de tamaño \(2^{19}\). La versión en Python usa un diccionario con el mismo estado lógico. Además, la versión de C++ compara el solucionador optimizado con una búsqueda exhaustiva en la instancia pequeña de cuatro esferas descrita antes.
Sea \(n=21\). Al fijar las dos esferas de los extremos quedan \(n-2=19\) radios dentro de la máscara de subconjuntos. El número de estados memorizados es \(O(n2^{n-2})\), y cada estado analiza hasta \(O(n)\) elecciones siguientes, de modo que el tiempo total es
$$O(n^2 2^{n-2}).$$
Para el Problema 222 esto es totalmente manejable, mientras que la fuerza bruta tendría que evaluar \(21!\) órdenes distintos. El consumo de memoria es
$$O(n2^{n-2}),$$
que en las versiones basadas en arreglos equivale aproximadamente a \(21\cdot 2^{19}\) entradas de punto flotante más un pequeño almacenamiento auxiliar.
圆柱管的半径是 \(R=50\)，需要把半径分别为 \(30,31,\dots,50\) 的球各放入一个。如果最短可行管长为 \(L\)，题目要求输出 \(\operatorname{round}(1000L)\)。
一共有 \(21\) 个球，直接枚举全部 \(21!\) 种排列根本不可行。实现代码因此把问题拆成两部分：几何部分负责计算两个半径相邻时必须留下的轴向距离，组合部分负责在所有可能顺序里找到总代价最小的那一个。
一旦球的半径顺序固定，球心的最优摆放方式就已经被圆柱几何完全决定了。这样一来，原本的三维堆放问题就变成了“半径序列上的最短路径”问题。
考虑圆柱半径为 \(R\) 时，两个相邻球的半径分别为 \(a\) 和 \(b\)。在最短摆放中，每个球都会尽量贴住管壁；因为如果某个球心离轴更远，它与邻球之间允许的横向分离只会更大，从而所需的轴向间距只会更小。
当两个球心分别贴在管道截面的相对两侧时，它们的横向距离为
$$d_\perp=(R-a)+(R-b)=2R-a-b.$$
两球相切，所以球心距离是 \(a+b\)。由勾股定理，沿管轴方向所需的最小距离为
$$d(a,b)=\sqrt{(a+b)^2-(2R-a-b)^2}=2\sqrt{R(a+b-R)}.$$
这正是 C++、Python 和 Java 实现中反复计算的核心量。对本题 \(R=50\) 而言，公式进一步化成
$$d(a,b)=10\sqrt{2(a+b-50)}.$$
这里最重要的结构事实是：相邻代价只依赖于 \(a+b\) 这一和，而且它作为该和的函数是对称、单调递增且凹的。
设球的轴向顺序为
$$r_1,r_2,\dots,r_n.$$
如果相邻球在管道左右两侧交替出现，那么管子的左端距离第一个球心是 \(r_1\)，右端距离最后一个球心是 \(r_n\)，每一对相邻球贡献一个轴向间距 \(d(r_i,r_{i+1})\)。因此总长度满足
$$L(r_1,\dots,r_n)=r_1+\sum_{i=1}^{n-1} d(r_i,r_{i+1})+r_n.$$
把整个顺序反过来不会改变这个值，因为端点项仍然是 \(r_1+r_n\)，相邻配对也完全相同，只是方向相反而已。
由于 \(d(a,b)\) 是 \(a+b\) 的递增凹函数，把一个大半径球放在内部通常要支付两次较大的相邻代价，而把它放在端点只需要承担一次相邻代价加一个端点半径项。对这种凹型配对代价做局部交换时，较大的半径会被逐步推向两侧，形成类似“钟摆排列”的最优结构，而最外侧恰好是最大的两个半径。
实现代码正是利用了这个结构性约简：存在一个最优摆放，其两端分别是 \(49\) 和 \(50\)。由于把整个顺序反转后总长度不变，因此只需固定左端为 \(49\)、右端最终为 \(50\)，中间再去优化其余 \(19\) 个半径 \(30,31,\dots,48\) 的顺序即可。
令 \(S\subseteq\{30,31,\dots,48\}\) 表示尚未放置的内部半径集合，令 \(x\) 表示当前部分链条开放端最后一个球的半径。定义 \(F(S,x)\) 为：从这一状态继续完成摆放，并在最后接上半径 \(50\) 的球，所需增加的最小长度。
终止情形很直接：
$$F(\varnothing,x)=d(x,50)+50.$$
如果 \(S\neq\varnothing\)，下一颗球可以是任意 \(r\in S\)，于是有
$$F(S,x)=\min_{r\in S}\bigl(d(x,r)+F(S\setminus\{r\},r)\bigr).$$
因此，在乘上 \(1000\) 并取整之前，真实的最小管长就是
$$L_{\min}=49+F(\{30,31,\dots,48\},49).$$
这个递推是完全精确的，因为未来只由两件事决定：哪些半径还没有使用，以及当前开放端最后一个球的半径是多少。
C++ 实现里包含了一个很小的穷举校验：管半径取 \(R=8\)，球半径取 \(5,6,7,8\)。在这个例子里，最优顺序是
$$7,5,6,8$$
或者它的反向 \(8,6,5,7\)。三段相邻距离分别为
$$d(7,5)=\sqrt{12^2-4^2}=8\sqrt{2},\qquad d(5,6)=\sqrt{11^2-5^2}=4\sqrt{6},\qquad d(6,8)=\sqrt{14^2-2^2}=8\sqrt{3}.$$
所以总长度是
$$L=7+8+8\sqrt{2}+4\sqrt{6}+8\sqrt{3}\approx 49.9680739307.$$
这个小例子已经清楚展示了与完整题目相同的规律：最大的两个半径跑到两端，中间则通过大小交错来控制相邻和，从而压低总长度。
C++、Python 和 Java 实现都在求解同一个递推。每个状态由两部分组成：一是“还没用掉哪些内部半径”的位掩码，二是“当前部分排列开放端最后一个球”的半径。算法从这个状态出发，依次尝试所有剩余半径，加入相应的几何间距 \(d(x,r)\)，并把最优续接结果记忆化。
搜索从左端已经固定为 \(49\) 的状态开始，同时把 \(50\) 保留为必定最后接上的终点球。当位掩码为空时，算法只需再补上当前末球到 \(50\) 的最后一段距离，以及末端贡献 \(50\) 本身。得到最优实数长度以后，程序输出 \(\operatorname{round}(1000L)\)。
三种语言的存储方式略有区别。C++ 和 Java 使用按 \((\text{mask},\text{last})\) 编号的稠密浮点表，因为去掉 \(49\) 和 \(50\) 以后，可用掩码刚好形成大小为 \(2^{19}\) 的连续区间。Python 则用字典来保存同样的逻辑状态。除此之外，C++ 版本还会在上面的四球小例子上，把优化算法与完整穷举进行对照验证。
设 \(n=21\)。固定两端球之后，子集掩码里还剩 \(n-2=19\) 个半径。记忆化状态数是 \(O(n2^{n-2})\)，每个状态最多尝试 \(O(n)\) 个下一步，因此总时间复杂度为
$$O(n^2 2^{n-2}).$$
对 Problem 222 来说这完全可行，而暴力法则需要检查 \(21!\) 个不同顺序。空间复杂度为
$$O(n2^{n-2}),$$
在数组实现里大约对应 \(21\cdot 2^{19}\) 个浮点单元，再加上一点常数级辅助存储。
Труба имеет радиус \(R=50\), и в нее нужно поместить по одной сфере каждого целого радиуса \(30,31,\dots,50\). Если минимально возможная длина трубы равна \(L\), то требуется вывести \(\operatorname{round}(1000L)\).
Всего сфер \(21\), поэтому прямой перебор всех \(21!\) порядков невозможен. Реализации разделяют задачу на две части: геометрию, которая дает точную цену соседства двух радиусов, и комбинаторику, которая выбирает лучший общий порядок.
Как только порядок радиусов зафиксирован, оптимальное расположение центров уже полностью задается геометрией цилиндра. Тем самым пространственная задача упаковки превращается в задачу о кратчайшем пути по множеству радиусов.
Рассмотрим две соседние сферы радиусов \(a\) и \(b\) внутри трубы радиуса \(R\). В кратчайшей конфигурации каждая сфера прижата к стенке, потому что смещение центра дальше от оси только увеличивает поперечное расстояние и уменьшает необходимый продольный зазор.
Если центры находятся по разные стороны трубы, их поперечное расстояние равно
$$d_\perp=(R-a)+(R-b)=2R-a-b.$$
Сферы касаются друг друга, значит расстояние между центрами равно \(a+b\). По теореме Пифагора минимальный зазор вдоль оси трубы равен
$$d(a,b)=\sqrt{(a+b)^2-(2R-a-b)^2}=2\sqrt{R(a+b-R)}.$$
Именно эта величина вычисляется во всех трех реализациях. Для Problem 222 при \(R=50\) формула упрощается до
$$d(a,b)=10\sqrt{2(a+b-50)}.$$
Главное структурное наблюдение состоит в том, что стоимость пары зависит только от суммы \(a+b\), а как функция этой суммы она симметрична, возрастает и является вогнутой.
Пусть радиусы идут вдоль оси в порядке
$$r_1,r_2,\dots,r_n.$$
Если соседние сферы чередуются между двумя сторонами трубы, то левый конец трубы находится на расстоянии \(r_1\) от первого центра, правый конец на расстоянии \(r_n\) от последнего, а каждая соседняя пара вносит одно слагаемое \(d(r_i,r_{i+1})\). Поэтому
$$L(r_1,\dots,r_n)=r_1+\sum_{i=1}^{n-1} d(r_i,r_{i+1})+r_n.$$
При обращении порядка это выражение не меняется: крайний вклад по-прежнему равен \(r_1+r_n\), а те же попарные расстояния просто появляются в обратном направлении.
Стоимость \(d(a,b)\) является возрастающей вогнутой функцией от \(a+b\). Поэтому выгоднее смешивать большие и маленькие радиусы, чем заставлять большую внутреннюю сферу платить два крупных соседних вклада. Перестановочные аргументы для вогнутых попарных стоимостей выталкивают большие радиусы к краям и приводят к маятникообразному оптимальному порядку, в котором на концах стоят два наибольших радиуса.
Именно это сокращение используют реализации: существует оптимальная конфигурация с \(49\) на одном конце и \(50\) на другом. Так как обращение всего порядка не меняет длину, достаточно зафиксировать \(49\) в начале, \(50\) в конце и оптимизировать только \(19\) промежуточных радиусов \(30,31,\dots,48\).
Пусть \(S\subseteq\{30,31,\dots,48\}\) - множество внутренних радиусов, которые еще не использованы, а \(x\) - радиус сферы, стоящей сейчас на открытом конце уже построенной цепочки. Определим \(F(S,x)\) как минимальную дополнительную длину, необходимую для завершения раскладки и добавления в конце сферы радиуса \(50\).
Базовый случай записывается сразу:
$$F(\varnothing,x)=d(x,50)+50.$$
Если \(S\neq\varnothing\), следующей можно поставить любую сферу \(r\in S\), поэтому
$$F(S,x)=\min_{r\in S}\bigl(d(x,r)+F(S\setminus\{r\},r)\bigr).$$
Следовательно, полное решение до умножения на \(1000\) равно
$$L_{\min}=49+F(\{30,31,\dots,48\},49).$$
Эта рекурсия точна, потому что дальнейшее будущее определяется только двумя вещами: какие радиусы еще не использованы и какой радиус стоит на текущем открытом конце цепочки.
В реализации на C++ есть небольшая полная проверка для трубы радиуса \(R=8\) и сфер радиусов \(5,6,7,8\). Для этого случая лучший порядок таков:
$$7,5,6,8$$
или в обратном направлении \(8,6,5,7\). Три соседних расстояния равны
$$d(7,5)=\sqrt{12^2-4^2}=8\sqrt{2},\qquad d(5,6)=\sqrt{11^2-5^2}=4\sqrt{6},\qquad d(6,8)=\sqrt{14^2-2^2}=8\sqrt{3}.$$
Поэтому общая длина составляет
$$L=7+8+8\sqrt{2}+4\sqrt{6}+8\sqrt{3}\approx 49.9680739307.$$
Даже этот маленький пример показывает ту же структуру, что и полная задача: два наибольших радиуса уходят на концы, а внутри большие и маленькие значения чередуются, чтобы контролировать суммы соседних пар.
Реализации на C++, Python и Java вычисляют одну и ту же рекурсию. Состояние кодируется битовой маской неиспользованных внутренних радиусов и радиусом сферы, стоящей на открытом конце частично построенного расположения. Из этого состояния программа перебирает каждый оставшийся радиус, добавляет геометрический зазор \(d(x,r)\) и запоминает лучшую возможную продолженную конфигурацию.
Поиск стартует с уже зафиксированным слева радиусом \(49\), тогда как \(50\) оставляется как обязательная финальная сфера. Когда маска становится пустой, цепочка закрывается: добавляется последний промежуток до \(50\), а затем крайний вклад \(50\). После получения оптимальной вещественной длины программа возвращает \(\operatorname{round}(1000L)\).
Способ хранения немного отличается по языкам. Версии на C++ и Java используют плотные таблицы чисел с плавающей точкой, индексируемые парой \((\text{маска},\text{последний})\), что эффективно, потому что после удаления \(49\) и \(50\) остается непрерывный диапазон масок размера \(2^{19}\). Версия на Python использует словарь с тем же логическим состоянием. Кроме того, версия на C++ сравнивает оптимизированный алгоритм с полным перебором на описанном выше маленьком примере из четырех сфер.
Пусть \(n=21\). После фиксации двух крайних сфер в битовой маске остается \(n-2=19\) радиусов. Число мемоизированных состояний равно \(O(n2^{n-2})\), а каждое состояние рассматривает до \(O(n)\) следующих вариантов, поэтому время работы составляет
$$O(n^2 2^{n-2}).$$
Для Problem 222 это вполне практично, тогда как грубая сила требовала бы проверить \(21!\) различных порядков. Память равна
$$O(n2^{n-2}),$$
что в версиях на массивах означает примерно \(21\cdot 2^{19}\) элементов с плавающей точкой плюс небольшой вспомогательный объем.
نصف قطر الأنبوب هو \(R=50\)، ويجب وضع كرة واحدة لكل نصف قطر صحيح من \(30\) إلى \(50\) داخله. إذا كان أقصر طول ممكن للأنبوب هو \(L\)، فالمطلوب إخراج \(\operatorname{round}(1000L)\).
عدد الكرات هو \(21\)، ولذلك فإن فحص جميع الترتيبات وعددها \(21!\) غير عملي تمامًا. لهذا تفصل التطبيقات المسألة إلى جزأين: جزء هندسي يحسب الكلفة الدقيقة لوضع نصفي قطر متجاورين، وجزء تركيبي يختار أفضل ترتيب كلي.
بمجرد تثبيت ترتيب أنصاف الأقطار، يصبح التموضع الأمثل لمراكز الكرات محددًا بالكامل بواسطة هندسة الأسطوانة. عندها تتحول مسألة الرص ثلاثية الأبعاد إلى مسألة مسار أقصر على مجموعة أنصاف الأقطار.
لنأخذ كرتين متجاورتين نصفي قطريهما \(a\) و\(b\) داخل أنبوب نصف قطره \(R\). في الترتيب الأقصر تُدفَع كل كرة حتى تلامس الجدار، لأن إبعاد المركز أكثر عن المحور لا يفعل إلا زيادة الفصل العرضي، وبالتالي تقليل الفجوة المحورية المطلوبة.
إذا كان المركزان على جهتين متقابلتين من الأنبوب، فإن المسافة العرضية بينهما تساوي
$$d_\perp=(R-a)+(R-b)=2R-a-b.$$
وبما أن الكرتين متماسّتان، فالمسافة بين المركزين هي \(a+b\). ومن مبرهنة فيثاغورس نحصل على المسافة الدنيا المطلوبة على طول محور الأنبوب:
$$d(a,b)=\sqrt{(a+b)^2-(2R-a-b)^2}=2\sqrt{R(a+b-R)}.$$
وهذه هي بالضبط الكمية التي تحسبها تطبيقات C++ وPython وJava. وفي Problem 222 حيث \(R=50\)، تصبح الصيغة
$$d(a,b)=10\sqrt{2(a+b-50)}.$$
والحقيقة البنيوية المهمة هنا أن كلفة الزوج تعتمد فقط على المجموع \(a+b\)، وهي بوصفها دالة في هذا المجموع دالة متناظرة ومتزايدة ومقعّرة.
لنفرض أن الترتيب المحوري للكرات هو
$$r_1,r_2,\dots,r_n.$$
إذا كانت الكرات المتجاورة تتناوب بين جانبي الأنبوب، فإن طرف الأنبوب الأيسر يقع قبل أول مركز بمقدار \(r_1\)، والطرف الأيمن يقع بعد آخر مركز بمقدار \(r_n\)، وكل زوج متجاور يضيف فجوة واحدة مقدارها \(d(r_i,r_{i+1})\). لذا يكون
$$L(r_1,\dots,r_n)=r_1+\sum_{i=1}^{n-1} d(r_i,r_{i+1})+r_n.$$
وقلب الترتيب بالكامل لا يغيّر هذه القيمة، لأن مساهمة الطرفين تبقى \(r_1+r_n\)، والمسافات الزوجية نفسها تظهر فقط بالعكس.
الكلفة \(d(a,b)\) هي دالة متزايدة ومقعّرة في \(a+b\). وهذا يجعل مزج نصف قطر كبير مع نصف قطر صغير أفضل عادة من وضع نصف قطر كبير في الداخل بحيث يدفع كلفتي تجاور كبيرتين معًا. حجج المبادلة الخاصة بالكلف الزوجية المقعّرة تدفع أنصاف الأقطار الكبيرة نحو الخارج، وتنتج ترتيبًا أمثل شبيهًا بالبندول يكون طرفاه أكبر نصفَي قطر.
هذا هو الاختزال البنيوي الذي تستعمله التطبيقات: توجد هيئة مثلى يكون فيها \(49\) عند أحد الطرفين و\(50\) عند الطرف الآخر. وبما أن عكس الترتيب كله يعطي الطول نفسه، فيكفي تثبيت \(49\) كأول كرة و\(50\) كآخر كرة، ثم تحسين ترتيب الأنصاف التسعة عشر الواقعة بينهما، أي \(30,31,\dots,48\).
لتكن \(S\subseteq\{30,31,\dots,48\}\) مجموعة أنصاف الأقطار الداخلية التي لم توضع بعد، وليكن \(x\) نصف قطر الكرة الموجودة حاليًا عند الطرف المفتوح من السلسلة الجزئية. نعرّف \(F(S,x)\) بأنه أقل طول إضافي مطلوب لإكمال الترتيب ثم إلحاق الكرة النهائية ذات نصف القطر \(50\).
الحالة النهائية مباشرة:
$$F(\varnothing,x)=d(x,50)+50.$$
أما إذا كان \(S\neq\varnothing\)، فيمكن أن تكون الكرة التالية أي \(r\in S\)، ومن ثم
$$F(S,x)=\min_{r\in S}\bigl(d(x,r)+F(S\setminus\{r\},r)\bigr).$$
إذن فالطول الأدنى الحقيقي قبل الضرب في \(1000\) هو
$$L_{\min}=49+F(\{30,31,\dots,48\},49).$$
وهذه العلاقة دقيقة تمامًا، لأن المستقبل يعتمد فقط على معلومتين: ما أنصاف الأقطار التي ما زالت غير مستخدمة، وما نصف قطر الكرة الواقفة عند الطرف المفتوح الحالي.
تتضمن نسخة C++ فحصًا كاملاً صغيرًا عندما يكون نصف قطر الأنبوب \(R=8\) وأنصاف أقطار الكرات \(5,6,7,8\). في هذه الحالة يكون أفضل ترتيب هو
$$7,5,6,8$$
أو عكسه \(8,6,5,7\). والمسافات الثلاث بين الأزواج المتجاورة هي
$$d(7,5)=\sqrt{12^2-4^2}=8\sqrt{2},\qquad d(5,6)=\sqrt{11^2-5^2}=4\sqrt{6},\qquad d(6,8)=\sqrt{14^2-2^2}=8\sqrt{3}.$$
ومن ثم يكون الطول الكلي
$$L=7+8+8\sqrt{2}+4\sqrt{6}+8\sqrt{3}\approx 49.9680739307.$$
حتى هذا المثال الصغير يكشف البنية نفسها الموجودة في المسألة الكاملة: أكبر نصفَي قطر يذهبان إلى الطرفين، بينما يتناوب الداخل بين القيم الكبيرة والصغيرة لضبط مجاميع الأزواج المتجاورة.
تطبيقات C++ وPython وJava كلها تقيم علاقة العودية نفسها. فالحالة تمثل بقناع بتات يحدد أنصاف الأقطار الداخلية غير المستخدمة بعد، وبنصف قطر الكرة الموجودة عند الطرف المفتوح من الترتيب الجزئي. ومن هذه الحالة تجرّب الشيفرة كل نصف قطر متبقٍ، وتضيف الفجوة الهندسية \(d(x,r)\)، ثم تحفظ أفضل متابعة بطريقة الحفظ التذكري.
يبدأ البحث بعد تثبيت \(49\) في الطرف الأيسر، مع إبقاء \(50\) كرة نهائية مفروضة. وعندما يصبح القناع فارغًا، تُغلق السلسلة بإضافة المسافة الأخيرة إلى \(50\) ثم مساهمة النهاية \(50\) نفسها. وبعد إيجاد الطول الحقيقي الأمثل، يعيد كل برنامج القيمة \(\operatorname{round}(1000L)\).
تختلف طريقة التخزين قليلًا بين اللغات. فنسختا C++ وJava تستعملان جداول كثيفة من الأعداد العائمة مفهرسة بالزوج \((\text{mask},\text{last})\)، وهذا فعال لأن حذف \(49\) و\(50\) يترك مجال أقنعة متصلاً حجمه \(2^{19}\). أما نسخة Python فتستخدم قاموسًا بالمفتاح المنطقي نفسه. كذلك تتضمن نسخة C++ مقارنة بين الحل المحسن والبحث الشامل على مثال الكرات الأربع الصغير المذكور أعلاه.
لنضع \(n=21\). بعد تثبيت الكرتين الطرفيتين يبقى \(n-2=19\) نصف قطر داخل قناع المجموعات الجزئية. عدد الحالات المحفوظة هو \(O(n2^{n-2})\)، وكل حالة تفحص حتى \(O(n)\) اختيارًا لاحقًا، ولذلك يكون الزمن الكلي
$$O(n^2 2^{n-2}).$$
وهذا عملي جدًا في Problem 222، بينما كانت القوة الغاشمة ستحتاج إلى فحص \(21!\) ترتيبًا مختلفًا. أما الذاكرة فتساوي
$$O(n2^{n-2}),$$
وهو ما يعادل في النسخ المعتمدة على المصفوفات نحو \(21\cdot 2^{19}\) خانة عائمة، بالإضافة إلى قدر صغير من التخزين المساعد.