समस्या
Ranked pairs विधि हर आमने-सामने के मुकाबले को देखकर विजेता चुनती है। हर मतदाता सभी उम्मीदवारों को रैंक करता है, और उम्मीदवार a, उम्मीदवार b को हराता है जब a को b से ऊपर रखने वाले मतदाता, b को a से ऊपर रखने वालों से ज़्यादा हों। उस जीत का अंतर (margin) है (a को पसंद करने वाले मतदाता) − (b को पसंद करने वाले मतदाता)। जिन मुकाबलों में दोनों तरफ़ की गिनती बराबर है, वे छोड़ दिए जाते हैं।
- जीतों को अंतर के हिसाब से sort कीजिए, सबसे बड़ा पहले। बराबर अंतर होने पर विजेता का नंबर छोटा वाला पहले, फिर हारने वाले का नंबर छोटा वाला पहले।
- इसी क्रम में जीतों पर चलिए और हर जीत को विजेता से हारने वाले की ओर एक तीर के रूप में lock कीजिए, बशर्ते वह तीर पहले से lock किए गए तीरों के साथ चक्र पूरा न करे (यानी, अगर हारने वाला पहले से lock किए तीरों पर चलकर विजेता तक पहुँच सकता है, तो नहीं)। ऐसी जीत छोड़ दी जाती है।
- विजेता वे उम्मीदवार हैं जिनकी ओर कोई lock किया गया तीर नहीं आता।
ranked_pairs_winner(candidates, ballots) लिखिए।
इनपुट
candidates: उम्मीदवारों के नाम। उम्मीदवार i है candidates[i]।
ballots: हर मतदाता के लिए एक पंक्ति: उम्मीदवारों के नंबर (0 से शुरू), सबसे पसंदीदा से सबसे कम पसंदीदा तक। हर पंक्ति में हर उम्मीदवार ठीक एक बार आता है।
आउटपुट
उन सभी उम्मीदवारों के नाम लौटाइए जिनकी ओर कोई lock किया गया तीर नहीं आता, उसी क्रम में जिसमें वे candidates में हैं। आम तौर पर यह एक ही नाम होता है; कुछ मुकाबले बराबर रहे हों तो कई नाम हो सकते हैं, और कोई मतपत्र न हो तो सभी उम्मीदवार।
सीमाएँ
1 ≤ candidates की लंबाई ≤ 9
0 ≤ मतपत्रों की संख्या ≤ 200
उदाहरण
इनपुट:
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, Ann को 6 से 3 से हराता है (अंतर 3), Ann, Bob को 7 से 2 से (अंतर 5) और Bob, Cal को 5 से 4 से (अंतर 1)। पहले Ann से Bob की ओर तीर lock होता है, फिर Cal से Ann की ओर; Bob से Cal की ओर वाला तीर चक्र पूरा कर देगा, इसलिए छोड़ दिया जाता है। Cal की ओर कोई तीर नहीं आता: ["Cal"]।
इनपुट:
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 और Bob 1 से 1 पर बराबर हैं, इसलिए कोई तीर lock नहीं होता और दोनों लौटाए जाते हैं: ["Ann", "Bob"]।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
हर मतपत्र में हर उम्मीदवार अपने बाद रैंक किए गए सभी उम्मीदवारों से ज़्यादा पसंद किया जाता है।
संकेत 2
विजेता से हारने वाले की ओर तीर lock करने से पहले, हारने वाले से lock किए तीरों पर चलकर खोजिए; अगर विजेता तक पहुँच जाएँ, तो इसे छोड़ दीजिए।
संकेत 3
अंत में, विजेता वह उम्मीदवार है जिसकी ओर कोई lock किया गया तीर नहीं आता।
अपेक्षित जटिलता
समय O(b × c^2 + c^4), अतिरिक्त स्थान O(c^2)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।