โจทย์ทั้งหมด
ยาก 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

ผู้ชนะแบบจับคู่เรียงลำดับ (Ranked Pairs)

หาผู้ชนะการเลือกตั้งแบบ Ranked Pairs โดยล็อกชัยชนะแบบตัวต่อตัวที่ไม่ทำให้เกิดวงวน

สิ่งที่คุณจะได้เรียนรู้

  • สร้างตารางความชอบแบบตัวต่อตัวจากบัตรที่เรียงลำดับ
  • เรียงชัยชนะตามส่วนต่างพร้อมกฎตัดสินเมื่อเท่ากันอย่างแม่นยำ
  • ล็อกเส้นเชื่อมเฉพาะเมื่อกราฟยังไม่มีวงวน

โจทย์

วิธี Ranked Pairs เลือกผู้ชนะโดยพิจารณาการแข่งขันแบบตัวต่อตัวทุกคู่ ผู้มีสิทธิ์ทุกคนจะเรียงลำดับผู้สมัครทุกคน และผู้สมัคร a ชนะผู้สมัคร b เมื่อจำนวนคนที่จัดให้ a อยู่เหนือ b มีมากกว่าจำนวนคนที่จัดให้ b อยู่เหนือ a ส่วนต่างของชัยชนะนั้นคือ (จำนวนคนที่ชอบ a มากกว่า) − (จำนวนคนที่ชอบ b มากกว่า) คู่ที่ทั้งสองฝ่ายได้จำนวนเท่ากันจะไม่ถูกนำมาพิจารณา

  1. เรียงชัยชนะตามส่วนต่างจากมากไปน้อย ถ้าส่วนต่างเท่ากัน ให้เรียงตามหมายเลขของผู้ชนะจากน้อยไปมาก แล้วจึงเรียงตามหมายเลขของผู้แพ้จากน้อยไปมาก
  2. ไล่ดูชัยชนะตามลำดับนั้น แล้วล็อกแต่ละรายการเป็นลูกศรจากผู้ชนะไปยังผู้แพ้ เว้นแต่ลูกศรนั้นจะทำให้เกิดวงวนกับลูกศรที่ล็อกไว้แล้ว (กล่าวคือ ผู้แพ้สามารถไปถึงผู้ชนะได้อยู่แล้วโดยเดินตามลูกศรที่ล็อกไว้) ชัยชนะแบบนั้นให้ข้ามไป
  3. ผู้ชนะคือผู้สมัครที่ไม่มีลูกศรที่ล็อกไว้ชี้มาหาเลย

จงเขียน ranked_pairs_winner(candidates, ballots)

อินพุต

candidates: ชื่อผู้สมัคร ผู้สมัครหมายเลข i คือ candidates[i]

ballots: หนึ่งแถวต่อผู้มีสิทธิ์หนึ่งคน แต่ละแถวเป็นหมายเลขผู้สมัคร (เริ่มนับจาก 0) เรียงจากคนที่ชอบมากที่สุดไปน้อยที่สุด และมีผู้สมัครทุกคนอยู่ครบคนละหนึ่งครั้งพอดี

เอาต์พุต

คืนค่าชื่อผู้สมัครทุกคนที่ไม่มีลูกศรที่ล็อกไว้ชี้มาหา เรียงตามลำดับที่ปรากฏใน candidates โดยปกติจะมีเพียงชื่อเดียว แต่อาจมีหลายชื่อได้เมื่อบางคู่เสมอกัน และถ้าไม่มีบัตรเลยจะได้ผู้สมัครทุกคน

เงื่อนไข

1 ≤ ความยาวของ candidates ≤ 9

0 ≤ จำนวนบัตร ≤ 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 ชนะ Ann 6 ต่อ 3 (ส่วนต่าง 3) Ann ชนะ Bob 7 ต่อ 2 (ส่วนต่าง 5) และ Bob ชนะ Cal 5 ต่อ 4 (ส่วนต่าง 1) ล็อก Ann เหนือ Bob ก่อน แล้วล็อก Cal เหนือ Ann ส่วน Bob เหนือ Cal จะทำให้เกิดวงวนจึงข้ามไป ไม่มีลูกศรชี้มาที่ 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 กับ Bob เสมอกัน 1 ต่อ 1 จึงไม่มีลูกศรถูกล็อก และต้องคืนค่าทั้งสองคน ได้ ["Ann", "Bob"]

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

ในบัตรแต่ละใบ ผู้สมัครแต่ละคนถูกชอบมากกว่าทุกคนที่อยู่ลำดับหลังจากตน

คำใบ้ 2

ก่อนล็อกลูกศรจากผู้ชนะไปผู้แพ้ ให้ค้นจากผู้แพ้ไปตามลูกศรที่ล็อกไว้ ถ้าไปถึงผู้ชนะได้ ให้ข้ามไป

คำใบ้ 3

ตอนจบ ผู้ชนะคือผู้สมัครที่ไม่มีลูกศรที่ล็อกไว้ชี้เข้ามา

ความซับซ้อนที่คาดหวัง

เวลา O(b × c^2 + c^4), หน่วยความจำเพิ่ม O(c^2)

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก