Phân tích bài toán

Có \(4^Q\) điểm trong không gian, mỗi điểm đại diện cho một tổ hợp đáp án -- một đáp án cho mỗi câu trong số \(Q\) câu hỏi. Vì đáp án của các câu hỏi độc lập với nhau, xác suất thành công tại mỗi điểm có thể được tính đơn giản bằng tích các xác suất từ mỗi câu hỏi thành phần.

Mô hình toán học đơn giản bao gồm \(4^Q\) điểm, mỗi điểm có một giá trị xác suất. Có duy nhất một điểm "đúng" ẩn trong số \(4^Q\) điểm đó; bạn có thể chọn tối đa \(M\) điểm; và bạn thắng trò chơi nếu một trong số chúng là điểm đúng. Sau khi bạn chọn một điểm, bạn biết được nó có đúng hay không, nhưng điều đó không làm thay đổi xác suất tương đối của các điểm còn lại. Chiến lược tốt nhất đơn giản là xem xét các điểm theo thứ tự xác suất giảm dần. Nhiệm vụ của bạn trong bài toán này là tính tổng của (tối đa) \(M\) giá trị cao nhất trong số \(4^Q\) giá trị đó.

Giải pháp

Mặc dù \(Q\) có vẻ vừa phải, nhưng \(4^Q\) bước tính toán có thể là một khối lượng công việc khổng lồ vượt quá khả năng của máy tính. Ràng buộc quan trọng trong bài toán này là thực tế \(M\) cũng vừa phải, và chúng ta có thể tính toán \(M\) giá trị cao nhất từng cái một.

Cách 1: Sử dụng Priority Queue

Một giải pháp sử dụng hàng đợi ưu tiên (priority queue) \(L\) để lưu trữ tất cả các ứng viên tổ hợp đáp án cho giá trị cao nhất tiếp theo -- sau khi chúng ta đã tính được \(k\) giá trị đầu tiên. Một chút suy luận sẽ thuyết phục bạn rằng tổ hợp cao thứ \((k+1)\) phải được tạo ra bằng cách lấy một trong \(k\) tổ hợp đầu tiên và thay đổi đáp án của một câu hỏi sang bước "tệ hơn" tiếp theo (đáp án có xác suất cao tiếp theo). Vì vậy, trong mỗi bước, chúng ta có thể lấy phần tử đầu tiên \(S\) (phần tử có xác suất cao nhất) từ \(L\), sau đó thêm (tối đa) \(Q\) ứng viên mới trở lại vào \(L\). Mỗi ứng viên mới được tạo ra bằng cách chuyển một đáp án trong \(S\) sang đáp án tệ hơn một bậc. Kích thước của \(L\) sẽ không bao giờ vượt quá \(M \times Q\), và độ phức tạp thời gian là \(O(MQ \log MQ)\).

Cách 2: Quy hoạch động kết hợp cắt tỉa

Một giải pháp khác có cách cài đặt thậm chí còn đơn giản hơn: ý tưởng là thêm từng câu hỏi một. Đối với \(k\) câu hỏi đầu tiên, có \(4^k\) tổ hợp giải pháp khả thi, mỗi tổ hợp có xác suất trả lời đúng tất cả \(k\) câu hỏi đầu tiên. Khi chúng ta thêm câu hỏi thứ \((k+1)\), tập hợp các tổ hợp giải pháp mới, cùng với xác suất của chúng, có thể được tính bằng cách lấy mỗi giá trị trong số các giá trị của bước trước đó và nhân nó với bốn xác suất cho mỗi đáp án của câu hỏi \((k+1)\). Chúng ta có thể dễ dàng tính toán tất cả các giá trị này, sau đó chỉ giữ lại (cắt tỉa) \(M\) giá trị lớn nhất, rồi lặp lại quy trình cho các câu hỏi còn lại. Việc cắt tỉa mất \(O(M \log M)\), và quy trình này được lặp lại \(Q\) lần, cho tổng độ phức tạp thời gian là \(O(QM \log M)\).

Thông tin thêm

• Xác suất rời rạc (Discrete Probability)
• Phân phối đồng thời (Joint Distribution)

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