Each challenge gives a target integer \(t\) and a short list \(a_1,\dots,a_n\). We may choose any nonempty subset of positions, use each chosen number exactly once, and combine them with binary operations. The implementations allow addition, multiplication, positive subtraction, and exact division, so every intermediate result remains a positive integer.
For one challenge, the score is the smallest possible sum of the chosen numbers that can produce \(t\). If no legal expression reaches the target, the score is \(0\). The final answer is the weighted sum of the 200 challenge scores, with weights \(3^r\), taken modulo \(1005075251\).
Write \([n]=\{1,\dots,n\}\). For every nonempty subset \(A\subseteq [n]\), let
$$\sigma(A)=\sum_{i\in A} a_i.$$
The main task is to determine exactly which positive integers can be formed by expressions that use the positions in \(A\) and no others.
Any valid expression has a topmost operation whose left and right children are themselves valid expressions. Therefore the set of used positions splits into two disjoint nonempty parts \(B\) and \(C\) with
$$A=B\cup C,\qquad B\cap C=\varnothing,\qquad B\ne\varnothing,\qquad C\ne\varnothing.$$
This matters because the dynamic program is indexed by position sets, not by numeric values alone. If the same number appears twice in the input, those copies are still different leaves because they occupy different positions.
Let \(V(A)\) be the set of all positive integers reachable from the positions in \(A\), using each chosen input exactly once. For a singleton subset we have
$$V(\{i\})=\{a_i\}.$$
For a larger subset \(A\), the reachable values come from combining two smaller disjoint subsets:
$$V(A)=\bigcup_{\substack{B\cup C=A,\\B\cap C=\varnothing,\\B\ne\varnothing,\ C\ne\varnothing}} \operatorname{Combine}\bigl(V(B),V(C)\bigr).$$
For each pair \(x\in V(B)\) and \(y\in V(C)\), the combination step inserts \(x+y\), \(xy\), \(x-y\) when \(x>y\), \(y-x\) when \(y>x\), \(x/y\) when \(y\mid x\), and \(y/x\) when \(x\mid y\).
Because subtraction is kept only when the result is positive and division is kept only when it is exact, all states contain positive integers only.
The recurrence captures every legal expression tree. The base case is immediate for a single leaf. For a larger expression, inspect the root: its two children use disjoint nonempty position sets \(B\) and \(C\). By induction, the child values lie in \(V(B)\) and \(V(C)\), so the root value is produced by the combination rule and lies in \(V(A)\).
The converse direction is equally important. Every value inserted by the recurrence is obtained by taking one valid expression over \(B\), one valid expression over \(C\), and joining them by an allowed operation. So each DP-generated value corresponds to a legal expression. This two-way induction shows that \(V(A)\) is exactly the reachable set.
Once the reachable sets are known, the score of a single challenge is
$$s=\min\left\{\sigma(A): \varnothing\ne A\subseteq [n],\ t\in V(A)\right\},$$
with the convention \(s=0\) if the set is empty. The optimization target is the sum of the chosen input numbers, not the number of operations and not the size of the subset.
This is why the implementation precomputes \(\sigma(A)\) for every subset: the DP answers whether a subset can reach \(t\), and the subset sums turn that information into the required score.
If \(s_r\) denotes the score of challenge \(r\), then the global answer is
$$\mathrm{Ans}=\sum_{r=1}^{200} 3^r s_r \pmod{1005075251}.$$
The challenges do not interact mathematically, so the same subset DP is run for each one separately. Only the final weighted modular sum ties them together.
Take target \(t=2\) and numbers \((a_1,a_2,a_3)=(3,6,7)\). The singleton states are
$$V(\{1\})=\{3\},\qquad V(\{2\})=\{6\},\qquad V(\{3\})=\{7\}.$$
For the subset \(\{1,2\}\), combining \(3\) and \(6\) yields
$$V(\{1,2\})\supseteq \{3+6,\ 3\cdot 6,\ 6-3,\ 6/3\}=\{9,18,3,2\}.$$
So the target \(2\) is already reachable with subset sum \(\sigma(\{1,2\})=3+6=9\). The other two-element subsets give
$$V(\{1,3\})\supseteq \{10,21,4\},\qquad V(\{2,3\})\supseteq \{13,42,1\}.$$
No singleton reaches \(2\), and any three-element solution would use sum \(16\), which cannot beat \(9\). Therefore the challenge score is \(9\).
The C++, Python, and Java implementations all represent subsets by bitmasks. They first precompute the sum of every mask by removing one set bit and reusing the previously computed sum. This makes the subset-score lookup constant time once the table has been built.
They then build the reachable sets in increasing mask order. A one-bit mask stores its lone input value. For a larger mask, the implementation enumerates nonempty proper submasks, pairs each submask with its complement, and evaluates all allowed operations on every pair of stored values. A hash-based set removes duplicates automatically, which is essential because many different expression trees can lead to the same integer.
Because addition and multiplication are symmetric and the implementation already checks both directions for subtraction and division, it only needs one representative of each unordered split. After all states have been built, the program scans every mask whose reachable set contains the target, keeps the minimum subset sum, and returns \(0\) if none work. The outer loop updates the current power of \(3\) modulo \(1005075251\) and accumulates the weighted total.
Let \(n\) be the number of input values in one challenge. There are \(2^n-1\) nonempty masks. Precomputing all subset sums costs \(O(2^n)\) time and \(O(2^n)\) memory. Enumerating proper submasks across all masks gives the standard \(O(3^n)\) split count.
The dominant practical cost is the value pairing inside each split, so a precise bound is
$$O\left(\sum_{A\subseteq [n]}\ \sum_{\substack{B\cup C=A,\\B\cap C=\varnothing}} |V(B)|\,|V(C)|\right).$$
The memory usage is
$$O\left(2^n+\sum_{\varnothing\ne A\subseteq [n]} |V(A)|\right).$$
Since each challenge uses only a small input list, this exact set-based DP is feasible.
Jede Challenge liefert einen Zielwert \(t\) und eine kurze Liste \(a_1,\dots,a_n\). Man darf eine nichtleere Teilmenge der Positionen wählen, jede ausgewählte Zahl genau einmal benutzen und die Werte mit binären Operationen verknüpfen. Die Implementierungen erlauben Addition, Multiplikation, positive Subtraktion und exakte Division; dadurch bleiben alle Zwischenwerte positive ganze Zahlen.
Die Punktzahl einer einzelnen Challenge ist die kleinste mögliche Summe der verwendeten Eingabezahlen, mit der sich \(t\) erzeugen lässt. Wenn kein zulässiger Ausdruck das Ziel erreicht, ist die Punktzahl \(0\). Das Gesamtergebnis ist die gewichtete Summe der 200 Punktzahlen mit Gewichten \(3^r\), modulo \(1005075251\).
Schreibe \([n]=\{1,\dots,n\}\). Für jede nichtleere Teilmenge \(A\subseteq [n]\) definieren wir
$$\sigma(A)=\sum_{i\in A} a_i.$$
Die eigentliche Aufgabe besteht darin, exakt zu bestimmen, welche positiven ganzen Zahlen sich aus genau den Positionen in \(A\) konstruieren lassen.
Jeder gültige Ausdruck besitzt eine oberste Operation, deren linker und rechter Teil wiederum gültige Ausdrücke sind. Die benutzten Positionen zerfallen also in zwei disjunkte, nichtleere Mengen \(B\) und \(C\) mit
$$A=B\cup C,\qquad B\cap C=\varnothing,\qquad B\ne\varnothing,\qquad C\ne\varnothing.$$
Deshalb wird die Dynamik über Positionsmengen und nicht nur über Zahlenwerte formuliert. Falls derselbe Zahlenwert mehrfach vorkommt, sind diese Vorkommen trotzdem verschieden, weil sie auf unterschiedlichen Positionen liegen.
Sei \(V(A)\) die Menge aller positiven ganzen Zahlen, die sich aus den Positionen in \(A\) gewinnen lassen, wobei jede gewählte Zahl genau einmal benutzt wird. Für eine Einermenge gilt
$$V(\{i\})=\{a_i\}.$$
Für eine größere Menge \(A\) entstehen die Werte durch das Kombinieren zweier kleinerer disjunkter Teilmengen:
$$V(A)=\bigcup_{\substack{B\cup C=A,\\B\cap C=\varnothing,\\B\ne\varnothing,\ C\ne\varnothing}} \operatorname{Combine}\bigl(V(B),V(C)\bigr).$$
Für jedes Paar \(x\in V(B)\) und \(y\in V(C)\) werden \(x+y\), \(xy\), \(x-y\) bei \(x>y\), \(y-x\) bei \(y>x\), \(x/y\) bei \(y\mid x\) und \(y/x\) bei \(x\mid y\) eingefügt.
Weil Subtraktion nur mit positivem Ergebnis und Division nur bei exaktem Quotienten übernommen wird, enthalten alle Zustände ausschließlich positive ganze Zahlen.
Die Rekursion erfasst jeden zulässigen Ausdrucksbaum. Der Basisfall mit einem Blatt ist trivial. Für einen größeren Ausdruck betrachten wir die Wurzel: Ihre beiden Kinder benutzen disjunkte, nichtleere Positionsmengen \(B\) und \(C\). Nach Induktionsannahme liegen deren Werte in \(V(B)\) und \(V(C)\), also wird der Wurzelwert durch die Kombinationsregel erzeugt und liegt in \(V(A)\).
Umgekehrt ist ebenso wichtig: Jeder durch die Rekursion erzeugte Wert entsteht aus einem gültigen Ausdruck über \(B\), einem gültigen Ausdruck über \(C\) und einer erlaubten Operation an der Wurzel. Damit entspricht jeder DP-Wert einem legalen Ausdruck. Diese Zwei-Wege-Induktion zeigt, dass \(V(A)\) genau die erreichbare Menge ist.
Sind alle erreichbaren Mengen bekannt, so ist die Punktzahl einer einzelnen Challenge
$$s=\min\left\{\sigma(A): \varnothing\ne A\subseteq [n],\ t\in V(A)\right\},$$
wobei \(s=0\) gilt, falls die Menge leer ist. Optimiert wird also nicht die Anzahl der Operationen und auch nicht die Größe der Teilmenge, sondern die Summe der ausgewählten Eingabezahlen.
Genau deshalb berechnet die Implementierung \(\sigma(A)\) für jede Teilmenge vorab. Die DP beantwortet die Frage, ob \(A\) das Ziel \(t\) erreichen kann; die Teilmengensummen machen daraus die verlangte Punktzahl.
Bezeichnet \(s_r\) die Punktzahl der \(r\)-ten Challenge, dann lautet das globale Resultat
$$\mathrm{Ans}=\sum_{r=1}^{200} 3^r s_r \pmod{1005075251}.$$
Die Challenges sind mathematisch unabhängig voneinander. Deshalb wird dieselbe Teilmengen-DP für jede Zeile separat ausgeführt; nur die abschließende gewichtete Modulsumme verbindet die Ergebnisse.
Betrachte \(t=2\) und \((a_1,a_2,a_3)=(3,6,7)\). Die Einermengen liefern
$$V(\{1\})=\{3\},\qquad V(\{2\})=\{6\},\qquad V(\{3\})=\{7\}.$$
Für die Teilmenge \(\{1,2\}\) erhält man durch Kombination von \(3\) und \(6\)
$$V(\{1,2\})\supseteq \{3+6,\ 3\cdot 6,\ 6-3,\ 6/3\}=\{9,18,3,2\}.$$
Damit ist das Ziel \(2\) bereits mit Teilmengensumme \(\sigma(\{1,2\})=3+6=9\) erreichbar. Die beiden anderen Zweiermengen liefern
$$V(\{1,3\})\supseteq \{10,21,4\},\qquad V(\{2,3\})\supseteq \{13,42,1\}.$$
Keine Einermenge erreicht \(2\), und jede Dreierlösung hätte Summe \(16\), also schlechter als \(9\). Folglich ist die Challenge-Punktzahl gleich \(9\).
Die C++-, Python- und Java-Implementierungen kodieren Teilmengen als Bitmasken. Zuerst berechnen sie die Summe jeder Maske, indem sie ein gesetztes Bit entfernen und die bereits bekannte Summe der kleineren Maske wiederverwenden. Danach kann jede Teilmengensumme in konstanter Zeit abgefragt werden.
Anschließend werden die erreichbaren Mengen in aufsteigender Maskenreihenfolge aufgebaut. Eine Ein-Bit-Maske speichert ihren einzelnen Eingangswert. Für eine größere Maske werden alle nichtleeren echten Teilmasken betrachtet, mit ihrem Komplement gepaart und alle erlaubten Operationen auf jedes Wertepaar angewandt. Eine hashbasierte Menge entfernt Duplikate automatisch; das ist wichtig, weil viele verschiedene Ausdrucksbäume dieselbe Zahl erzeugen können.
Da Addition und Multiplikation symmetrisch sind und die Implementierung bei Subtraktion und Division bereits beide Richtungen prüft, genügt ein Repräsentant pro ungeordneter Zerlegung. Nachdem alle Zustände aufgebaut sind, durchsucht das Programm alle Masken, deren Menge das Ziel enthält, merkt sich die kleinste Teilmengensumme und liefert \(0\), falls keine Maske funktioniert. Die äußere Schleife aktualisiert die aktuelle Potenz von \(3\) modulo \(1005075251\) und akkumuliert die gewichtete Summe.
Sei \(n\) die Anzahl der Eingabewerte einer Challenge. Es gibt \(2^n-1\) nichtleere Masken. Das Vorberechnen aller Teilmengensummen kostet \(O(2^n)\) Zeit und \(O(2^n)\) Speicher. Das Aufzählen echter Teilmasken über alle Masken hinweg liefert die Standardgröße \(O(3^n)\).
Der praktisch dominierende Aufwand ist das Paaren der gespeicherten Werte innerhalb jeder Zerlegung. Eine präzisere Schranke lautet daher
$$O\left(\sum_{A\subseteq [n]}\ \sum_{\substack{B\cup C=A,\\B\cap C=\varnothing}} |V(B)|\,|V(C)|\right).$$
Der Speicherbedarf ist
$$O\left(2^n+\sum_{\varnothing\ne A\subseteq [n]} |V(A)|\right).$$
Da jede Challenge nur eine kleine Eingabeliste besitzt, bleibt diese exakte mengenbasierte DP praktikabel.
Her challenge, bir hedef tam sayı \(t\) ve kısa bir \(a_1,\dots,a_n\) listesi verir. Boş olmayan herhangi bir konum altkümesini seçebilir, seçilen her sayıyı tam bir kez kullanabilir ve bunları ikili işlemlerle birleştirebiliriz. Uygulamalar toplama, çarpma, pozitif çıkarma ve tam bölmeyi kabul eder; bu yüzden tüm ara sonuçlar pozitif tamsayı olarak kalır.
Tek bir challenge için skor, \(t\)'yi üretebilen seçili sayıların toplamı bakımından en küçük değerdir. Hedefe ulaşan geçerli bir ifade yoksa skor \(0\) olur. Nihai cevap, 200 challenge skorunun \(3^r\) ağırlıklarıyla alınmış ve \(1005075251\) moduna göre hesaplanmış toplamıdır.
\([n]=\{1,\dots,n\}\) yazalım. Her boş olmayan \(A\subseteq [n]\) altkümesi için
$$\sigma(A)=\sum_{i\in A} a_i$$
tanımını yapalım. Asıl amaç, yalnızca \(A\) içindeki konumlar kullanıldığında hangi pozitif tamsayıların elde edilebildiğini tam olarak bulmaktır.
Geçerli her ifadenin en üstünde bir işlem vardır ve bu işlemin sol ile sağ tarafı yine geçerli iki alt ifadedir. Dolayısıyla kullanılan konumlar iki ayrık ve boş olmayan küme \(B\) ile \(C\)'ye ayrılır:
$$A=B\cup C,\qquad B\cap C=\varnothing,\qquad B\ne\varnothing,\qquad C\ne\varnothing.$$
Bu nokta önemlidir; çünkü dinamik program yalnızca sayısal değerlere göre değil, konum kümelerine göre kuruludur. Aynı sayı girişte iki kez geçse bile, farklı konumlarda durduğu için bunlar farklı yapraklar sayılır.
\(V(A)\), \(A\) içindeki konumlardan ve her seçili girdiyi tam bir kez kullanarak üretilebilen tüm pozitif tamsayıların kümesi olsun. Tek elemanlı durumda
$$V(\{i\})=\{a_i\}$$
olur. Daha büyük bir \(A\) için değerler, iki ayrık küçük altkümeyi birleştirerek elde edilir:
$$V(A)=\bigcup_{\substack{B\cup C=A,\\B\cap C=\varnothing,\\B\ne\varnothing,\ C\ne\varnothing}} \operatorname{Combine}\bigl(V(B),V(C)\bigr).$$
Burada her \(x\in V(B)\) ve \(y\in V(C)\) çifti için \(x+y\), \(xy\), \(x>y\) ise \(x-y\), \(y>x\) ise \(y-x\), \(y\mid x\) ise \(x/y\) ve \(x\mid y\) ise \(y/x\) eklenir.
Çıkarma yalnızca sonuç pozitif olduğunda, bölme ise yalnızca tam olduğunda tutulduğu için bütün durumlar sadece pozitif tamsayılar içerir.
Bu bağıntı her geçerli ifade ağacını kapsar. Taban durum tek yapraklı ifadedir. Daha büyük bir ifadede köke bakarız: sol ve sağ alt ifadeler ayrık, boş olmayan \(B\) ve \(C\) konum kümelerini kullanır. İndüksiyon varsayımına göre bu alt ifadelerin değerleri \(V(B)\) ve \(V(C)\) içindedir; o halde kökteki değer de birleştirme kuralıyla üretilir ve \(V(A)\) içine düşer.
Tersi yön de aynı derecede önemlidir. Bağıntının eklediği her değer, \(B\) üzerinde geçerli bir ifade, \(C\) üzerinde geçerli bir ifade ve kökte izin verilen bir işlem seçilerek oluşur. Yani DP'nin ürettiği her değer gerçekten geçerli bir ifadeye karşılık gelir. Bu çift yönlü indüksiyon, \(V(A)\)'nın tam olarak ulaşılabilir küme olduğunu kanıtlar.
Tüm ulaşılabilir kümeler bilindiğinde, bir challenge'ın skoru
$$s=\min\left\{\sigma(A): \varnothing\ne A\subseteq [n],\ t\in V(A)\right\}$$
şeklindedir; küme boşsa \(s=0\) kabul edilir. Burada minimize edilen şey işlem sayısı ya da kullanılan eleman sayısı değil, seçilen giriş sayılarının toplamıdır.
Bu nedenle uygulama her altküme için \(\sigma(A)\) değerini önceden hesaplar. DP, bir altkümeyle \(t\)'ye ulaşılıp ulaşılamadığını söyler; altküme toplamları ise bunu istenen skora dönüştürür.
\(s_r\), \(r\). challenge'ın skoru olsun. O zaman genel cevap
$$\mathrm{Ans}=\sum_{r=1}^{200} 3^r s_r \pmod{1005075251}$$
olur. Challenge'lar matematiksel olarak birbirinden bağımsızdır; bu yüzden aynı altküme DP'si her satır için ayrı ayrı çalıştırılır. Onları birbirine bağlayan tek şey, sondaki ağırlıklı modüler toplamdır.
\(t=2\) ve \((a_1,a_2,a_3)=(3,6,7)\) olsun. Tek elemanlı durumlar
$$V(\{1\})=\{3\},\qquad V(\{2\})=\{6\},\qquad V(\{3\})=\{7\}$$
şeklindedir. \(\{1,2\}\) altkümesinde \(3\) ile \(6\)'yı birleştirince
$$V(\{1,2\})\supseteq \{3+6,\ 3\cdot 6,\ 6-3,\ 6/3\}=\{9,18,3,2\}$$
elde edilir. Böylece hedef \(2\), \(\sigma(\{1,2\})=3+6=9\) toplamıyla zaten elde edilmiştir. Diğer iki elemanlı altkümeler
$$V(\{1,3\})\supseteq \{10,21,4\},\qquad V(\{2,3\})\supseteq \{13,42,1\}$$
değerlerini verir. Hiçbir tekli altküme \(2\)'ye ulaşamaz; üç elemanlı herhangi bir çözüm ise toplam \(16\) kullanacağı için \(9\)'dan daha iyi olamaz. Dolayısıyla challenge skoru \(9\)'dur.
C++, Python ve Java uygulamalarının üçü de altkümeleri bit maskeleriyle temsil eder. Önce her maskenin toplamı, maskeden bir set biti çıkarıp daha önce hesaplanmış küçük maskenin toplamını kullanarak hesaplanır. Böylece altküme skoru tablosu sabit zamanda okunabilir hale gelir.
Daha sonra ulaşılabilir kümeler, maske değeri artan sırada kurulur. Tek bitli bir maske yalnızca kendi giriş değerini içerir. Daha büyük bir maskede tüm boş olmayan gerçek altmaskeler gezilir, her altmaske tümleyeniyle eşleştirilir ve depolanmış değer çiftleri üzerinde izin verilen işlemler uygulanır. Hash tabanlı küme yapısı tekrarları otomatik temizler; bu kritik önemdedir, çünkü farklı ifade ağaçları aynı sayıyı sık sık üretebilir.
Toplama ve çarpma simetrik olduğundan, ayrıca uygulama çıkarma ve bölmenin iki yönünü de zaten denediğinden, sırasız her bölünme için tek temsilci yeterlidir. Tüm durumlar tamamlandıktan sonra program, hedefi içeren bütün maskeleri tarar, en küçük altküme toplamını saklar ve hiçbir maske uygun değilse \(0\) döndürür. Dış döngü de \(3\)'ün mevcut kuvvetini \(1005075251\) modunda günceller ve ağırlıklı toplamı biriktirir.
\(n\), tek bir challenge içindeki giriş sayısı olsun. Boş olmayan maske sayısı \(2^n-1\)'dir. Bütün altküme toplamlarını önceden hesaplamak \(O(2^n)\) zaman ve \(O(2^n)\) bellek ister. Tüm maskelerde gerçek altmaske dolaşımı, standart olarak \(O(3^n)\) bölünme sayısı verir.
Pratikte baskın maliyet, her bölünmede saklanan değerlerin eşleştirilmesidir. Bu nedenle daha kesin sınır
$$O\left(\sum_{A\subseteq [n]}\ \sum_{\substack{B\cup C=A,\\B\cap C=\varnothing}} |V(B)|\,|V(C)|\right)$$
şeklindedir. Bellek kullanımı ise
$$O\left(2^n+\sum_{\varnothing\ne A\subseteq [n]} |V(A)|\right)$$
olur. Her challenge küçük bir giriş listesi içerdiği için bu tam küme-tabanlı DP uygulanabilir durumdadır.
Cada reto proporciona un objetivo entero \(t\) y una lista corta \(a_1,\dots,a_n\). Podemos elegir cualquier subconjunto no vacío de posiciones, usar cada número elegido exactamente una vez y combinarlos mediante operaciones binarias. Las implementaciones permiten suma, multiplicación, resta positiva y división exacta, así que todos los valores intermedios siguen siendo enteros positivos.
La puntuación de un reto es la menor suma posible de los números elegidos con la que se puede obtener \(t\). Si ninguna expresión válida alcanza el objetivo, la puntuación es \(0\). La respuesta final es la suma ponderada de las 200 puntuaciones, con pesos \(3^r\), tomada módulo \(1005075251\).
Escribimos \([n]=\{1,\dots,n\}\). Para cada subconjunto no vacío \(A\subseteq [n]\), definimos
$$\sigma(A)=\sum_{i\in A} a_i.$$
La cuestión central es determinar exactamente qué enteros positivos pueden formarse usando las posiciones de \(A\) y ninguna otra.
Toda expresión válida tiene una operación en la raíz y dos subexpresiones válidas como hijos. Por lo tanto, las posiciones utilizadas se separan en dos partes disjuntas y no vacías \(B\) y \(C\) tales que
$$A=B\cup C,\qquad B\cap C=\varnothing,\qquad B\ne\varnothing,\qquad C\ne\varnothing.$$
Esto explica por qué la programación dinámica se indexa por conjuntos de posiciones y no sólo por valores numéricos. Si el mismo número aparece dos veces en la entrada, sus dos copias siguen siendo hojas distintas porque ocupan posiciones diferentes.
Sea \(V(A)\) el conjunto de todos los enteros positivos alcanzables a partir de las posiciones en \(A\), usando cada entrada elegida exactamente una vez. Para un singleton se tiene
$$V(\{i\})=\{a_i\}.$$
Para un subconjunto mayor \(A\), los valores se obtienen combinando dos subconjuntos disjuntos más pequeños:
$$V(A)=\bigcup_{\substack{B\cup C=A,\\B\cap C=\varnothing,\\B\ne\varnothing,\ C\ne\varnothing}} \operatorname{Combine}\bigl(V(B),V(C)\bigr).$$
Para cada par \(x\in V(B)\) y \(y\in V(C)\), se añaden \(x+y\), \(xy\), \(x-y\) si \(x>y\), \(y-x\) si \(y>x\), \(x/y\) si \(y\mid x\), y \(y/x\) si \(x\mid y\).
Como la resta sólo se conserva cuando el resultado es positivo y la división sólo cuando es exacta, todos los estados contienen enteros positivos.
La recurrencia captura cualquier árbol de expresión legal. El caso base con una sola hoja es inmediato. En una expresión mayor, miramos la raíz: sus dos hijos usan conjuntos disjuntos y no vacíos \(B\) y \(C\). Por hipótesis inductiva, los valores de esos hijos pertenecen a \(V(B)\) y \(V(C)\), así que el valor de la raíz se genera por la regla de combinación y pertenece a \(V(A)\).
La dirección inversa también es esencial. Cada valor insertado por la recurrencia surge al tomar una expresión válida sobre \(B\), otra sobre \(C\), y unirlas con una operación permitida. En consecuencia, cada valor producido por la DP corresponde a una expresión legal. Esta inducción en ambos sentidos prueba que \(V(A)\) es exactamente el conjunto alcanzable.
Una vez conocidos todos los conjuntos alcanzables, la puntuación de un reto es
$$s=\min\left\{\sigma(A): \varnothing\ne A\subseteq [n],\ t\in V(A)\right\},$$
con la convención \(s=0\) si el conjunto es vacío. No se minimiza el número de operaciones ni el tamaño del subconjunto, sino la suma de los números de entrada elegidos.
Por eso la implementación precalcula \(\sigma(A)\) para cada subconjunto. La DP responde si un subconjunto puede alcanzar \(t\), y las sumas de subconjunto convierten esa respuesta en la puntuación pedida.
Si \(s_r\) es la puntuación del reto \(r\), entonces la respuesta global es
$$\mathrm{Ans}=\sum_{r=1}^{200} 3^r s_r \pmod{1005075251}.$$
Los retos son independientes entre sí, así que la misma DP por subconjuntos se ejecuta por separado para cada línea. Sólo la suma modular ponderada final los une.
Tomemos \(t=2\) y \((a_1,a_2,a_3)=(3,6,7)\). Los estados unitarios son
$$V(\{1\})=\{3\},\qquad V(\{2\})=\{6\},\qquad V(\{3\})=\{7\}.$$
Para el subconjunto \(\{1,2\}\), al combinar \(3\) y \(6\) se obtiene
$$V(\{1,2\})\supseteq \{3+6,\ 3\cdot 6,\ 6-3,\ 6/3\}=\{9,18,3,2\}.$$
Por tanto, el objetivo \(2\) ya es alcanzable con suma \(\sigma(\{1,2\})=3+6=9\). Los otros subconjuntos de tamaño dos producen
$$V(\{1,3\})\supseteq \{10,21,4\},\qquad V(\{2,3\})\supseteq \{13,42,1\}.$$
Ningún singleton alcanza \(2\), y cualquier solución que use los tres números tendría suma \(16\), que no puede mejorar \(9\). Así, la puntuación del reto es \(9\).
Las implementaciones en C++, Python y Java representan los subconjuntos mediante máscaras de bits. Primero precalculan la suma de cada máscara quitando un bit activo y reutilizando la suma ya conocida de la máscara menor. Así, consultar la suma de un subconjunto pasa a costar tiempo constante.
Después construyen los conjuntos alcanzables en orden creciente de máscara. Una máscara con un solo bit contiene únicamente su valor de entrada. Para una máscara mayor, la implementación enumera submáscaras propias no vacías, empareja cada una con su complemento y evalúa todas las operaciones permitidas sobre cada par de valores almacenados. Un conjunto hash elimina duplicados automáticamente, algo crucial porque muchos árboles de expresión distintos pueden producir el mismo entero.
Como suma y multiplicación son simétricas y la implementación ya comprueba ambas direcciones de resta y división, basta con un representante de cada partición no ordenada. Cuando todos los estados están listos, el programa recorre las máscaras cuyo conjunto contiene el objetivo, conserva la menor suma de subconjunto y devuelve \(0\) si ninguna sirve. El bucle exterior actualiza la potencia actual de \(3\) módulo \(1005075251\) y acumula el total ponderado.
Sea \(n\) el número de valores de entrada de un reto. Existen \(2^n-1\) máscaras no vacías. Precalcular todas las sumas de subconjuntos cuesta \(O(2^n)\) tiempo y \(O(2^n)\) memoria. Enumerar submáscaras propias sobre todas las máscaras da el conteo estándar \(O(3^n)\).
El coste práctico dominante es combinar los valores almacenados dentro de cada partición. Por tanto, una cota más precisa es
$$O\left(\sum_{A\subseteq [n]}\ \sum_{\substack{B\cup C=A,\\B\cap C=\varnothing}} |V(B)|\,|V(C)|\right).$$
La memoria usada es
$$O\left(2^n+\sum_{\varnothing\ne A\subseteq [n]} |V(A)|\right).$$
Como cada reto contiene pocos números, esta DP exacta basada en conjuntos resulta viable.
每个挑战给出一个目标整数 \(t\) 和一个较短的整数列表 \(a_1,\dots,a_n\)。我们可以任选一个非空位置子集，把其中每个数恰好使用一次，并用二元运算把它们组合起来。三份实现都允许加法、乘法、正差以及整除，因此所有中间结果始终保持为正整数。
单个挑战的分数，是所有能够得到 \(t\) 的合法表达式中，所用输入数字之和的最小值。如果不存在合法表达式得到目标，则该挑战分数记为 \(0\)。最终答案是这 200 个挑战分数按 \(3^r\) 加权后的总和，并对 \(1005075251\) 取模。
记 \([n]=\{1,\dots,n\}\)。对每个非空子集 \(A\subseteq [n]\)，定义
$$\sigma(A)=\sum_{i\in A} a_i.$$
核心问题是：如果恰好使用 \(A\) 中这些位置上的数，那么究竟能构造出哪些正整数。
任意合法表达式都有一个最顶层运算，而它的左右子树本身又是合法表达式。因此，整棵树使用到的位置集合一定能拆成两个互不相交且都非空的部分 \(B\) 与 \(C\)，满足
$$A=B\cup C,\qquad B\cap C=\varnothing,\qquad B\ne\varnothing,\qquad C\ne\varnothing.$$
这就是为什么动态规划必须按“位置集合”建模，而不能只按数值建模。即使输入里有两个相同的数字，它们只要来自不同位置，在表达式树里就是不同的叶子。
设 \(V(A)\) 表示：恰好使用 \(A\) 中的位置、且每个被选数字只使用一次时，能够得到的全部正整数集合。若 \(A\) 只有一个位置，则
$$V(\{i\})=\{a_i\}.$$
若 \(A\) 更大，则其可达值来自两个更小的互斥子集的组合：
$$V(A)=\bigcup_{\substack{B\cup C=A,\\B\cap C=\varnothing,\\B\ne\varnothing,\ C\ne\varnothing}} \operatorname{Combine}\bigl(V(B),V(C)\bigr).$$
这里的组合规则是：对任意 \(x\in V(B)\) 与 \(y\in V(C)\)，加入 \(x+y\)、\(xy\)、当 \(x>y\) 时加入 \(x-y\)、当 \(y>x\) 时加入 \(y-x\)、当 \(y\mid x\) 时加入 \(x/y\)、当 \(x\mid y\) 时加入 \(y/x\)。
由于减法只保留正结果，而除法只保留整除结果，所以每个状态里都只会出现正整数。
这个递推覆盖了所有合法表达式树。单叶情形显然成立。对于更大的表达式，只要看根节点即可：左右两棵子树分别使用两个互不相交且都非空的位置集合 \(B\) 与 \(C\)。根据归纳假设，左右子树的值分别落在 \(V(B)\) 和 \(V(C)\) 中，于是根节点的值必然通过组合规则被加入 \(V(A)\)。
反过来，递推式生成的每一个值，也都来自某个 \(B\) 上的合法表达式、某个 \(C\) 上的合法表达式，以及根上的一个允许操作。因此 DP 插入的每个值都对应一棵真正合法的表达式树。双向归纳说明 \(V(A)\) 恰好就是完整的可达集合。
当所有可达集合都计算出来以后，单个挑战的分数就是
$$s=\min\left\{\sigma(A): \varnothing\ne A\subseteq [n],\ t\in V(A)\right\},$$
若该集合为空，则约定 \(s=0\)。需要最小化的不是运算次数，也不是所用数字个数，而是被选输入数字的和。
因此实现会先把每个子集的 \(\sigma(A)\) 预处理出来。DP 负责回答“这个子集能不能得到 \(t\)”，而子集和则把这个判定转化为题目要求的分数。
若第 \(r\) 个挑战的分数是 \(s_r\)，那么总答案为
$$\mathrm{Ans}=\sum_{r=1}^{200} 3^r s_r \pmod{1005075251}.$$
各个挑战之间在数学上彼此独立，因此同一套子集 DP 会对每一行输入分别执行一遍。把它们联系起来的只有最后这一步带权模和。
取目标 \(t=2\)，并设 \((a_1,a_2,a_3)=(3,6,7)\)。单元素状态为
$$V(\{1\})=\{3\},\qquad V(\{2\})=\{6\},\qquad V(\{3\})=\{7\}.$$
对子集 \(\{1,2\}\)，用 \(3\) 和 \(6\) 组合可得
$$V(\{1,2\})\supseteq \{3+6,\ 3\cdot 6,\ 6-3,\ 6/3\}=\{9,18,3,2\}.$$
因此目标 \(2\) 已经可以由子集 \(\{1,2\}\) 达到，其子集和为 \(\sigma(\{1,2\})=3+6=9\)。另外两个二元子集给出
$$V(\{1,3\})\supseteq \{10,21,4\},\qquad V(\{2,3\})\supseteq \{13,42,1\}.$$
任何单元素子集都无法得到 \(2\)，而如果使用三个数，总和一定是 \(16\)，不可能优于 \(9\)。所以这个挑战的分数就是 \(9\)。
C++、Python 和 Java 实现都用位掩码表示子集。第一步先预处理每个掩码对应的元素和：从当前掩码里去掉一个置位比特，再复用更小掩码已经算好的总和。这样一来，任何子集的分数查询都变成常数时间。
接着，程序按掩码递增顺序构造所有可达集合。只有一个比特的掩码直接保存对应输入值。对于更大的掩码，实现会枚举所有非空真子掩码，把它与补集配成一对，并对两个状态中存储的每个值对执行所有允许操作。哈希集合自动去重，这一点非常关键，因为很多不同的表达式树会得到同一个整数。
由于加法和乘法本身对称，而实现对减法和除法又同时检查了两个方向，所以每个无序划分只处理一个代表即可。所有状态构造完成后，程序扫描所有包含目标值的掩码，保留最小子集和；如果没有任何掩码可行，就返回 \(0\)。最外层循环则维护当前的 \(3\) 的幂，对 \(1005075251\) 取模，并不断累加带权总和。
设单个挑战里有 \(n\) 个输入数，则非空掩码共有 \(2^n-1\) 个。预处理所有子集和需要 \(O(2^n)\) 时间和 \(O(2^n)\) 空间。对所有掩码枚举真子掩码，标准结论是总共有 \(O(3^n)\) 次划分访问。
实际主耗时来自每次划分内部的值对组合，因此更精确的上界是
$$O\left(\sum_{A\subseteq [n]}\ \sum_{\substack{B\cup C=A,\\B\cap C=\varnothing}} |V(B)|\,|V(C)|\right).$$
空间复杂度为
$$O\left(2^n+\sum_{\varnothing\ne A\subseteq [n]} |V(A)|\right).$$
因为每个挑战的输入规模都很小，这种精确的集合型动态规划在这里是可行的。
В каждом испытании дан целевой целый \(t\) и короткий список \(a_1,\dots,a_n\). Можно выбрать любое непустое подмножество позиций, использовать каждое выбранное число ровно один раз и объединять их бинарными операциями. Реализации разрешают сложение, умножение, положительную разность и точное деление, поэтому все промежуточные значения остаются положительными целыми числами.
Очки одного испытания равны минимальной возможной сумме выбранных входных чисел, с помощью которой удается получить \(t\). Если допустимого выражения нет, очки равны \(0\). Итоговый ответ представляет собой взвешенную сумму 200 таких значений с весами \(3^r\), вычисленную по модулю \(1005075251\).
Пусть \([n]=\{1,\dots,n\}\). Для каждого непустого подмножества \(A\subseteq [n]\) определим
$$\sigma(A)=\sum_{i\in A} a_i.$$
Главная задача состоит в точном описании того, какие положительные целые числа можно построить, если использовать ровно позиции из \(A\).
У любого корректного выражения есть верхняя операция, а ее левый и правый потомки сами являются корректными выражениями. Значит, множество использованных позиций разбивается на две непустые непересекающиеся части \(B\) и \(C\), для которых
$$A=B\cup C,\qquad B\cap C=\varnothing,\qquad B\ne\varnothing,\qquad C\ne\varnothing.$$
Именно поэтому динамика строится по множествам позиций, а не только по числовым значениям. Если в списке два одинаковых числа, это все равно разные листья, потому что они стоят на разных позициях.
Обозначим через \(V(A)\) множество всех положительных целых чисел, достижимых из позиций в \(A\), если каждое выбранное число используется ровно один раз. Для одноэлементного множества имеем
$$V(\{i\})=\{a_i\}.$$
Для большего множества \(A\) значения получаются объединением двух меньших непересекающихся подмножеств:
$$V(A)=\bigcup_{\substack{B\cup C=A,\\B\cap C=\varnothing,\\B\ne\varnothing,\ C\ne\varnothing}} \operatorname{Combine}\bigl(V(B),V(C)\bigr).$$
Для каждой пары \(x\in V(B)\) и \(y\in V(C)\) добавляются \(x+y\), \(xy\), \(x-y\) при \(x>y\), \(y-x\) при \(y>x\), \(x/y\) при \(y\mid x\), и \(y/x\) при \(x\mid y\).
Поскольку разность сохраняется только при положительном результате, а деление только при точной делимости, все состояния содержат лишь положительные целые числа.
Рекурсия охватывает любое допустимое дерево выражения. База с одним листом очевидна. Для более крупного выражения достаточно посмотреть на корень: два его поддерева используют непустые непересекающиеся множества позиций \(B\) и \(C\). По индукционному предположению значения поддеревьев лежат в \(V(B)\) и \(V(C)\), следовательно, значение в корне создается правилом объединения и попадает в \(V(A)\).
Обратное направление столь же важно. Каждый добавленный рекурсией результат получается из одного корректного выражения на \(B\), одного корректного выражения на \(C\) и разрешенной операции в корне. Значит, любой DP-результат действительно соответствует допустимому выражению. Эта двусторонняя индукция доказывает, что \(V(A)\) совпадает с полным множеством достижимых значений.
Когда все множества достижимости построены, очки одного испытания равны
$$s=\min\left\{\sigma(A): \varnothing\ne A\subseteq [n],\ t\in V(A)\right\},$$
а если это множество пусто, полагаем \(s=0\). Минимизируется не число операций и не размер подмножества, а сумма выбранных входных чисел.
Именно поэтому реализация заранее считает \(\sigma(A)\) для каждого подмножества. Динамика отвечает на вопрос, может ли данное подмножество получить \(t\), а суммы подмножеств превращают этот факт в требуемое количество очков.
Если \(s_r\) обозначает очки \(r\)-го испытания, то итоговый ответ равен
$$\mathrm{Ans}=\sum_{r=1}^{200} 3^r s_r \pmod{1005075251}.$$
Математически испытания независимы, поэтому одна и та же динамика по подмножествам запускается отдельно для каждой строки. Связь между ними возникает только в финальной взвешенной сумме по модулю.
Возьмем \(t=2\) и \((a_1,a_2,a_3)=(3,6,7)\). Одноэлементные состояния таковы:
$$V(\{1\})=\{3\},\qquad V(\{2\})=\{6\},\qquad V(\{3\})=\{7\}.$$
Для подмножества \(\{1,2\}\), комбинируя \(3\) и \(6\), получаем
$$V(\{1,2\})\supseteq \{3+6,\ 3\cdot 6,\ 6-3,\ 6/3\}=\{9,18,3,2\}.$$
Значит, цель \(2\) уже достижима при сумме \(\sigma(\{1,2\})=3+6=9\). Два других двухэлементных подмножества дают
$$V(\{1,3\})\supseteq \{10,21,4\},\qquad V(\{2,3\})\supseteq \{13,42,1\}.$$
Ни одно одиночное число не дает \(2\), а любое решение с тремя числами имело бы сумму \(16\), то есть не могло бы улучшить \(9\). Следовательно, очки этого испытания равны \(9\).
Реализации на C++, Python и Java представляют подмножества битовыми масками. Сначала они предвычисляют сумму для каждой маски: удаляют один установленный бит и используют уже найденную сумму для меньшей маски. После этого сумма любого подмножества считывается за константное время.
Далее множества достижимости строятся в порядке возрастания маски. Маска с одним битом хранит единственное исходное значение. Для большей маски перебираются непустые собственные подмаски, каждая подмаска сочетается со своим дополнением, и все разрешенные операции применяются ко всем парам сохраненных значений. Хеш-множество автоматически удаляет повторы, что критично, поскольку разные деревья выражений часто приводят к одному и тому же числу.
Так как сложение и умножение симметричны, а реализация уже проверяет оба направления вычитания и деления, достаточно обрабатывать по одному представителю каждой неупорядоченной разбивки. Когда все состояния готовы, программа просматривает все маски, содержащие цель, удерживает минимальную сумму подмножества и возвращает \(0\), если подходящей маски нет. Внешний цикл поддерживает текущую степень числа \(3\) по модулю \(1005075251\) и накапливает взвешенную сумму.
Пусть \(n\) — число входных значений в одном испытании. Непустых масок \(2^n-1\). Предвычисление всех сумм подмножеств требует \(O(2^n)\) времени и \(O(2^n)\) памяти. Перебор собственных подмасок по всем маскам дает стандартную оценку \(O(3^n)\).
Практически доминирует объединение сохраненных значений внутри каждой разбивки, поэтому более точная граница такова:
$$O\left(\sum_{A\subseteq [n]}\ \sum_{\substack{B\cup C=A,\\B\cap C=\varnothing}} |V(B)|\,|V(C)|\right).$$
Память расходуется в объеме
$$O\left(2^n+\sum_{\varnothing\ne A\subseteq [n]} |V(A)|\right).$$
Поскольку в каждом испытании список чисел мал, такая точная динамика по множествам оказывается выполнимой.
يعطي كل تحدٍّ عددًا هدفًا \(t\) وقائمة قصيرة من الأعداد \(a_1,\dots,a_n\). يمكننا اختيار أي مجموعة جزئية غير فارغة من المواضع، واستخدام كل عدد مختار مرة واحدة فقط، ثم تركيب هذه القيم بعمليات ثنائية. تسمح التطبيقات بالجمع والضرب والطرح الموجب والقسمة التامة، ولذلك تبقى جميع القيم الوسيطة أعدادًا صحيحة موجبة.
درجة التحدي الواحد هي أصغر مجموع ممكن للأعداد المختارة التي يمكن بها الوصول إلى \(t\). وإذا لم يوجد أي تعبير صالح يحقق الهدف فالقيمة هي \(0\). أما الجواب النهائي فهو مجموع درجات التحديات الـ200 بعد وزنها بالأسس \(3^r\)، ثم أخذ النتيجة بترديد \(1005075251\).
لنكتب \([n]=\{1,\dots,n\}\). ولكل مجموعة جزئية غير فارغة \(A\subseteq [n]\) نعرّف
$$\sigma(A)=\sum_{i\in A} a_i.$$
جوهر المسألة هو معرفة جميع الأعداد الصحيحة الموجبة التي يمكن تكوينها عند استخدام المواضع الموجودة في \(A\) فقط.
كل تعبير صالح يملك عملية عليا في الجذر، ويكون فرعاه الأيسر والأيمن تعبيرين صالحين أيضًا. لذلك فإن مجموعة المواضع المستخدمة تنقسم إلى جزأين غير فارغين ومتباينين \(B\) و\(C\) بحيث
$$A=B\cup C,\qquad B\cap C=\varnothing,\qquad B\ne\varnothing,\qquad C\ne\varnothing.$$
ولهذا السبب تُبنى البرمجة الديناميكية على مجموعات المواضع لا على القيم العددية وحدها. فإذا تكرر نفس العدد في الإدخال مرتين فهذان الظهوران يظلان ورقتين مختلفتين لأن موضعيهما مختلفان.
لتكن \(V(A)\) مجموعة جميع الأعداد الصحيحة الموجبة التي يمكن الوصول إليها باستخدام المواضع في \(A\)، مع استعمال كل عنصر مختار مرة واحدة بالضبط. في حالة المجموعة الأحادية يكون
$$V(\{i\})=\{a_i\}.$$
أما إذا كانت \(A\) أكبر، فإن القيم الناتجة تأتي من دمج مجموعتين جزئيتين أصغر ومتباينتين:
$$V(A)=\bigcup_{\substack{B\cup C=A,\\B\cap C=\varnothing,\\B\ne\varnothing,\ C\ne\varnothing}} \operatorname{Combine}\bigl(V(B),V(C)\bigr).$$
ولكل زوج \(x\in V(B)\) و\(y\in V(C)\)، نضيف \(x+y\) و\(xy\)، ونضيف \(x-y\) إذا كان \(x>y\)، ونضيف \(y-x\) إذا كان \(y>x\)، ونضيف \(x/y\) إذا كان \(y\mid x\)، ونضيف \(y/x\) إذا كان \(x\mid y\).
وبما أن الطرح لا يُحفظ إلا إذا أعطى نتيجة موجبة، والقسمة لا تُحفظ إلا إذا كانت تامة، فإن جميع الحالات تحتوي على أعداد صحيحة موجبة فقط.
هذه العودية تغطي كل شجرة تعبير قانونية. حالة الأساس ذات الورقة الواحدة واضحة. وفي تعبير أكبر ننظر إلى الجذر: الفرعان يستخدمان مجموعتين غير فارغتين ومتباينتين من المواضع هما \(B\) و\(C\). وبحسب فرضية الاستقراء فإن قيم الفرعين تقع في \(V(B)\) و\(V(C)\)، ومن ثم فإن قيمة الجذر تُولَّد بواسطة قاعدة الدمج وتقع في \(V(A)\).
والاتجاه العكسي مهم بالقدر نفسه. فكل قيمة تضيفها العودية تنتج من تعبير صالح على \(B\)، وتعبير صالح على \(C\)، ثم عملية مسموحة عند الجذر. لذلك فإن كل قيمة تنتجها البرمجة الديناميكية تقابل تعبيرًا صالحًا فعلًا. وهذا الاستقراء في الاتجاهين يثبت أن \(V(A)\) هي بالضبط مجموعة القيم الممكنة.
بعد بناء جميع مجموعات الوصول، تصبح درجة التحدي الواحد
$$s=\min\left\{\sigma(A): \varnothing\ne A\subseteq [n],\ t\in V(A)\right\},$$
ومع الاتفاق على أن \(s=0\) إذا كانت المجموعة فارغة. المطلوب هنا ليس تقليل عدد العمليات ولا عدد العناصر المستخدمة، بل تقليل مجموع القيم المدخلة المختارة.
ولهذا السبب تحسب الشيفرة \(\sigma(A)\) مسبقًا لكل مجموعة جزئية. فالبرمجة الديناميكية تجيب عن سؤال: هل تصل هذه المجموعة إلى \(t\)؟ ثم تحوّل مجاميع المجموعات هذه المعلومة إلى الدرجة المطلوبة.
إذا كانت \(s_r\) هي درجة التحدي رقم \(r\)، فإن الجواب الكلي هو
$$\mathrm{Ans}=\sum_{r=1}^{200} 3^r s_r \pmod{1005075251}.$$
التحديات مستقلة رياضيًا، ولذلك تُنفَّذ برمجة المجموعات الجزئية نفسها لكل سطر على حدة. والشيء الوحيد الذي يربط بينها هو المجموع الموزون بترديد في النهاية.
خذ الهدف \(t=2\) والأعداد \((a_1,a_2,a_3)=(3,6,7)\). الحالات الأحادية هي
$$V(\{1\})=\{3\},\qquad V(\{2\})=\{6\},\qquad V(\{3\})=\{7\}.$$
وبالنسبة إلى المجموعة \(\{1,2\}\)، فإن دمج \(3\) و\(6\) يعطي
$$V(\{1,2\})\supseteq \{3+6,\ 3\cdot 6,\ 6-3,\ 6/3\}=\{9,18,3,2\}.$$
إذن الهدف \(2\) صار قابلًا للوصول بالفعل بمجموع \(\sigma(\{1,2\})=3+6=9\). أما المجموعتان الثنائيتان الأخريان فتعطيان
$$V(\{1,3\})\supseteq \{10,21,4\},\qquad V(\{2,3\})\supseteq \{13,42,1\}.$$
لا توجد مجموعة أحادية تصل إلى \(2\)، وأي حل يستخدم الأعداد الثلاثة جميعًا سيكون مجموعه \(16\)، فلا يمكن أن يتفوق على \(9\). لذلك تكون درجة هذا التحدي هي \(9\).
تستخدم تطبيقات C++ وPython وJava أقنعة البتات لتمثيل المجموعات الجزئية. أولًا تحسب مجموع كل قناع عن طريق إزالة بتٍّ مفعّل واحد وإعادة استعمال مجموع القناع الأصغر الذي سبق حسابه. وبهذا تصبح قراءة مجموع أي مجموعة جزئية عملية ذات زمن ثابت.
بعد ذلك تُبنى مجموعات القيم الممكنة بترتيب تصاعدي للأقنعة. القناع الذي يحتوي على بت واحد فقط يخزن قيمة الإدخال المقابلة له. أما القناع الأكبر فتُعدَّد له جميع المجموعات الجزئية الحقيقية غير الفارغة، ويُقرن كل منها بمتممها، ثم تُطبَّق العمليات المسموح بها على كل زوج من القيم المخزنة. وتزيل بنية المجموعة المعتمدة على التهشير التكرارات تلقائيًا، وهذا أمر أساسي لأن كثيرًا من أشجار التعبير المختلفة تعطي العدد نفسه.
وبما أن الجمع والضرب متناظران، ولأن التنفيذ يفحص أصلًا الاتجاهين في الطرح والقسمة، فيكفي التعامل مع ممثل واحد لكل تقسيم غير مرتب. وبعد اكتمال جميع الحالات تمسح الشيفرة كل الأقنعة التي تحتوي على الهدف، وتحتفظ بأصغر مجموع لمجموعة جزئية، وتعيد \(0\) إذا لم يوجد أي قناع مناسب. أما الحلقة الخارجية فتبقي القوة الحالية للعدد \(3\) بترديد \(1005075251\) وتراكم المجموع الموزون.
ليكن \(n\) عدد القيم المدخلة في تحدٍّ واحد. عدد الأقنعة غير الفارغة هو \(2^n-1\). وحساب جميع مجاميع المجموعات الجزئية مسبقًا يحتاج إلى \(O(2^n)\) زمنًا و\(O(2^n)\) ذاكرة. أما تعداد المجموعات الجزئية الحقيقية عبر جميع الأقنعة فيعطي الحد القياسي \(O(3^n)\).
الكلفة العملية المهيمنة تأتي من دمج القيم المخزنة داخل كل تقسيم، ولذلك يمكن كتابة حد أدق على الصورة
$$O\left(\sum_{A\subseteq [n]}\ \sum_{\substack{B\cup C=A,\\B\cap C=\varnothing}} |V(B)|\,|V(C)|\right).$$
أما الذاكرة فهي
$$O\left(2^n+\sum_{\varnothing\ne A\subseteq [n]} |V(A)|\right).$$
وبما أن كل تحدٍّ يحتوي على قائمة قصيرة فقط من الأعداد، فإن هذه البرمجة الديناميكية الدقيقة القائمة على المجموعات تبقى عملية.