Ermitteln der Größe der kleinsten Teilmenge mit GCD = 1

10

Dies ist ein Problem aus der Übungsstunde des polnischen Collegiate Programming Contest 2012 . Obwohl ich die Lösungen für den Hauptwettbewerb finden konnte, kann ich nirgendwo eine Lösung für dieses Problem finden.

Das Problem ist: Wenn eine Menge von verschiedenen positiven ganzen Zahlen nicht größer als 10 9 ist , finden Sie die Größe m der kleinsten Teilmenge, die keinen anderen gemeinsamen Teiler als 1 hat. N ist höchstens 500, und es kann angenommen werden, dass eine Lösung existiert.N109mN

Ich konnte zeigen, dass . Meine Argumentation lautet: Angenommen, es gibt eine minimale Teilmenge S der Größe | S | = 10 , mit gcd = 1. Dann müssen alle 9-Teilmengen von S gcd> 1 haben. Es gibt genau 10 solcher Teilmengen, und ihre gcds müssen paarweise koprime sein. Diese gcds seien 1 < g 1 < g 2 < . . . < g 10 , wobei gcd ( g i , g j ) = 1 für i ≠ istm9S|S|=10S1<g1<g2<...<g10gcd(gi,gj)=1 . Danndie maximale Anzahl in S ist , g 2 g 3 . . . g 10 . Aber g 2 g 3 . . . g 103 × 5 × 7 × 11 × . . . × 29 = 3234846615 > 10 9 , ein Widerspruch.ijSg2g3...g10g2g3...g103×5×7×11×...×29=3234846615>109

Trotzdem ist eine unkomplizierte rohe Gewalt immer noch zu langsam. Hat jemand andere Ideen?

Wakaka
quelle
Warum kann ? g2=2
vonbrand
. g 1 kann nicht 1 sein, da 9-Teilmengen keineg2>g12g1
gcd

Antworten:

1

Dieses Problem entspricht dem folgenden und es ist trivial, die Reduktion in beide Richtungen zu konstruieren.

Bestimmen Sie anhand einer Liste von Bitvektoren die minimale Anzahl von ihnen, sodass andalle den Bit-Vektor ergeben. ( )0()

Dann zeigen wir, dass sich die Set-Abdeckung auf reduziert . Mit Satzabdeckung meine ich, wenn eine Liste von Sätzen S 1 , , S k gegeben ist, die Mindestanzahl von Sätzen zu finden, die ihre Vereinigung abdecken.()S1,,Sk

Wir um die Elemente in den Sätzen zu . Sei f ( S ) = ( 1 - χ a 1 ( S ) , , 1 - χ a n ( S ) ) , wobei χ x ( S ) = 1 ist, wenn x S , sonst 0. Beachten Sie, dass diese Funktion eine Bijektion ist und daher eine Umkehrung aufweist.a1,,anf(S)=(1χa1(S),,1χan(S))χx(S)=1xS

Wenn wir nun nach f ( S 1 ) , , f ( S k ) lösen und die Lösungen { f ( S b 1 ) , , f ( S b m ) } sind , dann { f - 1 ( S b 1 ) , , f - 1 ( S b m ) }()f(S1),,f(Sk){f(Sb1),,f(Sbm)}{f1(Sb1),,f1(Sbm)} ist die Lösung, um Deckung zu setzen.

Daher würde ich denken, dass dieses Problem die Fähigkeit testet, den Suchraum zu beschneiden.

Chao Xu
quelle
Wie finden Sie die minimale Scheitelpunktabdeckung?
Yuval Filmus
oh nvm diese Lösung, es ist stattdessen Deckung gesetzt.
Chao Xu
1
Das stimmt, aber ich denke, wir können vielleicht bestimmte Eigenschaften dieses Sonderfalls ausnutzen. In diesem Fall sind die Mengen beispielsweise alle sehr groß und haben eine Größe von nicht weniger als . Wenn die Zahlen in den Sets alle klein sind, sind ihre Größen sogar noch größer. Außerdem finden wir definitiv 9 Sets, die alles abdecken. Wie schlagen Sie vor, den Suchraum zu beschneiden? n9
Wakaka
Ich sehe nicht, wie das Problem (*) dem in der Frage angegebenen entspricht. Zum einen verspricht das in der Frage angegebene Problem, dass alle ganzen Zahlen , was einer Garantie für die Gewichtung der Bitvektoren entspricht, die in Problem (*) nicht vorkommt. 109
DW
1

Es ist möglich, dies relativ effizient zu lösen, indem alle paarweisen GCDs berechnet, Duplikate entfernt und dann rekursiv behandelt werden. Es ist der Vorgang des Entfernens von Duplikaten, bevor Sie eine Wiederholung durchführen, die es effizient macht.

Ich werde den Algorithmus im Folgenden näher erläutern , aber zuerst, hilft es , einen binären Operator zu definieren . Wenn S , T Mengen positiver Ganzzahlen sind, definieren SieS,T

ST={gcd(s,t):sS,tT}.

