Tous les défis
Difficile 0 résolus 0 % de réussite

Vainqueur par la méthode des paires classées

Trouvez le vainqueur d'une élection par la méthode des paires classées, en verrouillant les victoires en duel qui ne créent pas de cycle.

Ce que vous allez apprendre

  • Construire une table des duels à partir de bulletins classés
  • Trier les victoires par marge avec des règles de départage précises
  • Ne verrouiller une arête que si le graphe reste sans cycle

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.

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

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

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

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.