Problema
Il metodo Ranked Pairs (metodo di Tideman) sceglie il vincitore esaminando tutti gli scontri diretti. Ogni elettore ordina tutti i candidati, e il candidato a batte il candidato b se gli elettori che mettono a prima di b sono più di quelli che mettono b prima di a. Il margine di questa vittoria è (elettori che preferiscono a) − (elettori che preferiscono b). Gli scontri in cui le due parti hanno lo stesso numero di preferenze vengono scartati.
- Ordina le vittorie per margine, dal più grande al più piccolo. A parità di margine, viene prima la vittoria con il numero del vincitore più piccolo e poi, a parità anche di questo, quella con il numero dello sconfitto più piccolo.
- Scorri le vittorie in quest'ordine e fissa ciascuna come una freccia dal vincitore allo sconfitto, a meno che questa freccia non chiuda un ciclo con le frecce già fissate (cioè a meno che lo sconfitto non possa già raggiungere il vincitore seguendo frecce fissate). In quel caso la vittoria viene saltata.
- I vincitori sono i candidati verso cui non punta nessuna freccia fissata.
Implementa ranked_pairs_winner(candidates, ballots).
Input
candidates: i nomi dei candidati. Il candidato i è candidates[i].
ballots: una riga per elettore, con i numeri dei candidati (a partire da 0) dal preferito al meno gradito. Ogni riga contiene tutti i candidati esattamente una volta.
Output
Restituisci i nomi di tutti i candidati verso cui non punta nessuna freccia fissata, nell'ordine in cui compaiono in candidates. Di solito è un solo nome; possono essere più nomi se alcuni scontri sono finiti in parità, e senza schede sono tutti i candidati.
Vincoli
1 ≤ lunghezza di candidates ≤ 9
0 ≤ numero di schede ≤ 200
Esempi
Input:
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]
]
Output atteso:
expected = ["Cal"]
Input:
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}
};
Output atteso:
std::vector<std::string> expected = {"Cal"};
Input:
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}
};
Output atteso:
string[] expected = new string[] {"Cal"};
Spiegazione
Cal batte Ann 6 a 3 (margine 3), Ann batte Bob 7 a 2 (margine 5) e Bob batte Cal 5 a 4 (margine 1). Si fissa prima Ann su Bob, poi Cal su Ann; Bob su Cal chiuderebbe un ciclo, quindi viene saltata. Nessuna freccia punta verso Cal: ["Cal"].
Input:
candidates = ["Ann", "Bob"]
ballots = [
[0, 1],
[1, 0]
]
Output atteso:
expected = ["Ann", "Bob"]
Input:
std::vector<std::string> candidates = {"Ann", "Bob"};
std::vector<std::vector<long long>> ballots = {
{0, 1},
{1, 0}
};
Output atteso:
std::vector<std::string> expected = {"Ann", "Bob"};
Input:
string[] candidates = new string[] {"Ann", "Bob"};
long[][] ballots = new long[][] {
new long[] {0, 1},
new long[] {1, 0}
};
Output atteso:
string[] expected = new string[] {"Ann", "Bob"};
Spiegazione
Ann e Bob sono in parità 1 a 1, quindi non si fissa nessuna freccia e vengono restituiti entrambi: ["Ann", "Bob"].
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
In ogni scheda, ciascun candidato è preferito a tutti quelli che vengono dopo di lui.
Suggerimento 2
Prima di fissare la freccia dal vincitore allo sconfitto, parti dallo sconfitto e segui le frecce già fissate; se raggiungi il vincitore, salta questa vittoria.
Suggerimento 3
Alla fine, un vincitore è un candidato senza frecce fissate in entrata.
Complessità attesa
tempo O(b × c^2 + c^4), spazio aggiuntivo O(c^2)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.