Phân tích: Many Prizes

Trước hết, có một quan sát giúp công việc dễ dàng hơn. Hãy đảo ngược số hiệu của mọi đội — đội \(0\) trở thành đội \(2^N-1\), đội \(1\) trở thành đội \(2^N-2\), v.v. — nhưng giữ nguyên cây thi đấu. Khi đó thứ hạng cuối cùng của các đội cũng bị đảo ngược, bởi mọi thành tích đều bị đảo ngược: thắng trở thành thua và ngược lại.

Vì thế, bài toán tìm đội có thứ hạng thấp nhất vẫn có thể lọt vào top \(P\) tương đương với bài toán tìm đội có thứ hạng cao nhất vẫn có thể nằm trong \(P\) vị trí cuối; nói cách khác, đội đó không lọt vào top \(2^N-P\). Do đó, nếu trả lời được câu hỏi “đội có thứ hạng thấp nhất nào vẫn có thể lọt vào top \(P\)?”, ta có thể chạy cùng đoạn mã để tìm đội có thứ hạng thấp nhất vẫn có thể lọt vào top \(2^N-P\), trừ đi một, rồi đảo ngược số hiệu. Kết quả thu được là đội có thứ hạng thấp nhất luôn giành giải. Như vậy, ta chỉ cần giải một bài toán: tìm đội có thứ hạng thấp nhất được bảo đảm nằm trong top \(P\).

Với tập dữ liệu nhỏ, có nhiều nhất \(1024\) đội. Ta có thể lần lượt tìm cây thi đấu mang lại vị trí tốt nhất cho từng đội, rồi xem đội có thứ hạng thấp nhất nào vẫn giành giải. Tuy nhiên, ta sẽ bỏ qua cách này và đi thẳng tới lời giải cho tập dữ liệu lớn, nơi \(2^{50}\) đội rõ ràng loại bỏ mọi cách tiếp cận trực tiếp.

Quan sát then chốt là: nếu muốn một đội đạt thứ hạng cao nhất có thể, ta có thể sắp xếp để thành tích của đội đó gồm một chuỗi trận thắng rồi đến một chuỗi trận thua, không có dạng nào khác. Điều này nghe có vẻ bất ngờ nhưng đúng.

Giả sử ngược lại rằng đội \(A\) thua đội \(B\), rồi sau đó thắng đội \(C\), trong khi \(C\) đã đấu với \(D\) ở vòng trước. Cho đến vòng mà \(A\) gặp \(B\), thành tích của bốn đội là giống hệt nhau. Hơn nữa, bốn cây thi đấu dẫn tới các đội này vẫn rời nhau, nên ta có thể hoán đổi chúng. Cụ thể, hãy đổi toàn bộ cây của \(C\) với toàn bộ cây của \(B\). Vì ta đổi nguyên cây, thành tích của các đội không đổi; nhưng giờ \(A\) sẽ gặp \(C\) trong trận trước đó và thắng. Do vậy, bất kể sau đó xảy ra chuyện gì, thành tích của \(A\) cũng tốt hơn hẳn thành tích cũ. Suy ra mọi cách sắp xếp khiến \(A\) có một trận thua rồi mới có một trận thắng đều không tối ưu.

Nhờ đó, ta có thể tìm thứ hạng cao nhất mà một đội cho trước có thể đạt được: chỉ cần tham lam thắng nhiều trận nhất có thể. Đội tệ nhất không thể thắng trận nào. Nếu không phải đội tệ nhất, đội đó chắc chắn có thể thắng trận đầu. Trận thứ hai phải đấu với người thắng của một trận khác, nên để thắng trận ấy, đội phải mạnh hơn ba đội. Để thắng hai trận, đội phải mạnh hơn bảy đội, và cứ thế.

Ta cũng có thể đảo ngược lập luận để tìm đội có thứ hạng thấp nhất vẫn có thể giành giải. Trước hết, hỏi cần thắng bao nhiêu trận để giành giải. Không thắng trận nào thì vẫn nằm trong top \(2^N\) — không phải thành tích quá lớn! Thắng một trận thì nằm trong top \(2^{N-1}\), và cứ tiếp tục như vậy. Khi biết số trận cần thắng, ta biết ngay đội phải mạnh hơn bao nhiêu đội khác.

Đoạn mã Python ngắn sau hiện thực hóa lập luận đó:

def LowRankCanWin(N, P):
  if P == 0:
    return -1
  matches_won = 0
  size_of_group = 2 ** N
  while size_of_group > P:
    matches_won += 1
    size_of_group /= 2
  return 2 ** N - 2 ** matches_won

def ManyPrizes(N, P):
  print 2 ** N - LowRankCanWin(N, 2 ** N - P) - 2, LowRankCanWin(N, P)

Dựa trên phân tích chính thức của Google Code Jam.