Phân tích: Cheaters

Bối cảnh

Bài toán này thách thức chúng ta với một trò chơi roulette "thông minh", nơi quả bóng luôn rơi vào một trong những con số có tổng số tiền đặt cược ít nhất. Với kiến thức này, chúng ta cần tính toán lợi nhuận kỳ vọng tối đa. Chúng ta biết các khoản cược hiện tại (phải là số nguyên) và ngân sách của mình. Chúng ta sẽ đặt cược (cũng là số nguyên) để tối đa hóa lợi nhuận kỳ vọng.

Ví dụ và nhận xét

Trước khi đi sâu vào giải pháp, hãy xem qua một vài ví dụ để có cái nhìn trực quan về chiến lược giải quyết. Đầu tiên, chúng ta mô tả quy ước được sử dụng trong các hình ảnh:

• Một ô vuông trong hình đại diện cho một đơn vị tiền tệ.
• Một cột trong hình đại diện cho khoản cược hiện tại (chồng tiền) trên một số nào đó.
• Màu sắc của các ô vuông:
  • Ô màu đỏ đại diện cho các khoản cược hiện có của những người chơi khác.
  • Ô màu trắng nghĩa là không có khoản cược nào.
  • Ô màu xanh lá cây đại diện cho các khoản cược chúng ta đã đặt.
  • Ô màu vàng đại diện cho một khoản cược chúng ta đang xem xét.
  • Ô màu xanh dương đại diện cho các khoản cược của chúng ta mà chúng ta đang nhấn mạnh.
• Trong các hình ảnh, chúng ta chỉ hiển thị 8 cột (các số khác nhau) mặc dù trong trò chơi roulette có 37 số khác nhau, chúng ta giả định tất cả các số khác đã có các khoản cược cao hơn nhiều.
• Chúng ta sắp xếp các chồng tiền (cột đỏ) theo chiều cao tăng dần từ trái sang phải.

Hãy bắt đầu với một ví dụ nhỏ (xem hình a). Ở đây, chúng ta có các chồng tiền với độ cao \(0, 0, 0, 2, 2, 3, 4, 4\). Giả sử chúng ta có \(3\) đơn vị để đặt cược: chúng ta nên đặt cược vào những chồng nào và bao nhiêu cho mỗi chồng? Trong trường hợp này, chúng ta có thể đặt cược vào ba chồng có độ cao \(0\) (xem hình b), điều này mang lại lợi nhuận kỳ vọng là \(33\).

Nhận xét #1: Vì chỉ những chồng có độ cao tối thiểu mới có cơ hội thắng, chúng ta muốn cố gắng đặt cược vào các chồng để tạo ra một độ cao tối thiểu.

Nếu chúng ta có \(6\) đơn vị để đặt cược thì sao? Chúng ta có thể một lần nữa đặt cược vào các chồng có độ cao \(0\) (xem hình c). Kết quả là có \(5\) chồng có độ cao \(2\) (\(3\) chồng xanh lá và \(2\) chồng đỏ). Lợi nhuận kỳ vọng của chúng ta là \(37.2\). Nhân tiện, nếu các chồng đỏ có độ cao \(2\) thay vào đó có độ cao \(3\), lợi nhuận kỳ vọng của chúng ta sẽ là \(66\)!

Nếu chúng ta có \(7\) đơn vị để đặt cược thì sao? Chúng ta có thể đặt \(6\) đơn vị như mô tả ở trên. Nhưng chúng ta nên đặt đơn vị thứ \(7\) ở đâu? Chúng ta có thể thử đặt nó vào các vị trí màu xanh dương trong hình d, nhưng điều đó không giúp ích gì cả. Hoặc chúng ta có thể thử đặt nó vào bất kỳ vị trí màu xanh dương nào trong hình e, điều này sẽ thay đổi lợi nhuận kỳ vọng vì nó sẽ làm giảm tổng số chồng có độ cao tối thiểu là \(2\). Nếu chúng ta đặt đơn vị thứ \(7\) vào vị trí màu vàng như trong hình f, chúng ta sẽ làm giảm lợi nhuận kỳ vọng! Nhưng nếu chúng ta đặt nó như trong hình g, lợi nhuận kỳ vọng sẽ tăng lên \(47\)! Nó tăng lên vì chúng ta đã giảm số lượng các chồng có độ cao tối thiểu mà không đóng góp vào lợi nhuận kỳ vọng của chúng ta.

