Phân tích: Cookie Clicker Alpha

Trong bài toán này, chúng ta cần quyết định số lượng trang trại bánh quy cần mua và thời điểm mua chúng.

Chiến thuật có lẽ đơn giản đến bất ngờ: đầu tiên, thu thập đủ bánh quy để mua một trang trại. Sau đó, tính toán xem việc mua một trang trại rồi sau đó mới thu thập \(X\) bánh quy sẽ nhanh hơn, hay chỉ đơn giản là thu thập \(X\) bánh quy ngay bây giờ sẽ nhanh hơn. Nếu thu thập \(X\) bánh quy ngay bây giờ nhanh hơn, bạn nên làm điều đó. Nếu mua một trang trại trước nhanh hơn, hãy mua trang trại đó và lặp lại quá trình này (thu thập đủ bánh quy để mua trang trại tiếp theo...).

Nói thì rất dễ, nhưng chứng minh nó hoạt động thì không đơn giản. Bạn có thể mua bao nhiêu trang trại? Nếu con số lên đến hàng tỷ, chương trình của bạn có thể quá chậm. Chúng ta cũng chưa chứng minh được rằng việc mua trang trại ngay lập tức khi có đủ bánh quy là tốt nhất. Phần còn lại của bài phân tích này sẽ đi sâu vào các câu hỏi đó.

Chúng ta xây dựng trực giác cho lời giải bằng hình học. Biểu diễn bài toán trên mặt phẳng 2D. Trục x đại diện cho thời gian (giây) và trục y đại diện cho số lượng bánh quy. Ban đầu, chúng ta nhận được bánh quy với tốc độ 2 chiếc mỗi giây, được biểu diễn bởi đường thẳng \(L_0\) trong Hình 1. Giả sử số bánh quy mục tiêu (\(X\)) là 16. Chúng ta có thể biểu diễn nó bằng đường thẳng \(y=16\) (\(L_X\)). Điều này có nghĩa là nếu không mua trang trại nào, thời gian để có 16 bánh quy được cho bởi giao điểm giữa \(L_X\) và \(L_0\). Xem Hình 1.

Hình 1

Bây giờ, hãy tìm hiểu điều gì xảy ra (về mặt hình học) khi chúng ta mua một trang trại. Giả sử chi phí mua trang trại (\(C\)) là 6, và số bánh quy tăng thêm mỗi giây (\(F\)) là 2. Trong Hình 2, chúng ta mua một trang trại ngay khi có 6 bánh quy. Nghĩa là tại thời điểm \(t = 3\), số bánh quy từ 6 giảm xuống 0 (để trả cho trang trại), và tốc độ sản xuất tăng lên 4. Thông tin này được biểu diễn bởi \(L_1\) trong Hình 2. Lưu ý các đường đứt nét biểu thị sự sụt giảm bánh quy hiện có khi mua trang trại. Lưu ý rằng \(L_0\) và \(L_1\) cắt nhau tại mốc 6 giây (tương ứng với \(X=12\) bánh quy). Điều đó có nghĩa là, nếu mục tiêu \(X\) nằm trong khoảng từ 0 đến 12 thì việc mua trang trại là không có lợi! Tại sao? Hãy nhìn vào đường \(L_Xa\) ví dụ trong phạm vi đó. Trong Hình 2, \(L_0\) cắt \(L_Xa\) sớm hơn (tại mốc 4 giây) so với \(L_1\) cắt \(L_Xa\) (tại mốc 5 giây). Tại \(X = 12\) (biểu diễn bởi \(L_Xb\)), việc mua hay không mua trang trại không quan trọng. Nhưng nếu \(X\) cao hơn 12, ví dụ \(X = 16\) (biểu diễn bởi \(L_X\)), chúng ta nên mua trang trại vì \(L_1\) cắt \(L_X\) sớm hơn (tại mốc 7 giây) so với \(L_0\) (tại mốc 8 giây). Nhìn nhanh về phía trước, chúng ta thấy hành vi tương tự cho giao điểm giữa \(L_1\), \(L_2\) và \(L_X\) trong Hình 4. Nếu chọn \(X = 18\), việc chọn \(L_1\) hay \(L_2\) không quan trọng, nhưng nếu \(X\) dưới 18 thì giao điểm \(L_1\) tốt hơn \(L_2\), còn nếu \(X\) trên 18 thì giao điểm \(L_2\) tốt hơn \(L_1\).

