Todos los desafíos
Difícil 0 resueltos 0% de aceptación

Ganador por pares clasificados (método de Tideman)

Encuentra al ganador de una elección por el método de pares clasificados, fijando las victorias cara a cara que no formen un ciclo.

Lo que aprenderás

  • Construir una tabla de preferencias cara a cara a partir de boletas con orden de preferencia
  • Ordenar las victorias por margen con reglas exactas de desempate
  • Fijar aristas solo si el grafo sigue siendo acíclico

Problema

Ver original (inglés)

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.

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

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

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

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.