Test Set 1

Giới hạn của Test Set 1 đủ nhỏ để dùng vét cạn. Vì không có lý do gì để giữ quá \(\max_j \mathbf{X}_{i,j}\) đĩa tạ loại \(i\), số trạng thái chồng tạ cần xét rất hạn chế; trên thực tế, con số đó là

Để tìm số thao tác ít nhất cho toàn bộ các bài tập, có thể chạy tìm kiếm theo chiều rộng trên mọi tổ hợp giữa trạng thái chồng tạ và số bài tập đã hoàn thành. Cụ thể, BFS bắt đầu tại trạng thái chồng rỗng, chưa hoàn thành bài tập nào; đáp án là khoảng cách từ trạng thái đó đến trạng thái chồng rỗng và đã hoàn thành tất cả bài tập.

Test Set 2

Nhận xét đầu tiên là: nếu có những đĩa tạ được dùng trong mọi bài tập, luôn tồn tại một phương án tối ưu đặt chúng ở đáy chồng trước bài tập đầu tiên và giữ nguyên ở đó cho đến sau bài tập cuối. Nếu có nhiều đĩa như vậy thì thứ tự giữa chúng không ảnh hưởng. Chính xác hơn, nếu \(C\) là đa tập các đĩa tạ chung cho mọi bài tập, tồn tại một lời giải tối ưu mà trong suốt mọi bài tập, \(C\) nằm ở đáy chồng.

Với một dãy bài tập đầy đủ cho trước, gọi \(A\) là dãy tạ dài nhất xuất hiện ở đáy chồng trong mọi bài tập; \(A\) có thể rỗng. Vì \(A\) được dùng trong mọi bài nên \(A\subseteq C\). Nếu áp dụng nhận xét đầu tiên thì cũng có \(C\subseteq A\), do đó \(A=C\). Suy ra nhận xét thứ hai: nếu có nhiều hơn một bài tập, tồn tại ít nhất một thời điểm giữa hai bài tập mà chồng tạ chứa chính xác \(C\). Điều này gợi đến chia để trị: tìm điểm trung gian ấy, rồi đệ quy tối ưu số thao tác trước và sau điểm đó, không xét lại phần \(C\).

Như thường gặp trong chia để trị, ta có thể tìm vị trí chia mà không cần đệ quy, hoặc dùng ghi nhớ để thử đơn giản mọi điểm chia mà không làm tăng đáng kể thời gian tính toán.

Để hình thức hóa, đặt \(C(\ell,r)\) là đa tập giao của các đa tập tạ cần cho từng bài tập từ \(\ell\) đến \(r\), kể cả hai đầu. Đặt thêm \(M(\ell,r)\) là số thao tác ít nhất để bắt đầu từ một chồng chứa \(C(\ell,r)\) theo thứ tự bất kỳ, thực hiện mọi bài tập từ \(\ell\) đến \(r\), rồi để lại trên chồng đúng \(C(\ell,r)\) theo cùng thứ tự ban đầu.

Để tính \(M(\ell,r)\), ta chọn một điểm giữa \(x\) và áp dụng chiến lược trên hai lần: chất thêm các đĩa cho một nửa, tối ưu bằng kết quả đệ quy, rồi dỡ các đĩa thêm đó. Các đĩa cần thêm cho nửa trái là \(C(\ell,x)\setminus C(\ell,r)\); cho nửa phải là \(C(x+1,r)\setminus C(\ell,r)\). Theo định nghĩa, \(C(\ell,r)\) là đa tập con của cả hai đa tập còn lại. Vì mỗi đĩa thêm vào sau đó phải được lấy ra, phần chi phí ngoài hai lời gọi đệ quy tại điểm chia \(x\) là

Gộp lại, ta có:

• \(M(\ell,r)=0\) nếu \(\ell=r\).
• Nếu \(\ell<r\) thì

Tiền xử lý \(O(\mathbf{E}^2)\) giá trị \(C\) cần \(O(\mathbf{E}^2\times\mathbf{W})\) thời gian. Với ghi nhớ, ta tính \(O(\mathbf{E}^2)\) giá trị \(M\) trong tổng thời gian \(O(\mathbf{E}^3)\). Mức này đủ nhanh cho Test Set 2.

Google Code Jam khuyến nghị luyện gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Lời giải này được dịch đầy đủ từ bản phân tích chính thức của Google Code Jam 2022, Vòng 1A.