Hình 2

Bây giờ chúng ta thảo luận về chiến thuật nên mua trang trại sớm đến mức nào, tức là nên mua ngay khi có \(C\) bánh quy hay nên đợi thêm một chút? Chúng tôi khẳng định rằng nên mua trang trại ngay khi có \(C\) bánh quy (và không đợi thêm giây nào).

Hình 3

Trong Hình 3, như trước, \(L_1\) biểu thị việc mua trang trại ngay khi có 6 bánh quy (tại giây thứ 3), trong khi \(L_1a\) biểu thị việc trì hoãn mua trang trại thêm một giây (tại giây thứ 4). Lưu ý rằng \(L_1\) và \(L_1a\) song song với nhau (cùng tốc độ: 4 bánh quy/giây) nhưng \(L_1\) nằm bên trái \(L_1a\). Điều này có nghĩa là giao điểm giữa bất kỳ đường \(L_X\) nào với \(L_1\) sẽ luôn ở thời điểm sớm hơn so với giao điểm với \(L_1a\). Do đó, không nên đợi để mua trang trại lâu hơn mức cần thiết. Điều này có nghĩa là nếu việc mua trang trại đóng góp vào chiến thuật chiến thắng của bạn, thì bạn nên mua nó càng sớm càng tốt, tức là ngay khi có \(C\) bánh quy.

Trong Hình 4, chúng ta có thể thấy thời điểm sớm nhất để mua trang trại đầu tiên là giao điểm của đường \(L_0\) với đường \(L_C\) (\(y=C\)). Sau đó, thời điểm sớm nhất để mua trang trại thứ hai là giao điểm của đường \(L_1\) với \(L_C\).

Hình 4

Bây giờ, chúng ta đã sẵn sàng mô tả chiến thuật giải quyết. Đầu tiên, xác định thời gian \(t_0\) để có \(X\) bánh quy mà không mua trang trại nào (giao điểm giữa \(L_0\) và \(L_X\)). Sau đó, thử mua 1 trang trại và tính thời gian \(t_1\) để có \(X\) bánh quy (giao điểm giữa \(L_1\) và \(L_X\)). Tiếp theo tính \(t_2\) cho việc mua thêm một trang trại nữa (giao điểm giữa \(L_2\) và \(L_X\)), và cứ tiếp tục như vậy. Chúng ta dừng lại khi \(t_{n+1} > t_n\) (tức là chúng ta làm tệ hơn về mặt thời gian nếu mua thêm trang trại). Ví dụ, trong Hình 4, chúng ta làm tệ hơn với \(L_2\) so với \(L_1\). Cuối cùng, báo cáo \(t_n\) là thời gian chiến thắng.

Lưu ý về việc tính toán giao điểm đường thẳng: Chúng ta muốn tính giao điểm giữa các đường \(L_0, L_1, L_2,...\) và \(y = C\) hoặc \(y = X\). Giả sử đường hiện tại \(L_n\) bắt đầu tại \((S_n, 0)\) và có độ dốc \(m\) (tốc độ bánh quy sau khi mua \(n\) trang trại). Lưu ý \(S_0 = 0\), và \(m = 2 + n \times F\). Khi đó thời gian cần thiết để có \(A\) bánh quy là: \(S_n + A / m\).

Chiến thuật của chúng ta lặp cho đến khi đạt điều kiện thắng. Nhưng bạn có thể thắc mắc về tổng số lần lặp cần thiết. Số lần lặp là hữu hạn. Điều kiện dừng là khi \(t_{i+1} > t_i\).
Gọi \(t_i = s_i + X / (2 + i \times F)\) và \(t_{i+1} = s_{i+1} + X / (2 + (i + 1) \times F)\).
Ta có \(s_{i+1} - s_i = C / (2 + i \times F)\).
Sau khi tính toán, ta có \(t_{i+1} > t_i\) khi \(i > (X / C) - 1 - (2 / F)\). Do đó, số lần lặp sẽ kết thúc quanh giá trị \(X / C\).

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