Alle Herausforderungen
Schwierig 0 gelöst 0% Erfolgsquote

Sieger nach der Ranked-Pairs-Methode

Ermittle den Sieger einer Wahl nach Ranked Pairs, indem du Siege im direkten Vergleich festschreibst, solange kein Zyklus entsteht.

Das lernst du

  • Aus Ranglisten-Stimmzetteln eine Tabelle der direkten Vergleiche aufbauen
  • Siege nach Vorsprung mit genauen Regeln für Gleichstände sortieren
  • Kanten nur festschreiben, wenn der Graph dadurch zyklenfrei bleibt

Problem

Die Ranked-Pairs-Methode (nach Tideman) bestimmt den Sieger über alle direkten Duelle. Jeder Wähler bringt alle Kandidaten in eine Rangfolge, und Kandidat a schlägt Kandidat b, wenn mehr Wähler a vor b einordnen als b vor a. Der Vorsprung dieses Siegs ist (Wähler, die a bevorzugen) − (Wähler, die b bevorzugen). Duelle, bei denen beide Seiten gleich viele Wähler haben, fallen weg.

  1. Sortiere die Siege nach Vorsprung, den größten zuerst. Bei gleichem Vorsprung entscheidet die Nummer des Siegers (die kleinere zuerst) und danach die Nummer des Verlierers (die kleinere zuerst).
  2. Gehe die Siege in dieser Reihenfolge durch und schreibe jeden als Pfeil vom Sieger zum Verlierer fest, außer dieser Pfeil würde mit den bereits festgeschriebenen Pfeilen einen Zyklus schließen (also außer der Verlierer kann den Sieger schon über festgeschriebene Pfeile erreichen). Ein solcher Sieg wird übersprungen.
  3. Sieger sind die Kandidaten, auf die kein festgeschriebener Pfeil zeigt.

Implementiere ranked_pairs_winner(candidates, ballots).

Eingabe

candidates: Die Namen der Kandidaten. Kandidat i ist candidates[i].

ballots: Eine Zeile pro Wähler mit den Nummern der Kandidaten (ab 0 gezählt), vom liebsten bis zum am wenigsten gewünschten. Jede Zeile enthält jeden Kandidaten genau einmal.

Ausgabe

Gib die Namen aller Kandidaten, auf die kein festgeschriebener Pfeil zeigt, in der Reihenfolge zurück, in der sie in candidates stehen. Meist ist das ein einziger Name; es können mehrere sein, wenn manche Duelle unentschieden waren, und ohne Stimmzettel sind es alle Kandidaten.

Einschränkungen

1 ≤ Länge von candidates ≤ 9

0 ≤ Anzahl der Stimmzettel ≤ 200

Beispiele

Beispiel 1
Eingabe:
candidates = ["Ann", "Bob", "Cal"]
ballots = [
    [0, 1, 2],
    [0, 1, 2],
    [0, 1, 2],
    [1, 2, 0],
    [1, 2, 0],
    [2, 0, 1],
    [2, 0, 1],
    [2, 0, 1],
    [2, 0, 1]
]

Erwartete Ausgabe:
expected = ["Cal"]
Eingabe:
std::vector<std::string> candidates = {"Ann", "Bob", "Cal"};
std::vector<std::vector<long long>> ballots = {
    {0, 1, 2},
    {0, 1, 2},
    {0, 1, 2},
    {1, 2, 0},
    {1, 2, 0},
    {2, 0, 1},
    {2, 0, 1},
    {2, 0, 1},
    {2, 0, 1}
};

Erwartete Ausgabe:
std::vector<std::string> expected = {"Cal"};
Eingabe:
string[] candidates = new string[] {"Ann", "Bob", "Cal"};
long[][] ballots = new long[][] {
    new long[] {0, 1, 2},
    new long[] {0, 1, 2},
    new long[] {0, 1, 2},
    new long[] {1, 2, 0},
    new long[] {1, 2, 0},
    new long[] {2, 0, 1},
    new long[] {2, 0, 1},
    new long[] {2, 0, 1},
    new long[] {2, 0, 1}
};

Erwartete Ausgabe:
string[] expected = new string[] {"Cal"};

Erläuterung

Cal schlägt Ann mit 6 zu 3 (Vorsprung 3), Ann schlägt Bob mit 7 zu 2 (Vorsprung 5) und Bob schlägt Cal mit 5 zu 4 (Vorsprung 1). Zuerst wird Ann vor Bob festgeschrieben, dann Cal vor Ann; Bob vor Cal würde einen Zyklus schließen und wird übersprungen. Auf Cal zeigt nichts: ["Cal"].

Beispiel 2
Eingabe:
candidates = ["Ann", "Bob"]
ballots = [
    [0, 1],
    [1, 0]
]

Erwartete Ausgabe:
expected = ["Ann", "Bob"]
Eingabe:
std::vector<std::string> candidates = {"Ann", "Bob"};
std::vector<std::vector<long long>> ballots = {
    {0, 1},
    {1, 0}
};

Erwartete Ausgabe:
std::vector<std::string> expected = {"Ann", "Bob"};
Eingabe:
string[] candidates = new string[] {"Ann", "Bob"};
long[][] ballots = new long[][] {
    new long[] {0, 1},
    new long[] {1, 0}
};

Erwartete Ausgabe:
string[] expected = new string[] {"Ann", "Bob"};

Erläuterung

Ann und Bob stehen 1 zu 1, also wird kein Pfeil festgeschrieben und beide werden zurückgegeben: ["Ann", "Bob"].

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Auf jedem Stimmzettel wird jeder Kandidat allen vorgezogen, die nach ihm eingeordnet sind.

Hinweis 2

Bevor du Sieger vor Verlierer festschreibst, suche vom Verlierer aus entlang der festgeschriebenen Pfeile; erreichst du den Sieger, überspringe den Sieg.

Hinweis 3

Am Ende ist ein Sieger ein Kandidat ohne eingehenden festgeschriebenen Pfeil.

Erwartete Komplexität

Zeit O(b × c^2 + c^4), zusätzlicher Speicher O(c^2)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.