Problema
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.
- 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.
- 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.
- 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
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"].
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.