Test Set 1

Các giới hạn của Test Set 1 vẫn đủ lớn để đánh bại việc mô phỏng thuần túy mọi lựa chọn, nên cần một số nhận xét trước:

• Rồng chỉ nên Cure khi bị buộc phải làm vậy: đòn kế tiếp của hiệp sĩ sẽ hạ nó, và Attack hoặc Debuff cũng không ngăn được điều đó. Nếu chưa bị buộc, làm hành động khác luôn tốt hơn.
• Mọi Buff nên đứng trước mọi Attack, để mỗi đòn đánh của rồng đều hưởng lợi từ tất cả Buff.
• Số Buff quyết định trực tiếp số Attack cần thiết.
• Mọi Debuff nên đứng trước mọi Buff/Attack, để tổng sát thương rồng phải chịu là nhỏ nhất.
• Nếu đòn đầu tiên của hiệp sĩ sẽ hạ rồng ngay cả khi rồng Attack hoặc Debuff ở lượt đầu, bộ test là không thể.
• Nếu rồng bị buộc Cure trong hai lượt liên tiếp, bộ test là không thể, vì điều đó có nghĩa nó sẽ phải Cure ở mọi lượt.

Các nhận xét này cho chiến lược: dành \(D'\) lượt Debuff, rồi \(B'\) lượt Buff, rồi \(A'\) lượt Attack, và xen Cure đúng lúc cần để không bị hạ. Vì \(B'\) quyết định \(A'\), chỉ cần xét các cặp \((D',B')\). Do \(A_k\) không vượt 100, không có lý do thực hiện quá 100 Debuff hay 100 Buff; hơn nữa, trường hợp tệ nhất không thể cần quá vài trăm lượt \(D'+B'+A'\). Có thể suy ra các cận nhỏ hơn với thêm một chút suy nghĩ, nhưng như vậy đã đủ thấy mô phỏng trực tiếp chạy nhanh cho Test Set 1.

Ta chuyển chiến lược trên thành mã, chú ý ưu tiên hành động đúng thứ tự; đặc biệt phải tránh Cure khi chưa cần và cũng không được quên Cure lúc bắt buộc. Mô phỏng từng cặp \((D',B')\), lấy số lượt nhỏ nhất toàn cục, hoặc kết luận IMPOSSIBLE.

Test Set 2

Như đã thấy, mọi Debuff đứng trước mọi Buff/Attack, còn số Buff quyết định số Attack. Thực ra phần Buff/Attack độc lập với phần Debuff. Thay đổi số Debuff có thể thay đổi số Cure, nhưng dù Debuff bao nhiêu lần, dùng nhiều hơn số lượt Buff + Attack tối thiểu không mang lại lợi ích; nó chỉ khiến ta lãng phí thêm lượt Cure.

Để tìm số lượt Buff + Attack tối thiểu, trước hết giả sử Buff 0 lần và tính số Attack cần để hạ hiệp sĩ. Sau đó liên tục tăng \(B'\) thêm 1 và tính số lượt Attack \(A'\) cần ở mức sức tấn công mới. Ngay khi tổng bắt đầu lớn hơn, có thể dừng và lấy tổng trước đó. Điều này an toàn vì tổng là

Phần \(B'\) là một đường thẳng có độ dốc dương; phần còn lại là một hàm bậc thang giảm dần. Nếu hàm bậc thang ấy là một đường cong trơn, sẽ có một điểm mà tốc độ giảm của đường cong đúng bằng tốc độ tăng của phần tuyến tính, và hàm đạt cực tiểu tại đó. Do tính rời rạc, có thể có nhiều giá trị \(B'\) cùng cho số lượt \(B'+A'\) tối thiểu, nhưng chọn giá trị nào cũng không quan trọng; ta chỉ cần tổng.

Cách tìm này tốn \(O(\sqrt N)\), với \(N\) là cận chung của mọi tham số (\(10^9\) ở Test Set 2). Khi \(B'\) đã tăng tới khoảng \(\sqrt N\), ta có thể hạ hiệp sĩ trong khoảng \(\sqrt N\) lượt Attack, nên không cần Buff thêm. Cũng có thể giải phần này bằng tìm kiếm nhị phân, tìm kiếm tam phân, hoặc giải phương trình bậc hai.

Còn số Debuff \(D'\) thì sao? Nhận xét then chốt là không cần xét mọi giá trị. Ví dụ, giả sử \(H_d=100\), \(A_k=50\), \(D=1\). Giảm \(A_k\) xuống 49 (mất 1 lượt Debuff) cũng tốt như giảm xuống 48 hay 34: trong mọi trường hợp đó, rồng vẫn phải Cure cách một lượt. Nhưng giảm \(A_k\) xuống 33 (mất 17 lượt Debuff) khiến rồng chỉ phải Cure sau mỗi ba lượt. Vì vậy chỉ cần xét các ngưỡng \(D'=0,1,17,26,31,\ldots\) và bỏ các giá trị khác. Mỗi ngưỡng kế tiếp có thể được tính bằng công thức trong thời gian hằng số.

Sau khi có các ngưỡng, thậm chí không cần mô phỏng chúng độc lập. Mô phỏng với \(D'=17\) ban đầu giống mô phỏng với \(D'=1\), vì phải thực hiện Debuff đầu tiên trước 16 Debuff còn lại. Ta thực hiện một mô phỏng duy nhất, giữ số lượt \(T\) đã dùng, rồi lặp:

• Giả sử không Debuff thêm. Tính số lượt bổ sung để Buff + Attack, kèm đủ Cure để sống sót. So sánh tổng đó cộng \(T\) với đáp án tốt nhất đã thấy.
• Tính số lượt cần để tăng số Debuff tới ngưỡng kế tiếp, kèm đủ Cure để sống sót, rồi cộng vào \(T\).

Debuff thêm tốn lượt, nhưng có thể “hoàn vốn” bằng cách giảm số Cure trong giai đoạn Buff + Attack. Chiến lược trên tìm đúng sự cân bằng.

Không cần thật sự mô phỏng từng lượt. Do các ngưỡng \(D'\) đã được chọn sao cho trong quãng Debuff giữa hai ngưỡng, tần suất Cure không đổi, ta tính tổng số lượt Debuff + Cure bằng công thức; số Cure trong giai đoạn Buff + Attack cũng tính được tương tự. Nhờ vậy bước này là \(O(\sqrt N)\). Kết hợp với \(O(\sqrt N)\) để tìm số lượt Buff + Attack tối ưu, toàn bộ thuật toán là \(O(\sqrt N)\).

Phần còn lại là cài đặt, có lẽ còn khó hơn việc nghĩ ra thuật toán vì có rất nhiều cơ hội phạm lỗi lệch một. Dù điều này không thường xảy ra trong Code Jam, riêng bài này có giới hạn đủ rộng để những lời giải chỉ dùng một phần các nhận xét trên, cộng thêm tối ưu cấp thấp, vẫn vượt qua được giới hạn tám phút ban đầu của cuộc thi.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2017, Round 1A, bài Play the Dragon.