Problema
El método de pares clasificados (ranked pairs) elige al ganador revisando todos los enfrentamientos cara a cara. Cada votante ordena a todos los candidatos, y el candidato a le gana al candidato b cuando hay más votantes que ponen a a por encima de b que votantes que ponen a b por encima de a. El margen de esa victoria es (votantes que prefieren a a) − (votantes que prefieren a b). Los enfrentamientos en los que ambos lados tienen la misma cantidad se descartan.
- Ordena las victorias por margen, de mayor a menor. Si dos márgenes son iguales, va primero la del ganador con número menor y, después, la del perdedor con número menor.
- Recorre las victorias en ese orden y fija cada una como una flecha del ganador al perdedor, a menos que esa flecha cierre un ciclo con las flechas ya fijadas (es decir, a menos que el perdedor ya pueda llegar al ganador siguiendo flechas fijadas). Esa victoria se omite.
- Los ganadores son los candidatos a los que no apunta ninguna flecha fijada.
Implementa ranked_pairs_winner(candidates, ballots).
Entrada
candidates: los nombres de los candidatos. El candidato i es candidates[i].
ballots: una fila por votante con los números de los candidatos (empezando en 0), del más preferido al menos preferido. Cada fila contiene a todos los candidatos exactamente una vez.
Salida
Devuelve los nombres de todos los candidatos a los que no apunta ninguna flecha fijada, en el orden en que aparecen en candidates. Normalmente es un solo nombre; pueden ser varios cuando algunos enfrentamientos terminaron empatados, y si no hay boletas son todos los candidatos.
Restricciones
1 ≤ longitud de candidates ≤ 9
0 ≤ número de boletas ≤ 200
Ejemplos
Entrada:
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]
]
Salida esperada:
expected = ["Cal"]
Entrada:
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}
};
Salida esperada:
std::vector<std::string> expected = {"Cal"};
Entrada:
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}
};
Salida esperada:
string[] expected = new string[] {"Cal"};
Explicación
Cal le gana a Ann 6 a 3 (margen 3), Ann le gana a Bob 7 a 2 (margen 5) y Bob le gana a Cal 5 a 4 (margen 1). Se fija Ann sobre Bob y luego Cal sobre Ann; Bob sobre Cal cerraría un ciclo, así que se omite. Nada apunta a Cal: ["Cal"].
Entrada:
candidates = ["Ann", "Bob"]
ballots = [
[0, 1],
[1, 0]
]
Salida esperada:
expected = ["Ann", "Bob"]
Entrada:
std::vector<std::string> candidates = {"Ann", "Bob"};
std::vector<std::vector<long long>> ballots = {
{0, 1},
{1, 0}
};
Salida esperada:
std::vector<std::string> expected = {"Ann", "Bob"};
Entrada:
string[] candidates = new string[] {"Ann", "Bob"};
long[][] ballots = new long[][] {
new long[] {0, 1},
new long[] {1, 0}
};
Salida esperada:
string[] expected = new string[] {"Ann", "Bob"};
Explicación
Ann y Bob empatan 1 a 1, así que no se fija ninguna flecha y se devuelven los dos: ["Ann", "Bob"].
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
En cada boleta, cada candidato es preferido sobre todos los que aparecen después de él.
Pista 2
Antes de fijar la flecha del ganador al perdedor, busca desde el perdedor siguiendo las flechas fijadas; si llegas al ganador, omítela.
Pista 3
Al final, un ganador es un candidato sin ninguna flecha fijada que llegue a él.
Complejidad esperada
tiempo O(b × c^2 + c^4), espacio extra O(c^2)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.