Zusammenfassung
Gegeben Eingang k
finden Sie eine Partition von ganzen Zahlen 1
auf n
in k
Summe freie Teilmengen für die größte n
Sie innerhalb von 10 Minuten kann.
Hintergrund: Schurnummern
Eine Menge A
ist summenfrei, wenn ihre Selbstsumme A + A = { x + y | x, y in A}
keine Elemente gemeinsam hat.
Für jede positive Ganzzahl k
gibt es eine größte Ganzzahl S(k)
, sodass die Menge {1, 2, ..., S(k)}
in k
summenfreie Teilmengen aufgeteilt werden kann. Diese Nummer wird die k genannt th Schur Nummer (OEIS A045652 ).
Zum Beispiel S(2) = 4
. Wir können {1, 2, 3, 4}
als partitionieren {1, 4}, {2, 3}
, und das ist die eindeutige Partition in zwei summenfreie Teilmengen, aber wir können jetzt keinem 5
der beiden Teile eine hinzufügen .
Herausforderung
Schreiben Sie ein deterministisches Programm , das Folgendes ausführt:
- Nehmen Sie eine positive ganze Zahl
k
als Eingabe - Schreiben Sie den aktuellen Unix-Zeitstempel in stdout
- Gibt nach jeder Sequenz mit dem aktuellen Unix-Zeitstempel eine Folge von Partitionen von
1
bisn
ink
summenfreie Teilmengen zum Vergrößern ausn
.
Der Gewinner ist das Programm, das n
innerhalb von 10 Minuten nach Eingabe eine Partition für die größte Partition auf meinem Computer druckt 5
. Die Verbindungen werden zum schnellsten Zeitpunkt unterbrochen, um eine Partition für die größte zu finden n
, gemittelt über drei Läufe: Aus diesem Grund sollte die Ausgabe Zeitstempel enthalten.
Wichtige Details:
- Ich habe Ubuntu Precise. Wenn Ihre Sprache nicht unterstützt wird, kann ich sie nicht bewerten.
- Ich habe eine Intel Core2 Quad-CPU. Wenn Sie also Multithreading verwenden möchten, macht es keinen Sinn, mehr als 4 Threads zu verwenden.
- Wenn Sie möchten, dass ich bestimmte Compiler-Flags oder Implementierungen verwende, dokumentieren Sie dies in Ihrer Antwort.
- Sie dürfen Ihren Code für die Eingabe nicht als Sonderfall behandeln
5
. - Sie müssen nicht jede Verbesserung ausgeben, die Sie finden. ZB für die Eingabe können
2
Sie nur die Partition für ausgebenn = 4
. Wenn Sie jedoch in den ersten 10 Minuten nichts ausgeben, werde ich dies als bewertenn = 0
.
quelle
n=59
und das Sortieren nach der größten Anzahl zulässiger ZahlennextN
ergibt weniger alsn=64
. Das Sortieren nach der Länge der Liste nicht zugelassener Nummern (die Wiederholungen enthalten kann) führt sehr schnell zu einem elegantenn=30
Muster.Tue Nov 10 00:44:25 2015
), aber ich habe esn=92
in weniger als 2 Sekunden gesehen.ctime
übernahm,time
weil die Ausgabe schöner war, alstime
genau das war, was ich hätte auswählen sollen.n=121
. oOPython 3, 121, <0,001 s
Verbesserte Heuristik dank Martin Buttner bedeutet, dass wir nicht einmal Zufälligkeit brauchen.
Ausgabe:
Code:
Python 3, 112
Nach Summe der ersten 2 Elemente + Versatz sortieren
Ich habe die Datenstruktur von El'endia Starman kopiert, die aus einer Liste von Paaren besteht, wobei das erste Element des Paares die Elemente in diesem Bucket und das zweite die Summen dieses Bucket sind.
Ich beginne mit dem gleichen Ansatz "Verfolge, welche Summen verfügbar sind". Meine Sortierheuristik ist einfach die Summe der kleinsten zwei Elemente in einer gegebenen Liste. Ich füge auch einen kleinen zufälligen Versatz hinzu, um verschiedene Möglichkeiten auszuprobieren.
Bei jeder Iteration wird einfach die neue Nummer in die erste verfügbare Bin gelegt, ähnlich wie bei zufälliger Gier. Sobald dies fehlschlägt, wird es einfach neu gestartet.
quelle
Java 8, n =
142144Letzte Ausgabe:
Führt eine gesetzte zufällige Suche durch, die auf 4 Threads verteilt ist. Wenn keine passende Partition gefunden wird,
n
wird versucht, Speicherplatz für jeweilsn
eine Partition freizugeben, indem so viel wie möglich auf die anderen Partitionen kopiert wird.Bearbeiten: Der Algorithmus zum Freigeben von Speicherplatz wurde überarbeitet
n
. Außerdem wurde die Möglichkeit hinzugefügt, zu einer vorherigen Auswahl zurückzukehren und erneut eine Auswahl zu treffen.Hinweis: Die Ausgabe ist nicht streng deterministisch, da mehrere Threads beteiligt sind und die besten Threads, die bisher
n
gefunden wurden, möglicherweise in unübersichtlicher Reihenfolge aktualisiert werden. Der Endwert von 144 ist jedoch deterministisch und wird ziemlich schnell erreicht: 30 Sekunden auf meinem Computer.Code ist:
quelle
C, Random Greedy, n = 91
Nur um eine Basislösung bereitzustellen, wird diese wiederholt
n
, wobei die Klassen und ihre Summen verfolgt undn
einer zufälligen Klasse hinzugefügt werden, in der sie noch nicht als Summe angezeigt wird. Es wirdn
in allenk
Summen einmal beendet. Wenn das Ergebnisn
besser war als alle vorherigen Versuche, wird es an STDOUT ausgegeben.Die Eingabe
k
erfolgt über ein Befehlszeilenargument. Das maximal möglichek
ist derzeit auf 10 fest codiert, da ich zu faul war, dynamische Speicherzuweisung hinzuzufügen, aber das konnte leicht behoben werden.Ich denke, ich könnte jetzt auf die Jagd nach einem besseren Samen gehen, aber diese Antwort ist wahrscheinlich sowieso nicht besonders wettbewerbsfähig, also meh.
Hier ist die Partition für
n = 91
:Und zum Schluss hier der Code:
quelle
n=91
, gefunden in 138 Sekunden. Wenn es nötig ist, um das Unentschieden zu beenden, stelle ich eine Pause ein, um große Fehler aufgrund unterschiedlicher CPU-Auslastung zu vermeiden.C ++, 135
Hängt das nächste n an eine zufällig ausgewählte Untermenge an. Wenn dies nicht möglich ist, werden Zufallszahlen aus Teilmengen entfernt und an andere angehängt, in der Hoffnung, dass dadurch irgendwo n angehängt werden kann.
Ich habe das in awk als Prototyp erstellt und es, da es vielversprechend aussah, in C ++ übersetzt, um es zu beschleunigen. Die Verwendung von a
std::set
sollte die Geschwindigkeit sogar noch erhöhen.Ausgabe für n = 135 (nach ca. 230 Sekunden auf meiner [alten] Maschine)
Ich habe die Gültigkeit nicht überprüft, aber es sollte in Ordnung sein.
quelle
Python 3, zufällig gierig, n = 61
Letzte Ausgabe:
Dies verwendet effektiv den gleichen Algorithmus wie Martin Büttner , aber ich habe ihn unabhängig entwickelt.
Es gibt
k
Behälter, in denen sowohl die Zahlen als auch die Zahlen enthalten sind, die nicht mehr verwendet werden können. Bei jeder Tiefe in der Iteration (im Grunde handelt es sich um eine Tiefensuche) wird die Sortierung der Behälter gemischt, und die nächste Zahl (nextN
) wird (nacheinander) in die Behälter gelegt, die sie aufnehmen können, und geht dann einen Schritt tiefer. Wenn es keine gibt, kehrt es zurück und sichert einen Schritt.quelle
Python, n = 31
Ok, es ist offensichtlich kein Gewinner, aber ich hatte das Gefühl, dass es trotzdem hierher gehört. Ich habe mir erlaubt, keine Zeitstempel einzuschließen, da diese sofort beendet werden und es sich nicht um einen echten Konkurrenten handelt.
Beachten Sie zunächst, dass die Summe von zwei ungeraden Zahlen gerade ist, sodass wir alle ungeraden Zahlen im ersten Block ausgeben können. Dann, da alle verbleibenden Zahlen gerade sind, können wir sie durch 2 teilen. Noch einmal können wir alle resultierenden ungeraden Zahlen in den zweiten Block werfen (nachdem wir sie erneut mit 2 multipliziert haben), die verbleibenden Zahlen durch 2 teilen (dh Wirf die ungeraden Zahlen in den dritten Block (nachdem du sie mit 4 multipliziert hast) und so weiter. Oder, um es in Worte zu fassen, wir setzen alle Zahlen, deren niedrigstwertige Menge bit ist das erste Bit im ersten Block, alle Zahlen, deren niedrigstwertiges gesetztes Bit das zweite Bit im zweiten Block ist, und so weiter ...
Für k Blöcke, führen wir in Schwierigkeiten , wenn wir erreichen n = 2 k , da das niedrigstwertige Bit Satz von n ist
der ( k + 1) -te Bit, das zu jedem Block nicht stimmt. Mit anderen Worten, dieses Schema funktioniert bis
zu n = 2 k - 1. Während also für k = 5 nur ein mageres n = 31 erhalten wird , wächst diese Zahl exponentiell mit k . Es stellt auch fest, dass S ( k ) ≥ 2 k - 1 ist (aber wir können tatsächlich leicht eine bessere Untergrenze als diese finden.)
Als Referenz ist hier das Ergebnis für k = 5:
quelle
[1], [2,3], [4,5,6,7], ...
, was wahrscheinlich einfacher ist, nur mit umgekehrter Bit- und Blockreihenfolge. Es ist leicht zu sehen, wie dieser erweitert werden kann.