Todos os desafios
Difícil 0 resolvidos 0% de aceitação

Vencedor pelo método dos pares ranqueados (Tideman)

Encontre o vencedor de uma eleição pelo método dos pares ranqueados, travando as vitórias em confronto direto que não formam ciclo.

O que você vai aprender

  • Montar uma tabela de preferências em confronto direto a partir de cédulas ranqueadas
  • Ordenar as vitórias pela margem com regras exatas de desempate
  • Travar arestas apenas quando o grafo continua acíclico

Problema

Ver original (inglês)

O método dos pares ranqueados (ranked pairs, ou método de Tideman) escolhe o vencedor olhando para todos os confrontos diretos. Cada eleitor ordena todos os candidatos, e o candidato a vence o candidato b quando mais eleitores colocam a acima de b do que b acima de a. A margem dessa vitória é (eleitores que preferem a) − (eleitores que preferem b). Confrontos em que os dois lados têm a mesma contagem são deixados de fora.

  1. Ordene as vitórias pela margem, da maior para a menor. Margens iguais são ordenadas pelo número do vencedor, do menor para o maior, e depois pelo número do perdedor, também do menor para o maior.
  2. Percorra as vitórias nessa ordem e trave cada uma como uma seta do vencedor para o perdedor, a menos que essa seta feche um ciclo com as setas já travadas (ou seja, a menos que o perdedor já consiga chegar ao vencedor seguindo setas travadas). Nesse caso, a vitória é pulada.
  3. Os vencedores são os candidatos para os quais nenhuma seta travada aponta.

Implemente ranked_pairs_winner(candidates, ballots).

Entrada

candidates: os nomes dos candidatos. O candidato i é candidates[i].

ballots: uma linha por eleitor, com os números dos candidatos (a partir de 0) do mais preferido para o menos preferido. Cada linha contém todos os candidatos exatamente uma vez.

Saída

Retorne os nomes de todos os candidatos que não recebem nenhuma seta travada, na ordem em que aparecem em candidates. Normalmente é um único nome; podem ser vários quando alguns confrontos empataram, e sem nenhuma cédula são todos os candidatos.

Restrições

1 ≤ tamanho de candidates ≤ 9

0 ≤ número de cédulas ≤ 200

Exemplos

Exemplo 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]
]

Saída 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}
};

Saída 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}
};

Saída esperada:
string[] expected = new string[] {"Cal"};

Explicação

Cal vence Ann por 6 a 3 (margem 3), Ann vence Bob por 7 a 2 (margem 5) e Bob vence Cal por 5 a 4 (margem 1). Trava-se Ann sobre Bob e depois Cal sobre Ann; Bob sobre Cal fecharia um ciclo, então é pulada. Nenhuma seta aponta para Cal: ["Cal"].

Exemplo 2
Entrada:
candidates = ["Ann", "Bob"]
ballots = [
    [0, 1],
    [1, 0]
]

Saída esperada:
expected = ["Ann", "Bob"]
Entrada:
std::vector<std::string> candidates = {"Ann", "Bob"};
std::vector<std::vector<long long>> ballots = {
    {0, 1},
    {1, 0}
};

Saída 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}
};

Saída esperada:
string[] expected = new string[] {"Ann", "Bob"};

Explicação

Ann e Bob empatam por 1 a 1, então nenhuma seta é travada e os dois são retornados: ["Ann", "Bob"].

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Em cada cédula, cada candidato é preferido em relação a todos os que estão depois dele.

Dica 2

Antes de travar a seta do vencedor para o perdedor, faça uma busca a partir do perdedor pelas setas travadas; se chegar ao vencedor, pule essa vitória.

Dica 3

No final, um vencedor é um candidato sem nenhuma seta travada chegando nele.

Complexidade esperada

tempo O(b × c^2 + c^4), espaço extra O(c^2)

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.