Test Set 1

Vì trong test set này có nhiều nhất một lệnh C, ta có thể giải riêng hai trường hợp.

Nếu \(P\) không có lệnh C, không phép đổi chỗ nào tạo ra khác biệt; ta chỉ có thể kiểm tra liệu sát thương của tia có vượt quá \(D\) hay không.

Nếu \(P\) có đúng một lệnh C, ta thử mọi vị trí có thể của lệnh C trong chương trình. Giả sử tồn tại ít nhất một vị trí khiến tổng sát thương không vượt quá \(D\), ta chọn phương án cần ít phép đổi chỗ nhất. Số phép đổi cần cho một phương án chính là khoảng cách giữa vị trí ban đầu và vị trí cuối cùng của lệnh C.

Test Set 2

Để giải Test Set 2, trước hết ta suy ra công thức tính tổng sát thương từ vị trí các lệnh C và S trong \(P\). Gọi \(N_C\) và \(N_S\) lần lượt là số lệnh C và S trong \(P\). Gọi \(C_i\) là số lệnh S nằm bên phải lệnh C thứ \(i\), với \(i\) được đánh số từ 1.

Lệnh C thứ \(i\) làm sát thương của các phát bắn sau nó tăng thêm \(2^{i-1}\). Ví dụ, với chương trình CSSCSSCSS, ban đầu mỗi lệnh S đều gây 1 sát thương. Xét sát thương của lệnh S cuối cùng: vì robot đã được nạp năng lượng hai lần, lệnh cuối gây 4 sát thương. Cũng có thể phân tích \(4=1\) (sát thương ban đầu) \(+2^0\) (phần do lệnh C thứ nhất tạo ra) \(+2^1\) (phần do lệnh C thứ hai tạo ra). Phân rã sát thương của từng lệnh S theo cùng cách, tổng sát thương \(D\) của chương trình đầu vào được cho bởi:

  D = NS + C1 × 1 + C2 × 2 + ... + CNC × 2NC - 1 .

Tiếp theo, ta xét ảnh hưởng của từng phép đổi chỗ lên sát thương. Đổi hai ký tự kề nhau giống hệt nhau không làm thay đổi công thức. Khi đổi lệnh C thứ \(i\) với một lệnh S bên phải nó, \(C_i\) giảm 1 vì lúc này có ít hơn trước một lệnh S ở bên phải. Ngược lại, đổi lệnh C thứ \(i\) với một lệnh S bên trái làm \(C_i\) tăng 1. Trong cả hai trường hợp, chỉ \(C_i\) thay đổi, còn mọi giá trị \(C\) khác được giữ nguyên. Điều này gợi ý rằng ta chỉ nên đổi các cặp lệnh kề nhau có dạng CS.

Vì vậy, thực hiện \(M\) phép đổi tương đương với giảm các giá trị \(C_i\) sao cho tổng lượng giảm trên mọi \(C_i\) bằng \(M\). Ta muốn tổng sát thương theo công thức trên nhỏ nhất. Rõ ràng, nên ưu tiên giảm những \(C_i\) đóng góp lượng sát thương lớn nhất, đồng thời bảo đảm mọi \(C_i\) vẫn không âm.

Trực giác đằng sau toàn bộ phần toán học trên dẫn đến một thuật toán rất đơn giản: chừng nào chương trình hiện tại còn cặp CS, ta luôn đổi cặp xuất hiện muộn nhất, tức cặp ngoài cùng bên phải. Sau mỗi lần đổi, tính lại sát thương và kiểm tra nó còn lớn hơn \(D\) hay không; nếu không, có thể kết thúc. Nếu không còn cặp CS nào để đổi mà chương trình vẫn gây sát thương lớn hơn \(D\), vũ trụ đã hết hy vọng.

Nguồn

Dịch đầy đủ từ phân tích chính thức của Google Code Jam 2018, Vòng loại, bài Saving The Universe Again; kho Google Coding Competitions Archive (Apache-2.0).