Vertausche die Boxen in minimalen Zügen

Question

Dies ist eine Frage aus einem Programmierwettbewerb (der bereits beendet ist). Ich hatte Schwierigkeiten, dieses Problem zu lösen, konnte jedoch keine gesunde Methode finden, um dies zu tun.

Die Frage lautet:

Das IIIT Allahabad feiert sein jährliches Techno-Cultural Fiesta Effervescence MM12 vom 1. bis 5. Oktober. Der Koch hat zugestimmt, Bonbons für diese Festtagssaison zu liefern. Der Koch hat N Schachteln Bonbons vorbereitet, nummeriert von 1 bis N (jede Zahl kommt genau einmal vor ). Der Koch legt großen Wert auf die Anordnung der Schachteln. Er möchte, dass die Schachteln in einer bestimmten Reihenfolge angeordnet sind, aber leider ist der Koch beschäftigt. Er hat Sie gebeten, die Schachteln für ihn neu anzuordnen. Angesichts der aktuellen Reihenfolge der Schachteln müssen Sie die Schachteln in der angegebenen Reihenfolge neu anordnen. Es gibt jedoch eine Einschränkung. Sie können nur zwei benachbarte Schachteln vertauschen, um die erforderliche Reihenfolge zu erreichen. Geben Sie die minimale Anzahl solcher benachbarter Vertauschungen aus.

Eingabe

Die erste Zeile der Eingabe enthält eine einzelne Ganzzahl T, die Anzahl der Testfälle. Jeder Testfall enthält 3 Zeilen, die erste Zeile enthält eine einzige Ganzzahl N, die Anzahl der Schachteln. Die nächsten 2 Zeilen enthalten jeweils N Zahlen, wobei die erste Zeile die gegebene Reihenfolge der Schachteln und die zweite Zeile die erforderliche Reihenfolge darstellt.

Ausgabe

Geben Sie für jeden Testfall eine einzelne Ganzzahl 'K' aus, die minimale Anzahl der benötigten benachbarten Vertauschungen. Einschränkungen:

1<=T<=10
1<=N<=10^5

Beispiel

Eingabe:

4

3
1 2 3
3 1 2

3
1 2 3
3 2 1

5
3 4 5 2 1  
4 1 5 2 3  

4
1 2 3 4
2 3 4 1

Ausgabe:

2
3
6
3

Ich war fast ratlos über diese Frage. Kann mir bitte jemand die Logik hinter der Frage erklären!!

Answer 1

Das Problem ist ein ziemlich "klassisches" Problem des Wettbewerbsprogrammierens, bei dem Inversionen in einem Array gezählt werden. Eine Inversion wird definiert als ein Paar (i, j), bei dem i < j und A[i] > A[j] ist.

Die allgemeinste Version, bei der ein Array beliebiger Zahlen gegeben ist und Sie aufgefordert werden, die Anzahl der Inversionen zu zählen, hat eine O(n log n)-Lösung durch Modifikation des Merge-Sort-Algorithmus.

Eine eingeschränktere Version, bei der eine vernünftige Obergrenze für den maximalen Wert im Array angegeben ist (beachten Sie, dass dies NICHT die Länge des Arrays ist), kann in O(n log m) gelöst werden, wobei m der maximale Wert im Array ist. Der Hauptpunkt hier ist, dass der Umfang des Codes, den Sie schreiben müssen, viel geringer ist als der bei der Merge-Sort-Methode.

Das im Fragebogen behandelte Problem besteht darin, die Anzahl der Vertauschungen zu zählen, um das Array in eine bestimmte Reihenfolge zu bringen, was als Zählen der Vertauschungen zum Sortieren des Arrays in aufsteigender Reihenfolge umgewandelt werden kann und letztendlich darauf hinausläuft, die Anzahl der Inversionen zu zählen. Warum die Anzahl der Inversionen? Weil Sie höchstens eine Inversion pro Vertauschen von 2 benachbarten Elementen auflösen können.

Sie müssen ein Array erstellen, das die aktuelle Position der Kästchen im Vergleich zu den endgültigen Einstellungen beschreibt. Dann kann der Algorithmus beginnen:

1. Erstellen Sie einen Fenwick-Baum (Binary Indexed Tree) mit der Länge m (m = n für das Problem im Fragebogen).

   Wir werden den Fenwick-Baum verwenden, um uns dabei zu helfen, die Anzahl der vorangehenden Elemente im Array zu zählen, die größer als das aktuelle Element sind. Wir werden die Häufigkeit der Zahlen, auf die wir bisher gestoßen sind, halten und die Fenwick-Baum-Bereichssummenabfrage verwenden, um die Anzahl der Elemente kleiner als das aktuelle Element zu erhalten (und die Anzahl der Elemente, die größer als das aktuelle Element sind, abzuleiten).

2. Schleifen Sie durch die n Elemente des Arrays:

   • Verwenden Sie die Bereichssummenabfrage, um zu zählen, wie viele Zahlen kleiner als die aktuelle Zahl erfasst wurden.
   • Verwenden Sie die obigen Informationen, um herauszufinden, wie viele Zahlen größer als die aktuelle Zahl sind. Fügen Sie dies zur Inversionsanzahl hinzu. Achten Sie darauf, das betrachtete Element nicht einzuschließen. (*)
   • Erhöhen Sie + 1 den Fenwick-Baum am Wert des Elements.

3. Die in Schritt (*) akkumulierte Inversionsanzahl.

