Hintergrund
Die Umordnungsungleichung ist eine Ungleichung, die auf der Neuanordnung von Zahlen basiert. Wenn ich zwei Listen von Zahlen gleicher Länge habe, x 0 , x 1 , x 2 ... x n-1 und y 0 , y 1 , y 2 ... y n-1 gleicher Länge, wobei I. Ich darf die Zahlen in der Liste neu anordnen. Eine Möglichkeit, die Summe x 0 y 0 + x 1 y 1 + x 2 y 2 + ... + x n-1 y n-1 zu maximieren, besteht darin, die 2 Listen zu sortieren nicht abnehmende Reihenfolge.
Lesen Sie hier den Wikipedia- Artikel.
Aufgabe
Sie würden ein Programm schreiben, das Eingaben von STDIN entgegennimmt, oder eine Funktion, die 2 Arrays (oder verwandte Container) von Zahlen (die gleich lang sind) akzeptiert.
Angenommen, Sie schreiben eine Funktion, die zwei Arrays (a und b) akzeptiert, werden Sie die Anzahl der Möglichkeiten finden, wie Sie die Zahlen im zweiten Array (b) neu anordnen können, um Folgendes zu maximieren:
a[0]*b[0]+a[1]*b[1]+a[2]*b[2]+...+a[n-1]*b[n-1]
In diesem Fall, wenn das Array b [1 0 , 2 1 , 2 2 , 3 3 , 3 4 ] ist (Indizes zur Klarheit),
[1 0 , 2 1 , 2 2 , 3 3 , 3 4 ],
[1 0 , 2 1 , 2 2 , 3 4 , 3 3 ] (tauschen Sie die beiden 3er aus)
[1 0 , 2 2 , 2 1 , 3 3 , 3 4 ] (tauschen Sie die beiden 2er aus)
[1 0 , 2 2 , 2 1 , 3 4 , 3 3 ] (Tauschen Sie die beiden 3er und die beiden 2er)
gelten als unterschiedliche Regelungen. Das ursprüngliche Array selbst zählt ebenfalls als mögliche Umlagerung, wenn es auch die Summe maximiert.
Bei der STDIN-Eingabe können Sie davon ausgehen, dass die Länge der Arrays vor den Arrays angegeben wird (bitte geben Sie an, dass Sie sie verwenden), oder dass die Arrays in verschiedenen Zeilen bereitgestellt werden (bitte auch angeben).
Hier sind die 4 möglichen Eingaben (der Einfachheit halber):
5 1 1 2 2 2 1 2 2 3 3 (length before arrays)
1 1 2 2 2 1 2 2 3 3 (the 2 arrays, concatenated)
1 1 2 2 2
1 2 2 3 3 (the 2 arrays on different lines)
5
1 1 2 2 2
1 2 2 3 3 (length before arrays and the 2 arrays on different lines)
Für die Ausgabe können Sie die Antwort zurückgeben (wenn Sie eine Funktion schreiben) oder die Antwort an STDOUT drucken. Sie können den Antwort-Mod 10 9 +7 (von 0 bis 10 9 + 6 ) ausgeben, wenn dies bequemer ist.
Testfälle (und Erklärung):
[1 1 2 2 2] [1 2 2 3 3] => 24
Die ersten 2 Einträge müssen 1 und 2 sein. Die letzten 3 Einträge sind 2, 3 und 3. Es gibt zwei Möglichkeiten, die 2 zwischen den ersten 2 Einträgen und den letzten 2 Einträgen anzuordnen. Unter den ersten beiden Einträgen gibt es zwei Möglichkeiten, sie neu anzuordnen. Unter den letzten beiden Einträgen gibt es 6 Möglichkeiten, sie neu anzuordnen.
[1 2 3 4 5] [6 7 8 9 10] => 1
Es gibt nur einen Weg, nämlich die in den Arrays angegebene Anordnung.
[1 1 ... 1 1] [1 1 ... 1 1] (10000 numbers) => 10000! or 531950728
Jede mögliche Permutation des zweiten Arrays ist gültig.
Dennis 'Testfall: Pastebin => 583159312 (mod 1000000007)
Wertung:
Dies ist Code-Golf, also gewinnt die kürzeste Antwort.
Im Falle eines Unentschieden werden die Unentschieden zum Zeitpunkt der Einreichung unterbrochen, was die frühere Einreichung begünstigt.
Beachten:
Die Container sind möglicherweise unsortiert.
Die ganzen Zahlen in den Containern können Null oder negativ sein.
Das Programm muss schnell genug (höchstens eine Stunde) für Arrays mit bescheidener Größe (ca. 10000 Länge) ausgeführt werden.
Inspiriert von dieser Frage zu Mathematics Stack Exchange.
quelle
[. . .]
PLZ antwortenAntworten:
CJam,
3026 BytesProbieren Sie es online im CJam-Interpreter aus .
Es vervollständigt diesen Testfall in weniger als einer Sekunde:
Das Ausführen im Online-Interpreter sollte weniger als 10 Sekunden dauern.
Algorithmus
Das Ergebnis hängt nicht von der Reihenfolge von A ab , daher können wir davon ausgehen, dass es sortiert ist. Dies bedeutet, dass B auch sortiert werden muss, um das maximale Punktprodukt zu erreichen.
Wenn nun r 1 ,… r n die Länge der Läufe des sortierten A sind , gibt es ∏r k ! verschiedene Umlagerungen der Elemente von A , die immer noch zu aufsteigender Reihenfolge führen.
Wenn s 1 ,… s n die Länge der Läufe des sortierten B sind , gibt es ebenfalls ∏s k ! verschiedene Umlagerungen der Elemente von B , die immer noch zu aufsteigender Reihenfolge führen.
Dies zählt jedoch alle Paarungen mehrmals. Wenn wir die Paare der entsprechenden Elemente von sortiertem A und sortiertem B nehmen und t 1 definieren ,… t n als die Länge der Läufe des resultierenden Arrays, ∏t k ! ist der oben genannte Multiplikator.
Somit ist das gewünschte Ergebnis (∏r k !) × (∏s k !) ÷ (∏t k !) .
Code
quelle
Pyth,
2928 BytesProbieren Sie es online im Pyth Compiler aus .
Algorithmus
Das Ergebnis hängt nicht von der Reihenfolge von A ab , daher können wir davon ausgehen, dass es sortiert ist. Dies bedeutet, dass B auch sortiert werden muss, um das maximale Punktprodukt zu erreichen.
Wenn nun r 1 ,… r n die Länge der Läufe des sortierten A sind , gibt es ∏r k ! verschiedene Umlagerungen der Elemente von A , die immer noch zu aufsteigender Reihenfolge führen.
Wenn s 1 ,… s n die Länge der Läufe des sortierten B sind , gibt es ebenfalls ∏s k ! verschiedene Umlagerungen der Elemente von B , die immer noch zu aufsteigender Reihenfolge führen.
Dies zählt jedoch alle Paarungen mehrmals. Wenn wir die Paare der entsprechenden Elemente von sortiertem A und sortiertem B nehmen und t 1 definieren ,… t n als die Länge der Läufe des resultierenden Arrays, ∏t k ! ist der oben genannte Multiplikator.
Somit ist das gewünschte Ergebnis (∏r k !) × (∏s k !) ÷ (∏t k !) .
Code
Nachprüfung
Ich habe pseudozufällig 100 Testfälle der Länge 6 generiert, die ich mit dem obigen Code und diesem Brute-Force-Ansatz gelöst habe:
Dies waren die Ergebnisse:
Um zu überprüfen, ob meine Einreichung die Geschwindigkeitsanforderungen erfüllt, habe ich sie mit diesem Testfall ausgeführt .
quelle
Matlab, 230 Bytes
Ausführung
Dennis 'Testfall:
Ausgänge:
quelle
C ++, 503 Bytes
(nur zum Spaß, eine Sprache ohne Golf)
Ungolfed Version:
quelle