Tổng quan và chuẩn hóa

Bài cho một phiên bản của một ngôn ngữ lập trình nhỏ và yêu cầu theo dõi số thao tác được thực thi khi chương trình chạy. Bộ nhớ là mảng vòng gồm \(2^{40}\) vị trí; mọi giá trị được xét modulo 256. Để thuận tiện, dịch các giá trị 1..256 đi một đơn vị thành 0..255. Chương trình có thể chạy cực lâu, nên ta mô phỏng hiệu quả bằng cách gom nhiều thao tác. Mã thực tế dài và phức tạp — đây là bài cuối của vòng chung kết — nên phân tích chính thức chỉ trình bày tổng quan ý tưởng chính.

Phân tích chương trình thành năm phần \(A(B)C(D)E\); một số phần có thể rỗng, và trong bộ nhỏ \(D,E\) luôn rỗng. Bằng mô phỏng, mỗi dãy lệnh đơn giản được chuyển thành một lệnh phức hợp:

1. Gọi \(i\) là vị trí hiện tại.
2. Cộng \(x_j\) vào vị trí \(i+j\) với mọi \(j\in[-2000,2000]\) (2000 là độ dài tối đa của mỗi phần).
3. Chuyển vị trí hiện tại tới \(i+k\), trong đó \(k\in[-2000,2000]\).

Chạy \(A\)

Sau khi chạy \(A\), chỉ các giá trị cách vị trí bắt đầu không quá 2000 có thể bị thay đổi. Gọi đây là vùng “đỏ”.

Chạy \((B)\)

Sau một số lần chạy \(B\), vòng lặp sẽ kết thúc, hoặc xe đi ra khỏi vùng đỏ. Sau thêm một số lượt ở bên ngoài, bộ nhớ ngoài vùng đỏ bắt đầu tuần hoàn với chu kỳ \(|k|\). Xe tiếp tục dịch theo \(k\) ở bước 3 của phép biến đổi \(B\) cho đến khi quay lại vùng đỏ từ phía đối diện, hoàn tất một vòng tròn.

Ta gom toàn bộ các lệnh cần để hoàn thành vòng tròn, và biểu diễn vùng không đỏ như sự lặp lại của một chu kỳ dài nhiều nhất 4001 (số giá trị \(j\) trong bước 2). Tiếp tục làm như vậy cho tới khi vòng lặp kết thúc, điều mà đầu vào bảo đảm.

Sau nhiều nhất 4001 vòng tròn hoàn chỉnh quanh bộ nhớ, các vị trí bắt đầu bên trong vùng đỏ sẽ lặp lại. Khi đó các giá trị ở đó cũng bắt đầu lặp, nên không thể thực hiện quá \(4001\times256\) lượt lặp mà không trở thành vòng lặp vô hạn; đầu vào cấm trường hợp vô hạn.

Chạy \(C\)

Sau đó mô phỏng \(C\). Vì vòng trước kết thúc trong phạm vi 2000 quanh điểm đầu, \(C\) có thể sửa phạm vi \([-4000,4000]\). Gọi đây là vùng “xanh”.

Chạy \((D)\)

Với \(D\), hiện tượng tương tự \(B\) xảy ra, nhưng bộ nhớ ngoài vùng xanh lúc này là tổng của hai cấu trúc tuần hoàn có chu kỳ dài nhiều nhất 4001, nên chu kỳ tổng có thể dài tới \(4001^2\). May mắn là kích thước này vẫn đủ nhỏ để mô phỏng; ngoài điểm đó, dùng đúng ý tưởng của \(B\).

Chạy \(E\)

Xử lý \(E\) theo cùng cách. Vùng không tuần hoàn lúc này có thể tăng tới vài triệu ô do chu kỳ bậc hai của vòng lặp trước, nhưng vẫn thấp hơn nhiều so với giới hạn bộ nhớ.

Nguồn

Bản dịch dựa trên phân tích chính thức Google Code Jam 2015 - World Finals - Crane Truck, kho Google Coding Competitions (Apache-2.0).