Phân tích: Perfect Game

Mở đầu

Không có gì ngạc nhiên khi bài toán này được lấy cảm hứng từ một trò chơi điện tử mà tác giả đã chơi: Super Meat Boy. Việc chuyển đổi thử thách thành tựu thực tế thành một bài toán Code Jam bao gồm một chút đơn giản hóa: ví dụ, trong thực tế thời gian để thua một màn không nhất thiết bằng thời gian để thắng nó.

Tổng thời gian kỳ vọng và số lần thử

Tổng thời gian kỳ vọng của bạn để hoàn thành thành tựu sẽ là số lần thử kỳ vọng, nhân với thời gian kỳ vọng của mỗi lần thử.

Đầu tiên, hãy tính xem sẽ mất bao nhiêu lần thử để hoàn thành thành tựu. Xác suất thành công trong bất kỳ lần thử nào là dễ tính, vì nó đơn giản là xác suất thành công ở mọi màn chơi một lần mà không thất bại ở bất kỳ màn nào: (1-P_1)*(1-P_2)*...*(1-P_N). Số lần thử kỳ vọng sẽ không phụ thuộc vào bất cứ điều gì khác ngoài xác suất này, và xác suất này không phụ thuộc vào thứ tự của các màn chơi; do đó số lần thử kỳ vọng không phụ thuộc vào thứ tự các màn chơi, và chúng ta có thể bỏ qua nó khi tính toán thứ tự thực hiện.

Trong trường hợp bạn tò mò về số lần thử kỳ vọng là bao nhiêu: Giả sử chúng ta đang cố gắng thực hiện một việc gì đó có thể thất bại, và chúng ta sẽ tiếp tục thử cho đến khi thành công. Nếu xác suất thành công là P, thì những gì chúng ta đang làm được gọi là Thử nghiệm Bernoulli, lặp lại cho đến khi đạt được thành công. Số lần thử sẽ tuân theo một phân phối ngẫu nhiên gọi là Phân phối Hình học. Giá trị kỳ vọng của phân phối này – số lần thử cần thiết – là 1/P.

Kiến thức về Phân phối Hình học cho phép ta dễ dàng tính số lần thử kỳ vọng. Xác suất vượt qua thành công mọi màn liên tiếp là tích các xác suất thành công; gọi tích này là \(P\). Số lần thử cần thiết có kỳ vọng là \(1/P\). Như đã hứa, con số này không phụ thuộc vào thứ tự mà chúng ta thử các màn chơi, và vì mục tiêu là tìm thứ tự tốt nhất, chúng ta sẽ bỏ qua nó.

Thời gian cho mỗi lần thử

Hãy chọn một thứ tự tùy ý cho các màn chơi. Giả sử màn chơi thứ \(i\) trong số đó mất thời gian \(t_i\), và bạn chết ở màn đó với xác suất \(p_i\) (\(p_i = P_i / 100\)). Trong bất kỳ lần thử nào, bạn chắc chắn sẽ đạt đến màn 1; bạn sẽ đạt đến màn 2 với xác suất \((1-p_1)\); bạn sẽ đạt đến màn 3 với xác suất \((1-p_1)(1-p_2)\); và cứ tiếp tục như vậy.

Dựa trên những tính toán đó, lượng thời gian để thực hiện một lần thử sẽ là:
\(\text{thời gian kỳ vọng} = t_1 + (1-p_1)t_2 + (1-p_1)(1-p_2)t_3 + \dots\)
Điều này là do bạn sẽ chỉ thử màn \(i\) nếu bạn vượt qua \(i-1\) màn đầu tiên.

Bây giờ, hãy xem xét điều gì sẽ xảy ra với thời gian kỳ vọng đó nếu chúng ta tráo đổi màn \(i\) và \(i+1\). Chỉ có hai số hạng trong phương trình thời gian kỳ vọng bị ảnh hưởng — các số hạng khác chỉ đơn giản là đảo ngược thứ tự của \((1-p_i)\) và \((1-p_{i+1})\), điều này không quan trọng. Bản thân hai số hạng đó có một vài thừa số chung:

Trước khi tráo đổi:
\((1-p_1)(1-p_2)\dots(1-p_{i-1})t_i + (1-p_1)(1-p_2)\dots(1-p_{i-1})(1-p_i)t_{i+1}\)

Sau khi tráo đổi:
\((1-p_1)(1-p_2)\dots(1-p_{i-1})t_{i+1} + (1-p_1)(1-p_2)\dots(1-p_{i-1})(1-p_{i+1})t_i\)

Vì vậy, chúng ta sẽ tốt hơn sau khi tráo đổi nếu và chỉ nếu:
\(t_i + (1-p_i)t_{i+1} > t_{i+1} + (1-p_{i+1})t_i\)
\(\Leftrightarrow t_i + t_{i+1} - p_i t_{i+1} > t_{i+1} + t_i - p_{i+1} t_i\)
\(\Leftrightarrow -p_i t_{i+1} > -p_{i+1} t_i\)
\(\Leftrightarrow t_i p_{i+1} > t_{i+1} p_i\)

Bây giờ chúng ta có thể so sánh hai màn chơi kề nhau để xem chúng có nên được tráo đổi hay không. Việc thực hiện điều này một cách tham lam dẫn đến một thuật toán sắp xếp ổn định cho các màn chơi. Với một chút nỗ lực hơn, bạn có thể chứng minh rằng các màn chơi không kề nhau cũng nên được tráo đổi theo cùng các điều kiện, và do đó sắp xếp ổn định là tối ưu.

Chi tiết cài đặt

Bất đẳng thức cuối cùng của chúng ta ở trên nói rằng chúng ta nên tráo đổi nếu \(t_i p_{i+1} > t_{i+1} p_i\). Sẽ rất hấp dẫn nếu tiến thêm một bước nữa thành \(t_i/p_i > t_{i+1}/p_{i+1}\), nhưng chúng ta không thể: \(p_i\) hoặc \(p_{i+1}\) có thể bằng 0, và chia cho 0 không phải là một phép toán hợp lệ.

Một lý do khác để không thực hiện bước cuối cùng đó – mặc dù nó có thể hoạt động nếu bạn xử lý riêng trường hợp \(p_i=0\) để cho kết quả vô hạn – là vì phép chia hầu như chắc chắn khiến chúng ta phải đối mặt với số dấu phẩy động. Trong một bài toán như thế này, nơi chúng ta cố gắng đưa ra quyết định dựa trên các con số, chúng ta muốn đảm bảo rằng mình đang thực hiện các so sánh chính xác. Chúng ta không muốn đảo ngược hai màn chơi tương đương chỉ vì sai số làm cho \(t_i/p_i = 10.0000000001\) và \(t_{i+1}/p_{i+1} = 10.0\).

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