Problème
La méthode des paires classées (Ranked Pairs) désigne un vainqueur en examinant chaque duel entre deux candidats. Chaque électeur classe tous les candidats, et le candidat a bat le candidat b lorsque plus d'électeurs placent a devant b que b devant a. La marge de cette victoire vaut (électeurs préférant a) − (électeurs préférant b). Les duels où les deux camps sont à égalité sont ignorés.
- Triez les victoires par marge décroissante. À marge égale, on classe d'abord selon le numéro du gagnant, du plus petit au plus grand, puis selon le numéro du perdant, du plus petit au plus grand.
- Parcourez les victoires dans cet ordre et verrouillez chacune sous forme d'une flèche allant du gagnant vers le perdant, sauf si cette flèche fermait un cycle avec les flèches déjà verrouillées (autrement dit, sauf si le perdant peut déjà atteindre le gagnant en suivant des flèches verrouillées). Une telle victoire est alors ignorée.
- Les vainqueurs sont les candidats vers lesquels ne pointe aucune flèche verrouillée.
Implémentez ranked_pairs_winner(candidates, ballots).
Entrée
candidates : les noms des candidats. Le candidat i est candidates[i].
ballots : une ligne par électeur, contenant les numéros des candidats (à partir de 0) du préféré au moins apprécié. Chaque ligne contient chaque candidat exactement une fois.
Sortie
Renvoyez les noms de tous les candidats vers lesquels ne pointe aucune flèche verrouillée, dans l'ordre où ils apparaissent dans candidates. En général, il n'y en a qu'un ; il peut y en avoir plusieurs si certains duels étaient à égalité, et sans aucun bulletin, ce sont tous les candidats.
Contraintes
1 ≤ longueur de candidates ≤ 9
0 ≤ nombre de bulletins ≤ 200
Exemples
Entrée :
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]
]
Sortie attendue :
expected = ["Cal"]
Entrée :
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}
};
Sortie attendue :
std::vector<std::string> expected = {"Cal"};
Entrée :
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}
};
Sortie attendue :
string[] expected = new string[] {"Cal"};
Explication
Cal bat Ann 6 à 3 (marge 3), Ann bat Bob 7 à 2 (marge 5) et Bob bat Cal 5 à 4 (marge 1). On verrouille Ann sur Bob, puis Cal sur Ann ; Bob sur Cal fermerait un cycle, donc cette victoire est ignorée. Aucune flèche ne pointe vers Cal : ["Cal"].
Entrée :
candidates = ["Ann", "Bob"]
ballots = [
[0, 1],
[1, 0]
]
Sortie attendue :
expected = ["Ann", "Bob"]
Entrée :
std::vector<std::string> candidates = {"Ann", "Bob"};
std::vector<std::vector<long long>> ballots = {
{0, 1},
{1, 0}
};
Sortie attendue :
std::vector<std::string> expected = {"Ann", "Bob"};
Entrée :
string[] candidates = new string[] {"Ann", "Bob"};
long[][] ballots = new long[][] {
new long[] {0, 1},
new long[] {1, 0}
};
Sortie attendue :
string[] expected = new string[] {"Ann", "Bob"};
Explication
Ann et Bob sont à égalité 1 à 1, donc aucune flèche n'est verrouillée et les deux sont renvoyés : ["Ann", "Bob"].
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Sur chaque bulletin, chaque candidat est préféré à tous ceux classés après lui.
Indice 2
Avant de verrouiller la flèche du gagnant vers le perdant, partez du perdant en suivant les flèches verrouillées ; si vous atteignez le gagnant, ignorez cette victoire.
Indice 3
À la fin, un vainqueur est un candidat vers lequel ne pointe aucune flèche verrouillée.
Complexité attendue
temps O(b × c^2 + c^4), espace supplémentaire O(c^2)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.