Phân tích

Bài toán này là một bài khá thú vị trong quá trình xây dựng. Trong trò chơi Kingdom Rush thật, mỗi màn có ba ngôi sao, có các màn "thử thách", và bạn không thể thử màn 2 cho đến khi đã vượt qua màn 1 với ít nhất một sao. Việc tạo ra một bài toán vừa giải được, vừa giữ được cảm giác của trò chơi truyền cảm hứng cho nó, là một bài toán cân bằng.

Đầu tiên, hãy quan sát rằng Ryan chỉ nên hoàn thành một màn chơi nếu anh ấy chưa bao giờ hoàn thành nó trước đó, hoặc nếu anh ấy có thể nâng cấp từ xếp hạng 1 sao lên xếp hạng 2 sao. Đơn giản là không có lý do gì để thắng một màn chơi nếu không đạt được thêm sao. Khi nói về các màn chơi dưới đây, chúng ta sẽ bỏ qua các màn chơi mà anh ấy không nên hoàn thành vì lý do này.

Thứ hai, nếu Ryan rơi vào trạng thái không thể hoàn thành bất kỳ màn chơi nào còn lại, thì anh ấy "TOO BAD" để thắng trò chơi. Điều này sẽ xảy ra độc lập với thứ tự mà anh ấy hoàn thành các màn chơi.

Thứ ba, nếu Ryan có thể hoàn thành một màn chơi với xếp hạng 2 sao, anh ấy nên làm điều đó ngay lập tức. Không có lý do gì để anh ấy phải chờ đợi: anh ấy có thể kiếm được 2 sao đó (hoặc 1 sao nếu đã có 1 sao trước đó) chỉ với một lần hoàn thành màn chơi dù là bây giờ hay sau này. Nếu có nhiều màn chơi có thể đạt 2 sao mà Ryan có thể hoàn thành, anh ấy có thể chọn bất kỳ màn nào; anh ấy có thể làm màn còn lại ngay sau đó.

Bây giờ chúng ta đã bao quát tất cả các tình huống ngoại trừ một tình huống: khi các màn chơi duy nhất Ryan có thể hoàn thành là các màn mà anh ấy chỉ có thể đạt được xếp hạng 1 sao. Hãy xem xét hai màn chơi như vậy, màn 0 và màn 1:

a0 b0
a1 b1

Hãy nhớ rằng mục tiêu của Ryan là hoàn thành các màn chơi với số lần tối thiểu. Trong trường hợp xấu nhất, Ryan sẽ mất 4 lần hoàn thành để xong hai màn này: hai lần để đạt 1 sao ở cả hai màn, và thêm hai lần nữa để đạt 2 sao ở cả hai màn. Nhưng việc kiếm sao từ các màn này (hoặc các màn khác) có thể cho phép anh ấy hoàn thành một trong số chúng với xếp hạng 2 sao mà không cần phải hoàn thành nó với xếp hạng 1 sao trước.

Đây là một chuỗi sự kiện có thể xảy ra. Giả sử Ryan bắt đầu với \(S\) sao. Chúng ta sẽ quyết định sau xem \(k\) là 0 hay 1:

1. Ryan hoàn thành màn \(k\) với xếp hạng 1 sao và kiếm được 1 sao.
2. Ryan hoàn thành các màn khác và kiếm được \(s\) sao.
3. Ryan hoàn thành màn \(1-k\) với xếp hạng 2 sao trực tiếp.

Lựa chọn \(k\) nào làm cho kịch bản này khả thi? Nếu \(k=0\), điều này khả thi khi và chỉ khi \(S + 1 + s \ge b_1\). Nếu \(k=1\), điều này khả thi khi và chỉ khi \(S + 1 + s \ge b_0\). Vì \(b_0 < b_1\), nên nếu kịch bản khả thi với \(k=0\) thì nó chắc chắn khả thi với \(k=1\). Do đó, chúng ta nên chọn \(k=1\), tức là Ryan chọn màn chơi có giá trị \(b\) lớn nhất.

Tóm lại, chiến lược của Ryan nên là:

1. Trong khi vẫn còn bất kỳ màn chơi nào mà Ryan chưa hoàn thành, hoặc bất kỳ màn nào anh ấy có thể kiếm được xếp hạng cao hơn mức đã có:
   • Nếu anh ấy có thể kiếm được xếp hạng 2 sao ở bất kỳ màn nào trong số đó, anh ấy nên hoàn thành một trong những màn đó (chọn tùy ý).
   • Ngược lại, nếu có một tập hợp các màn mà anh ấy có thể kiếm được xếp hạng 1 sao, anh ấy nên hoàn thành màn có giá trị \(b\) lớn nhất trong số đó.
   • Nếu không thể thực hiện cả hai điều trên, Ryan không thể hoàn thành trò chơi.
2. Nếu Ryan đã thắng tất cả các màn với xếp hạng 2 sao, anh ấy đã xong. Ngược lại, anh ấy "Too Bad".

Bằng cách mô phỏng chiến lược này, chúng ta có thể xác định Ryan có thể thắng Kingdom Rush hay không, và nếu có thì số lần hoàn thành màn chơi nhỏ nhất là bao nhiêu.

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