Tất cả thử thách
Khó 0 đã giải Tỷ lệ chấp nhận 0%

Người thắng theo phương pháp Ranked Pairs

Tìm người thắng cử theo phương pháp ranked pairs bằng cách chốt các trận thắng đối đầu không tạo thành chu trình.

Bạn sẽ học được gì

  • Lập bảng so sánh đối đầu từ các lá phiếu xếp hạng
  • Sắp xếp các trận thắng theo cách biệt với quy tắc phân xử hòa chính xác
  • Chỉ chốt cạnh khi đồ thị vẫn không có chu trình

Đề bài

Xem bản gốc (English)

Phương pháp ranked pairs (cặp xếp hạng) chọn người thắng bằng cách xét mọi cặp đối đầu. Mỗi cử tri xếp hạng tất cả ứng viên, và ứng viên a thắng ứng viên b khi số cử tri xếp a trên b nhiều hơn số cử tri xếp b trên a. Cách biệt của trận thắng đó là (số cử tri thích a hơn) − (số cử tri thích b hơn). Những cặp mà hai bên bằng nhau thì bỏ qua.

  1. Sắp xếp các trận thắng theo cách biệt, lớn nhất trước. Nếu cách biệt bằng nhau, trận có số thứ tự người thắng nhỏ hơn đứng trước; nếu vẫn bằng thì trận có số thứ tự người thua nhỏ hơn đứng trước.
  2. Duyệt các trận thắng theo thứ tự đó và chốt từng trận thành một mũi tên từ người thắng đến người thua, trừ khi mũi tên ấy khép kín một chu trình với các mũi tên đã chốt (tức là trừ khi từ người thua đã có thể đi tới người thắng theo các mũi tên đã chốt). Trận thắng như vậy bị bỏ qua.
  3. Người thắng cuộc là những ứng viên không bị mũi tên đã chốt nào chỉ vào.

Hãy viết ranked_pairs_winner(candidates, ballots).

Đầu vào

candidates: Tên các ứng viên. Ứng viên i là candidates[i].

ballots: Mỗi cử tri một hàng, gồm số thứ tự các ứng viên (đánh số từ 0) xếp từ người được ưu tiên nhất đến người ít được ưu tiên nhất. Mỗi hàng liệt kê mọi ứng viên đúng một lần.

Đầu ra

Trả về tên tất cả ứng viên không bị mũi tên đã chốt nào chỉ vào, theo thứ tự trong candidates. Thường chỉ có một tên; có thể có nhiều tên khi một số cặp đối đầu hòa nhau, và nếu không có lá phiếu nào thì đó là tất cả ứng viên.

Ràng buộc

1 ≤ độ dài candidates ≤ 9

0 ≤ số lá phiếu ≤ 200

Ví dụ

Ví dụ 1
Đầu vào:
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]
]

Kết quả mong đợi:
expected = ["Cal"]
Đầu vào:
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}
};

Kết quả mong đợi:
std::vector<std::string> expected = {"Cal"};
Đầu vào:
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}
};

Kết quả mong đợi:
string[] expected = new string[] {"Cal"};

Giải thích

Cal thắng Ann 6 phiếu so với 3 (cách biệt 3), Ann thắng Bob 7 so với 2 (cách biệt 5) và Bob thắng Cal 5 so với 4 (cách biệt 1). Chốt Ann thắng Bob trước, rồi đến Cal thắng Ann; Bob thắng Cal sẽ khép kín chu trình nên bị bỏ qua. Không có mũi tên nào chỉ vào Cal: ["Cal"].

Ví dụ 2
Đầu vào:
candidates = ["Ann", "Bob"]
ballots = [
    [0, 1],
    [1, 0]
]

Kết quả mong đợi:
expected = ["Ann", "Bob"]
Đầu vào:
std::vector<std::string> candidates = {"Ann", "Bob"};
std::vector<std::vector<long long>> ballots = {
    {0, 1},
    {1, 0}
};

Kết quả mong đợi:
std::vector<std::string> expected = {"Ann", "Bob"};
Đầu vào:
string[] candidates = new string[] {"Ann", "Bob"};
long[][] ballots = new long[][] {
    new long[] {0, 1},
    new long[] {1, 0}
};

Kết quả mong đợi:
string[] expected = new string[] {"Ann", "Bob"};

Giải thích

Ann và Bob hòa 1 đều, nên không có mũi tên nào được chốt và cả hai đều được trả về: ["Ann", "Bob"].

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Trên mỗi lá phiếu, mỗi ứng viên được ưu tiên hơn tất cả những người xếp sau mình.

Gợi ý 2

Trước khi chốt mũi tên từ người thắng đến người thua, hãy tìm đường từ người thua theo các mũi tên đã chốt; nếu tới được người thắng thì bỏ qua trận đó.

Gợi ý 3

Cuối cùng, người thắng là ứng viên không có mũi tên đã chốt nào đi vào.

Độ phức tạp mong đợi

thời gian O(b × c^2 + c^4), bộ nhớ phụ O(c^2)

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.