Tutte le sfide
Difficile 0 risolte 0% di accettazione

Vincitore con il metodo Ranked Pairs

Trova il vincitore di un'elezione con il metodo Ranked Pairs, fissando le vittorie negli scontri diretti che non creano un ciclo.

Cosa imparerai

  • Costruire una tabella degli scontri diretti a partire dalle schede a preferenze ordinate
  • Ordinare le vittorie per margine con regole precise per le parità
  • Fissare un arco solo se il grafo resta aciclico

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.

  1. 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.
  2. 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.
  3. 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

Esempio 1
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"].

Esempio 2
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.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.