Beachten Sie, dass und | S T | 10 9 (in Ihrem Problem); Typischerweise ist S T sogar kleiner als eine dieser Grenzen vermuten lässt, was dazu beiträgt, den Algorithmus effizienter zu machen. Beachten Sie auch, dass wir S T mit | berechnen können S | × | T | GCD-Operationen durch einfache Aufzählung.|ST||S|×|T||ST|109STST|S|×|T|

Mit dieser Notation ist hier der Algorithmus. Sei der eingegebene Satz von Zahlen. Berechnen Sie S 2 = S 1S 1 , dann S 3 = S 1S 2 , dann S 4 = S 1S 3 und so weiter. Finden Sie das kleinste k so, dass 1 S k aber 1 S k - 1 ist . Dann wissen Sie, dass die Größe der kleinsten solchen Teilmenge k istS1S2=S1S1S3=S1S2S4=S1S3k1Sk1Sk1k. Wenn Sie auch ein konkretes Beispiel für eine solche Teilmenge ausgeben möchten, können Sie eine solche Menge leicht rekonstruieren, indem Sie Rückzeiger beibehalten.

Dies ist relativ effizient, da keiner der Zwischensätze eine Größe über (tatsächlich wird ihre Größe wahrscheinlich viel kleiner als diese sein) und die Laufzeit etwa 500 × ( | S 1 | + | S 2) erfordert | + ) gcd-Operationen.109500×(|S1|+|S2|+)

Hier ist eine Optimierung, die die Effizienz noch weiter verbessern könnte. Grundsätzlich können Sie iteriertes Verdoppeln verwenden, um das kleinste so zu finden, dass 1 S k . Insbesondere verfolgen wir für jedes Element x S i die kleinste Teilmenge von S 1, deren gcd x ist und deren Größe i ist . (Wenn Sie Duplikate entfernen, lösen Sie Bindungen zugunsten der Teilmenge auf, die kleiner ist.) Anstatt nun die Folge von neun Mengen S 1 , S 2 , S 3 , S 4 , zu berechnen ,k1SkxSiS1xi , wir stattdessen die Sequenz der fünf Sätze berechnen S 1 , S 2 , S 4 , S 8 , S 9 , durch Berechnen von S 2 = S 1S 1 , dann S 4 = S 2S 2 , dann S 8 = S 4S 4 , dann S 9 = S 1 × S 8S1,S2,S3,S4,,S9S1,S2,S4,S8,S9S2=S1S1S4=S2S2S8=S4S4S9=S1×S8. Finden Sie dabei das erste so dass 1 S k . Sobald Sie k so gefunden haben, dass 1 S k ist , können Sie sofort aufhören: Sie können die kleinste Teilmenge finden, deren gcd 1 ist, indem Sie sich die mit 1 verknüpfte Teilmenge ansehen . Sie können also anhalten, sobald Sie eine Menge S k erreichen, so dass 1 S k , wodurch Sie vorzeitig anhalten können, wenn Sie eine kleinere Teilmenge finden.k[1,2,4,8,9]1Skk1Sk11Sk1Sk

xSkSi,Sjx

[1,2,4,8,9]Sk

Si

DW
quelle
Ich glaube, eine binäre Suche ist nicht notwendig. Sie können die Elementanzahl mit jedem gcd speichern und bei jeder Verdoppelung auf die minimale Paarsumme setzen.
KWillets
Toller Punkt, @KWillets! Vielen Dank für diese schöne Idee! Ich habe es in meine Antwort aufgenommen.
DW
0

109

ai=p1ni1p2ni2Pi
PiainijP
vonbrand
quelle
(1,1)(1,0)(1,0)(0,0)
1
p3401 pi500 PiAppBAp|ApB|1NP-complete, aber es könnte einige Implementierungen geben, die für diese Größe schnell genug sind.
Polkjh
Könnten Sie mich auf einige Implementierungen verweisen, die funktionieren könnten? Bisher kann ich nur Approximationsalgorithmen finden. Vielen Dank!
Wakaka
In diesem Umfragepapier werden sowohl ungefähre als auch genaue Lösungen untersucht. Wenn Sie auf einen Kommentar antworten, fügen Sie dem Kommentar bitte @ name-of-person hinzu. Es wird eine Benachrichtigung an diese Person gesendet. Andernfalls erfahren sie möglicherweise nie etwas über Ihren Kommentar.
Polkjh
-1

Wenn Sie eine Teilmenge mit gcd (S) = 1 finden können, kann ich immer redundante Elemente aus der Teilmenge entfernen, bis nur noch 2 Elemente übrig sind, die gcd (S) = 1 haben. Daher kann ich behaupten, dass entweder die kleinste Die Teilmenge enthält 2 Elemente oder ist nicht vorhanden.

Jetzt verwenden wir die Rekursion, um dieses Problem zu lösen. Teilen wir das Zahlenfeld in zwei Teile, einen mit n-1 Elementen und einen mit 1 Element (letztes Element). Entweder befinden sich die 2 Zahlen in den ersten n-1 Elementen oder ein Element aus dem ersten Teil, gepaart mit dem letzten Element. Daher können wir dieses Problem in lösen

T (n) = T (n-1) + O (n) Zeit. was bedeutet, T (n) = O (n ^ 2).

Pratik
quelle
4
gcd(6,10,15)=1