कठिन 0 हल किए गए 0% स्वीकृति

Ranked Pairs Winner

Find the ranked pairs winner of an election by locking head-to-head victories that do not make a cycle.

आप क्या सीखेंगे

  • Build a head-to-head preference table from ranked ballots
  • Sort victories by margin with exact tie rules
  • Lock edges only when they keep the graph acyclic

समस्या

अनुवाद दिखाएँ

Ranked pairs picks a winner by looking at every head-to-head matchup. Every voter ranks all the candidates, and candidate a beats candidate b when more voters rank a above b than b above a. The margin of that victory is (voters preferring a) − (voters preferring b). Matchups where both sides have the same count are left out.

  1. Sort the victories by margin, largest first. Equal margins are ordered by the winner's number, smaller first, and then by the loser's number, smaller first.
  2. Go through the victories in that order and lock each one in as an arrow from winner to loser, unless that arrow would close a cycle with arrows already locked (that is, unless the loser can already reach the winner by following locked arrows). Such a victory is skipped.
  3. The winners are the candidates that no locked arrow points to.

Implement ranked_pairs_winner(candidates, ballots).

Input

candidates: The candidates' names. Candidate i is candidates[i].

ballots: One row per voter: the candidate numbers (0-based) from most preferred to least preferred. Each row lists every candidate exactly once.

Output

Return the names of all candidates with no locked arrow pointing to them, in the order they appear in candidates. Usually this is a single name; it can be several when some matchups were tied, and with no ballots it is every candidate.

सीमाएँ

1 ≤ length of candidates ≤ 9

0 ≤ number of ballots ≤ 200

उदाहरण

उदाहरण 1
इनपुट:
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]
]

अपेक्षित आउटपुट:
expected = ["Cal"]
इनपुट:
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}
};

अपेक्षित आउटपुट:
std::vector<std::string> expected = {"Cal"};
इनपुट:
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}
};

अपेक्षित आउटपुट:
string[] expected = new string[] {"Cal"};

व्याख्या

Cal beats Ann 6 to 3 (margin 3), Ann beats Bob 7 to 2 (margin 5) and Bob beats Cal 5 to 4 (margin 1). Lock Ann over Bob, then Cal over Ann; Bob over Cal would close a cycle, so it is skipped. Nothing points to Cal: ["Cal"].

उदाहरण 2
इनपुट:
candidates = ["Ann", "Bob"]
ballots = [
    [0, 1],
    [1, 0]
]

अपेक्षित आउटपुट:
expected = ["Ann", "Bob"]
इनपुट:
std::vector<std::string> candidates = {"Ann", "Bob"};
std::vector<std::vector<long long>> ballots = {
    {0, 1},
    {1, 0}
};

अपेक्षित आउटपुट:
std::vector<std::string> expected = {"Ann", "Bob"};
इनपुट:
string[] candidates = new string[] {"Ann", "Bob"};
long[][] ballots = new long[][] {
    new long[] {0, 1},
    new long[] {1, 0}
};

अपेक्षित आउटपुट:
string[] expected = new string[] {"Ann", "Bob"};

व्याख्या

Ann and Bob are tied 1 to 1, so no arrow is locked and both are returned: ["Ann", "Bob"].

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

For every ballot, each candidate is preferred over everyone ranked after them.

संकेत 2

Before locking winner to loser, search from the loser along locked arrows; if you reach the winner, skip it.

संकेत 3

At the end, a winner is a candidate with no incoming locked arrow.

अपेक्षित जटिलता

O(b × c^2 + c^4) time, O(c^2) extra space

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।