^ Der Fragebogen besagt eindeutig, dass die Elemente eindeutig sind, daher wird der obige Algorithmus funktionieren. Ich bin mir nur nicht sicher, ob Eindeutigkeit eine notwendige Bedingung ist oder ob der Algorithmus modifiziert werden kann, um den Fall zu berücksichtigen, in dem sich wiederholende Elemente vorhanden sind.

Answer 2

Reduzieren Sie die Quellliste auf eine Permutation von (1,2,...,N). (indem Sie das Inverse des Ziels auf die Quelle anwenden)

Zählen Sie dann die Anzahl der Inversionen.

d.h.

vector source = ...;
vector target = ...;

vector inv(N)

for (int i = 0; i < N; i++)
   inv[target[i]] = i;

vector perm(N);

for (int i = 0; i < N; i++)
    perm[i] = source[inv[i]];

Zählen Sie dann die Inversionen in perm mit dem Standardalgorithmus.

Answer 3

Vorausgesetzt, die gewünschte Reihenfolge ist die sortierte Reihenfolge der Zahlen, reduziert sich das Problem auf das Finden der Anzahl von Inversionen in einem Array.

Ein Paar (i,j) gilt als Inversion, wenn i < j und array[i] > array[j] ist. Dies liegt daran, dass jeder (optimale) Tausch zwischen benachbarten Elementen die Anzahl der Inversionen genau um 1 verringert. Sie können die Anzahl der Inversionen in O(n log n) durch einen Divide-and-Conquer-Algorithmus finden, der sehr ähnlich zu Merge Sort ist. Hier ist eine gute Erklärung mit C-Code.

BEARBEITEN Nachweis, dass die Anzahl der Inversionen gleich der optimalen Anzahl von Vertauschungen ist:

Sei i eine beliebige Position in einem array. Das Vertauschen von array[i] und array[i+1] verringert die Anzahl der Inversionen um höchstens 1. Daher ist die Anzahl der erforderlichen Vertauschungen mindestens gleich der Anzahl der Inversionen. Andererseits, wenn array nicht sortiert ist, können wir immer ein Paar (i, i+1) finden, so dass array[i] > array[i+1] (d.h. (i,j) ist eine Inversion), und die Anzahl der Inversionen um 1 verringern, indem wir array[i] mit array[i+1] tauschen. Daher ist die Anzahl der Inversionen gleich der minimalen Anzahl von Vertauschungen.

Answer 4

Das Problem kann als ein Problem der Inversionszählung betrachtet werden, wie folgt:

Da die Prioritäten der Zahlen angegeben sind, d.h. in der Reihenfolge, in der wir sortieren sollen.

Betrachten Sie die Prioritäten und ersetzen Sie sie durch die Zahlen

z.B:

3 4 5 2 1  
4 1 5 2 3  

In dem obigen Testfall können wir beobachten, dass 4 die Priorität 1 zugewiesen wird, 1 die Priorität 2 , 5 die Priorität 3 und so weiter. Warum also die Zahl in der Original-Liste nicht durch diese Prioritäten ersetzen

d.h. die Original-Liste zu transformieren

(3 4 5 2 1) zu (5 1 3 4 2) 

(einfach die Zahl durch ihre jeweiligen Prioritäten wie oben besprochen ersetzen)

Jetzt wurde unsere Liste transformiert zu

5 1 3 4 2

und wir sollen sie einfach in aufsteigender Reihenfolge sortieren.

Jetzt sind nur benachbarte Vertauschungen erlaubt, die etwas mit Bubble Sort zu tun haben.

die Anzahl der benötigten Vertauschungen für Bubble Sort, die gleich der Summe der Anzahl der Elemente auf der rechten Seite jedes Elements ist, das kleiner als das aktuelle Element ist.

z.B: In der Liste

5 1 3 4 2

5 hat 4 Elemente, die kleiner als 5 auf seiner rechten Seite sind.

1 hat 0 Elemente, die kleiner als 1 auf seiner rechten Seite sind.

3 hat 1 Element, das kleiner als 3 auf seiner rechten Seite ist.

4 hat 1 Element, das kleiner als 1 auf seiner rechten Seite ist.

2 hat 0 Elemente, die kleiner als 2 auf der rechten Seite sind.

Jetzt ist das endgültige Ergebnis (4+0+1+1+0)=6.

Jetzt kann das obige Verfahren unter Verwendung der Inversionszählung berechnet werden, die hier diskutiert wird http://www.geeksforgeeks.org/archives/3968 .

HINWEIS: Die Antworten, die ich erhalten habe, waren sehr hilfreich, nur die ganze Sache detailiert beschreibend. Danke

Answer 5

Ich kann das mathematisch nicht beweisen, aber in 4/4 der Testfälle erhält man die minimalen Vertauschungen, indem man die Kisten in der richtigen Position beginnend mit der linksten (könnte dies auch mit der rechtesten tun) und nach rechts bewegt. d.h.

3 4 5 2 1 //Erstmal die 4 an die richtige Stelle bringen
4 3 5 2 1 //Fertig. Jetzt die 1 an die richtige Stelle bringen
4 3 5 1 2
4 3 1 5 2
4 1 3 5 2 //Fertig. Jetzt die 5
4 1 5 3 2 //Fertig. Jetzt die 2
4 1 5 2 3 //Alles erledigt.

Also scheint dieser Algorithmus für jede gegebene Eingabe das Minimum zu liefern. Der allgemein schlechteste Fall sieht wie eine Umkehrung aus, die N*(N-1)/2 Vertauschungen erfordert (siehe Beispiel 2).