Diese Abfrage ist teilweise eine Algorithmusabfrage, teilweise eine Optimierungsabfrage und teilweise einfach eine schnellste Codeabfrage.
Eine zyklische Matrix ist durch ihre erste Zeile vollständig spezifiziert r
. Die verbleibenden Zeilen sind jeweils zyklische Permutationen der Zeile r
mit einem Versatz gleich dem Zeilenindex. Wir werden zyklische Matrizen zulassen, die nicht quadratisch sind, so dass ihnen einfach einige ihrer letzten Zeilen fehlen. Wir gehen jedoch immer davon aus, dass die Anzahl der Zeilen nicht größer als die Anzahl der Spalten ist. Betrachten Sie beispielsweise die folgende zyklische 3 × 5-Matrix.
10111
11011
11101
Wir sagen, eine Matrix hat die Eigenschaft X, wenn sie zwei nicht leere Sätze von Spalten mit nicht identischen Indizes enthält, die dieselbe (Vektor-) Summe haben. Die Vektorsumme zweier Spalten ist einfach eine elementweise Summierung der beiden Spalten. Das ist die Summe von zwei Spalten, die x
Elemente enthalten. Jede Spalte enthält x
Elemente.
Die obige Matrix hat trivialerweise die Eigenschaft X, da die erste und die letzte Spalte identisch sind. Die Identitätsmatrix hat niemals die Eigenschaft X.
Wenn wir nur die letzte Spalte der obigen Matrix entfernen, erhalten wir ein Beispiel, das keine Eigenschaft X hat und eine Punktzahl von 4/3 ergibt.
1011
1101
1110
Die Aufgabe
Die Aufgabe besteht darin, Code zu schreiben, um die zyklische Matrix mit der höchsten Punktzahl zu finden, deren Einträge alle 0 oder 1 sind und die keine Eigenschaft X hat.
Ergebnis
Ihre Punktzahl ergibt sich aus der Anzahl der Spalten geteilt durch die Anzahl der Zeilen in Ihrer Matrix mit der besten Punktzahl.
Kabelbinder
Wenn zwei Antworten die gleiche Punktzahl haben, gewinnt die zuerst eingereichte.
In dem (sehr) unwahrscheinlichen Fall, dass jemand eine Methode findet, um unbegrenzte Punktzahlen zu erhalten, wird der erste gültige Beweis für eine solche Lösung akzeptiert. In dem noch unwahrscheinlicheren Fall, dass Sie einen Beweis für die Optimalität einer endlichen Matrix finden, werde ich natürlich auch den Gewinn vergeben.
Hinweis
Es ist nicht schwer, eine Punktzahl von 12/8 zu erreichen.
Sprachen und Bibliotheken
Sie können jede Sprache verwenden, die über einen frei verfügbaren Compiler / Interpreter / etc. Verfügt. für Linux und alle Bibliotheken, die auch für Linux frei verfügbar sind.
Führende Einträge
- 36/19 von Peter Taylor (Java)
- 32/17 von Suboptimus Prime (C #)
- 21/12 von justhalf (Python 2)
quelle
01
die Eigenschaft X, da die Menge der ersten Spalte dieselbe Vektorsumme wie die leere Menge hat. Vielleicht meinten Sie nicht leere Spaltengruppen? Ich denke, es ist sauberer, es nicht zu ändern.01
Eigentum X hat:(1) = (0) + (1)
. Wenn Sie dies ausschließen möchten, sollten Sie sagen, dass die beiden Spaltengruppen nicht verbunden sein dürfen.2^m
Spaltenkombinationen dazu, die Eigenschaft X zu überprüfen. Wenn wir irgendwie ein "Treffen in der Mitte" -Schema entwickeln könnten (siehe das "Teilmengen" -Problem), könnte dies wahrscheinlich dazu führen, dassm * 2^(m/2)
...Antworten:
16/9 20/11 22/12 28/15 30/16 32/17 34/1836/19 (Java)Dies nutzt eine Reihe von Ideen, um den Suchraum und die Kosten zu reduzieren. Weitere Informationen zu früheren Versionen des Codes finden Sie im Revisionsverlauf.
0
und1
), und arbeite sie aus. Ich verwende den in A Gray-Code beschriebenen Algorithmus für Halsketten mit fester Dichte und Lyndon-Wörter in konstanter Amortisationszeit , Sawada und Williams, Theoretical Computer Science 502 (2013): 46-54.BigInteger
, um einen genauen Test zu geben. Ich erhalte eine signifikante Geschwindigkeitsverbesserung, bei der das Risiko von falschen Negativen besteht, indem ich modulo mit einer großen Primzahl bediene und alles in Primitiven halte. Die von mir gewählte Primzahl ist die größte, die kleiner als 2 57 ist , da dies das Multiplizieren mit der Basis meiner fiktiven Vektordarstellung ohne Überlaufen ermöglicht.{-1,0,1}^m
seine Negation hat, es auch{-1,0,1}^m
nur notwendig ist, eines der beiden zu speichern.2n/(n+1)
, beschleunige ich die Dinge, indem ich das nur teste.Der erste gefunden ist
und das ist der einzige Treffer in 15 Stunden.
Kleinere Gewinner:
quelle
n
eher als verwendenrows
, obwohl es in dem Sinne ausfallsicher ist, dass gültige Lösungen verworfen werden, anstatt ungültige zu akzeptieren. Es hat auch keinen Einfluss auf die Ergebnisse.Python 2 - 21/12
In dem Prozess zu beweisen, dass
2-(3/n)
es für jeden immer ein gibtn
Inspiriert von dieser Frage benutzte ich De Bruijn Sequence , um die möglichen Matrizen zu erzwingen. Und nach brachialer Anstrengung
n=6,7,8,9,10
fand ich ein Muster, dessen höchste Lösung immer die Form von ist(n, 2n-3)
.Deshalb habe ich eine andere Methode entwickelt, um nur diese Form der Matrix zu erzwingen und Multiprocessing zu verwenden, um die Dinge zu beschleunigen, da diese Aufgabe hochgradig verteilbar ist. In 16-Core-Ubuntu kann es
n=12
in etwa 4 Minuten eine Lösung finden :Der Großteil der Berechnung geht zur Überprüfung der Eigenschaft X, für die alle Teilmengen überprüft werden müssen (es gibt
2^(2n-3)
Teilmengen).Beachten Sie, dass ich die erste Reihe nach links drehe, nicht wie in der Frage nach rechts. Dies ist jedoch äquivalent, da Sie die gesamte Matrix einfach umkehren können. =)
Der Code:
Alte Antwort als Referenz
Die bisher optimale Lösung (
n=10
):Für
n=7
:Eine Lösung mit der Form wie von OP (
n=8
) beschrieben:Aber eine bessere (
n=8
):Es fand auch eine andere optimale Lösung bei
n=9
:Der Code lautet wie folgt. Es ist nur rohe Gewalt, aber zumindest kann es etwas Besseres finden als OPs Behauptung =)
quelle
n >= 31
, was impliziert, dass ich bis zu2^(2n-3) = 2^59
Kombinationen von 31-dimensionalen Vektoren prüfen müsste . Wird in unserem Leben nicht zu Ende sein = Dn*(2n-3)
24/13 26/14 28/15 30/1632/17 (C #)Bearbeiten: Veraltete Informationen aus meiner Antwort gelöscht. Ich verwende größtenteils den gleichen Algorithmus wie Peter Taylor ( Bearbeiten: Es sieht so aus, als würde er jetzt einen besseren Algorithmus verwenden), obwohl ich einige meiner eigenen Optimierungen hinzugefügt habe:
HasPropertyXFast
Funktion hinzugefügt , mit der schnell überprüft wird, ob kleine Mengen mit gleichen Summen vorhanden sind, bevor der Ansatz "Treffen in der Mitte" verwendet wird.HasPropertyXFast
Funktion beginne ich mit dem Überprüfen von Spaltensätzen mit 1 Spalte, dann mit 2, 3 usw. Die Funktion kehrt zurück, sobald die erste Kollision von Spaltensummen gefunden wurde. In der Praxis bedeutet dies, dass ich normalerweise nur ein paar Hundert oder Tausende von Spaltensätzen anstelle von Millionen überprüfen muss.long
Variablen, um ganze Spalten und ihre Vektorsummen zu speichern und zu vergleichen. Dieser Ansatz ist mindestens eine Größenordnung schneller als der Vergleich von Spalten als Arrays.long
Datentyp und für meine Verwendungsmuster optimiert ist .Programmausgabe:
Code:
Konfigurationsdatei:
quelle
ulong
den Shift-Wrap verwenden und nicht verwendenBigInteger
.GetSumOfColumns
eine zusätzliche Schleife hinzufügen, von der ich erwarten würde, dass sie mehr als den Faktor 2 kostet. Die Maskensortierung klingt interessant: Vielleicht könnten Sie das die Antwort editieren, um ein bisschen darüber zu reden? (Und irgendwann werde ich mit einer alternativen Methode experimentieren, um den frühen Abbruch durchzuführen: Der Grund, warum ich das nicht kann, ist, dass HashSet keine gleichzeitige Iteration und Modifikation unterstützt, aber ich habe Ideen, um die Notwendigkeit eines Iterators zu vermeiden.) .