Nhận xét #2: Chúng ta có thể tăng lợi nhuận kỳ vọng bằng cách giảm số lượng các chồng có độ cao tối thiểu.

Nếu chúng ta có \(8\) đơn vị để đặt cược thì sao? Bạn đoán đúng rồi đấy. Chúng ta có thể đặt nó như trong hình h và nhận được lợi nhuận kỳ vọng là \(64\). Nói chung, tập hợp các khoản cược tối ưu của chúng ta sẽ có dạng hình bậc thang với độ cao tối thiểu \(h\), và độ cao \(h+1\) hoặc cao hơn (như được hiển thị bởi các ô màu xanh dương trong hình i).

Chiến lược đơn giản

Chiến lược đơn giản của chúng ta (cho Small dataset) là đặt các khoản cược từng cái một như trong hình j. Mỗi lần chúng ta đặt một khoản cược (ví dụ: ở vị trí 1), chúng ta tính lợi nhuận kỳ vọng, sau đó đặt khoản cược tiếp theo (tức là 1 và 2), tính lợi nhuận kỳ vọng, rồi lặp lại cho cái tiếp theo (1, 2 và 3). Chúng ta giữ lại lợi nhuận kỳ vọng tối đa.

Chiến lược này hoạt động tốt khi số tiền đặt cược nhỏ, nhưng số tiền chúng ta có thể đặt cược có thể lên tới \(10^{12}\)! Do đó, chúng ta cần sử dụng một chiến lược chạy nhanh hơn.

Chiến lược nâng cao

Nhận xét #3: Đối với giải pháp tối ưu, bước nhảy từ độ cao tối thiểu \(h\) lên \(h+1\) (hoặc cao hơn) sẽ xảy ra tại một vị trí cột nào đó (xem hình k). Tại vị trí đó, chúng ta muốn độ cao tối thiểu \(h\) cao nhất có thể với số tiền chúng ta có.

Với nhận xét này, về cơ bản chúng ta sẽ cố định một vị trí cột và cố gắng xây dựng một "bậc thang" cao nhất có thể. Ví dụ, nếu chúng ta có \(7\) đơn vị tiền và chúng ta cố định vị trí bước nhảy sau cột đầu tiên như trong hình k, thì bậc thang cao nhất chúng ta có thể xây dựng được hiển thị trong hình l, sử dụng \(5\) đơn vị tiền (\(2\) đơn vị còn dư). Đối với vị trí bước nhảy sau cột thứ tư như trong hình m, chúng ta sử dụng toàn bộ \(7\) đơn vị tiền.

Do đó, chiến lược là thử tất cả các vị trí cột có thể (từ \(1\) đến \(37\)), tính toán "bậc thang" cao nhất mà chúng ta có thể tạo ra cho mỗi vị trí đó và tính lợi nhuận kỳ vọng. Như thường lệ, chúng ta giữ lại giá trị tối đa.

Vậy làm thế nào để tính toán bậc thang cao nhất có thể cho một vị trí cột cụ thể? Việc thêm từng ô vuông một sẽ quá chậm, do đó chúng ta sử dụng tìm kiếm nhị phân. Chúng ta muốn xác định độ cao tối thiểu \(h\) cao nhất cho vị trí cột đó. Lưu ý rằng vì lượng tiền cần thiết để xây dựng mỗi "bậc thang" tăng đơn điệu theo độ cao, chúng ta có thể thực hiện tìm kiếm nhị phân trên \(h\).

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