Có hai loại chương trình: chương trình kết thúc và chương trình không kết thúc!

Với bất kỳ chương trình nào không lặp vô hạn vì cuối cùng chạy hết danh sách, đều có một chương trình tương đương không dùng lệnh G; đó cũng là cách ngắn nhất để viết hành vi ấy. Tương tự, nếu chương trình lặp vô hạn, có một chương trình tương đương chỉ gồm các lệnh di chuyển và đúng một lệnh G ở cuối; đây cũng là dạng ngắn nhất.

Vì vậy chỉ cần xét hai trường hợp: toàn lệnh di chuyển, hoặc một lệnh G duy nhất nằm cuối. Đáp án là chương trình ngắn nhất trong tất cả các trường hợp đó.

Chương trình loại thứ nhất được tìm dễ dàng bằng BFS từ M tới N, tránh các ô #. Nếu BFS không tới được N, bài toán là IMPOSSIBLE.

Chương trình có một vòng lặp

Loại thứ hai khó hơn. Tách chương trình thành hai đoạn tạo ra hai đường đi: đường đầu \(P\) do các lệnh không lặp tạo nên, rồi đường \(Q\) lặp lại cho đến khi tới N. Gọi \(B\) là điểm kết thúc \(P\). BFS như trên cho đường \(P\) ngắn nhất tới mọi khả năng của \(B\).

Trong lần đầu đi qua \(Q\), Marlin đi qua một mẫu ô nào đó. Lần thứ hai, cậu đi qua cùng mẫu nhưng tịnh tiến bởi vectơ độ dời \(D\). Quá trình tiếp tục qua một số lần lặp \(K\) cho tới khi tới ô N.

Do đó lần đầu của \(Q\) đưa Marlin từ \(B\) tới \(B+D\). Đường đi không chỉ phải tránh ô #, mà còn phải tránh mọi ô có một bản sao tương ứng trong lần lặp về sau là #. Ngoài ra, lần đầu của \(Q\) phải chứa một ô mà ở lần lặp sau nào đó sẽ trở thành N. Khó thỏa các điều kiện nếu chưa biết \(D\) và \(K\), nên ta liệt kê mọi khả năng của chúng. Với mỗi cặp \(D,K\), ta tìm chương trình ngắn nhất cho đồng thời mọi \(B\).

Tách \(Q\) thành hai đường

Tách \(Q\) thành \(Q_1\) và \(Q_2\). \(Q_1\) chứa các lệnh được lặp \(K\) lần và chạm ô N ở lần cuối; \(Q_2\) chứa các lệnh chỉ được lặp \(K-1\) lần. Nếu N được chạm đúng cuối một vòng thì \(Q_2\) rỗng.

Gọi \(n\) là tọa độ ô mang ký tự N. Khi đó \(Q_1\) là đường từ \(B\) tới \(n-(K-1)D\), còn \(Q_2\) là đường từ \(n-(K-1)D\) tới \(B+D\).

\(Q_1\) chỉ được đi qua ô \(X\) sao cho \(X+iD\) trống với mọi \(0<i<K\). Chạy BFS bắt đầu từ \(n-(K-1)D\) trên các ô hợp lệ này để tìm \(Q_1\) tối ưu cho mọi \(B\).

\(Q_2\) chỉ được đi qua ô \(X\) sao cho \(X+iD\) trống với mọi \(0<i<K-1\). Chạy một BFS khác từ \(n-(K-1)D\) trên tập ô này để tìm \(Q_2\) tối ưu cho mọi \(B\).

Cuối cùng duyệt mọi ô \(B\), cộng độ dài đường ngắn nhất \(P,Q_1,Q_2\) và thêm 1 cho lệnh G.

Độ phức tạp

Đặt \(N=\max(R,C)\). Vòng ngoài có vẻ có \(O(N^2)\) vectơ \(D\) và \(O(N)\) giá trị \(K\), nhưng không phải mọi tổ hợp đều khả thi. Khi \(K\) lớn, độ dời mỗi vòng phải nhỏ, nếu không đường đi sẽ rời lưới trước khi hoàn thành \(K\) vòng. Tổng số cặp \(D,K\) hợp lệ là \(O(N^2)\); phân tích chính thức để phần chứng minh này như một bài tập.

Bên trong mỗi lượt, dựng các lưới hợp lệ cho BFS, chạy hai BFS và thử mọi \(B\) đều tốn \(O(N^2)\). Vì vậy toàn bộ vòng lặp tốn \(O(N^4)\). BFS ngoài vòng để tính mọi \(P\) tối ưu tốn \(O(N^2)\), và việc tìm lời giải không dùng G cũng vậy. Tổng độ phức tạp là \(O(N^4)\), đủ cho cả hai Test Set.

Nếu kém cẩn thận, chẳng hạn tốn \(O(K)\) để kiểm tra một ô có hợp lệ cho mỗi BFS bên trong hay không, lời giải thành \(O(N^5)\); vẫn đủ cho Test Set 1. Vét cạn theo cấp số nhân mọi khả năng của \(Q\) khó có thể qua ngay cả Test Set 1 vì độ dài tối đa của \(Q\) quá lớn.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2019, Chung kết thế giới, bài Go To Considered Helpful; kho Google Coding Competitions (Apache-2.0).