Phân tích: Millionaire

Đề bài nêu rõ rằng người chơi có vô số lựa chọn tự do. Cô ấy có thể đặt cược BẤT KỲ phần nào trong số tiền hiện có của mình. Điều này khiến việc duyệt trâu (brute force) qua tất cả các mức đặt cược khả thi là không thể. Bí quyết là rời rạc hóa bài toán.

Theo một trong những nguyên tắc giải quyết vấn đề, chúng ta hãy xem xét các trường hợp dễ hơn. Bài toán sẽ dễ dàng nếu chỉ có một vòng đấu. Chúng tôi khuyên bạn nên thử giải cho trường hợp có hai vòng đấu. Nó không khó, nhưng nó tiết lộ bản chất thú vị của bài toán. Hình dưới đây minh họa tình huống ở vòng áp chót, vòng cuối cùng và sau vòng cuối cùng.

Các màu sắc đại diện cho các vùng xác suất khác nhau. Tất cả các số tiền trong cùng một vùng xác suất đều có chung một xác suất thắng cuộc. Các số tiền quan trọng được đánh dấu và dán nhãn.

Nếu chúng ta biết xác suất thắng cho tất cả các số tiền ở vòng tiếp theo \(P_{next}(sum)\), thì xác suất thắng ở vòng này là:

trong đó stake là số tiền chúng ta đặt cược.

Bây giờ, dựa trên sự tồn tại và vị trí của các số tiền quan trọng trong vòng tiếp theo, chúng ta có thể tìm thấy vị trí của các số tiền quan trọng trong vòng này. Hình dưới đây minh họa cách chúng ta tìm các số tiền này. Các điểm trung điểm giữa các số tiền quan trọng của vòng tiếp theo sẽ trở nên quan trọng trong vòng này. Ví dụ, trong trường hợp điểm màu xanh lá cây ở Hình 2, chúng ta có thể di chuyển lên bằng cách giảm mức đặt cược, và có thể di chuyển xuống bằng cách tăng mức đặt cược, mà không làm thay đổi xác suất cuối cùng. Xác suất của các điểm màu xanh lam, xanh lá cây và đỏ là như nhau. Điều này cũng minh họa rằng xác suất trong một 'vùng xác suất' được giới hạn bởi hai số tiền quan trọng sẽ bằng xác suất tại số tiền quan trọng thấp hơn.

Kết luận: Các số tiền quan trọng của vòng \(i\) là hợp của các số tiền quan trọng của vòng \((i+1)\) và các trung điểm của chúng. Chúng ta cần coi \(0\) là một số tiền quan trọng ở vòng cuối cùng vì chúng ta không thể đặt cược nhiều hơn số tiền mình có.

Bây giờ, chúng ta chỉ cần tính toán xác suất tại các số tiền quan trọng, khởi tạo tại \(1.0\) cho số tiền \(1.000.000\) đô la, và \(0.0\) cho \(0\) đô la ở vòng cuối cùng. Sau đó, đi ngược lại, chúng ta điền xác suất tại các số tiền quan trọng trong các vòng trước đó.

Theo giới hạn của dữ liệu vào, chúng ta có thể thử tất cả các mức đặt cược dẫn đến các điểm quan trọng ở vòng tiếp theo. Việc liệu có những tính chất toán học nào giúp giảm độ phức tạp của phép tính này hay không là một câu hỏi thú vị, nhưng nằm ngoài phạm vi của bài phân tích.

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