Phân tích

Gọi \(D_{i,j}\) là chữ số của khối có đúng \(j\) khối bên dưới trong tháp \(i\). Số trên tháp \(i\) là

và tổng điểm là

Mỗi hạng độc lập: mỗi vị trí có trọng số cố định nhân với chữ số; đổi các khối cùng độ cao giữa tháp không đổi kết quả. Muốn tối đa điểm, ghép chữ số lớn với trọng số lớn, tức đặt chữ số lớn gần đỉnh.

Trọng số một vị trí lớn hơn \(9\) lần tổng trọng số mọi vị trí bên dưới. Vì vậy, trì hoãn dùng một vị trí để chờ chữ số tối đa có thể đáng giá ngay cả khi phải hy sinh quyền sắp các vị trí dưới của tới \(9\) tháp, thậm chí nhiều hơn vì thứ tự ngẫu nhiên vẫn sinh điểm. Mọi cách sau đều dành vị trí giá trị cao cho chữ số cao, hy sinh phần còn lại.

Chiến lược tham lam

Cách đơn giản nhất: cố đặt \(9\) ở vị trí đỉnh mọi tháp và hy sinh mọi thứ khác. Khi khối là \(9\), đặt vào tháp chưa hoàn tất cao nhất. Nếu không, đặt vào tháp cao nhất còn ít hơn \(B-1\) khối. Cách này giữ chỗ đỉnh cho \(9\) và nhanh chóng mở thêm vị trí đỉnh bằng cách xây tháp sớm.

Các biến thể có thể dành hai vị trí trên cùng cho \(9\), rồi chuyển sang chỉ dành đỉnh khi sắp hết lượt; hoặc chấp nhận chữ số thấp hơn ở vị trí áp đỉnh/đỉnh khi còn ít khối và xác suất nhận đủ \(9\) thấp.

Các tham lam đơn giản dao động từ \(87\%\) đến \(91\%\) của \(S\); nhiều cách qua Test Set 1 nhưng không gần đủ Test Set 2. Heuristic tinh vi hơn có thể qua Test Set 2, nhưng phải xét ít nhất hai vị trí trên cùng, xử lý cả \(8\) lẫn \(9\), cần tinh chỉnh và không chắc chắn. Quy hoạch động sau vừa bảo đảm điểm vừa có thể tiết kiệm thời gian phát triển.

Chiến lược quy hoạch động

Một hướng là tối đa hóa điểm kỳ vọng. Điều này không đúng hoàn toàn với tối đa xác suất vượt một ngưỡng — gần cuối có thể nên táo bạo hay bảo thủ tùy khoảng cách tới ngưỡng — nhưng rất gần và đơn giản hơn.

Lời giải kỳ vọng tối ưu đạt \(S\) quá chậm, nhưng là điểm xuất phát. Theo tính tuyến tính của kỳ vọng, khi chọn tháp cho khối, chỉ đa tập chiều cao tháp quan trọng; các chữ số đã đặt không ảnh hưởng quyết định tương lai vì phần điểm đó chắc chắn nhận được. Dùng trạng thái là đa tập chiều cao và hàm \(f(\text{state},\text{next digit})\) thử mọi vị trí cho từng chữ số kế. Không gian trạng thái quá lớn; đây là cách tính \(S\), nhưng phải chạy lâu hơn giới hạn rất nhiều.

Giảm trạng thái bằng cách bỏ qua vị trí giá trị thấp. Ví dụ, với mỗi chữ số chỉ cho phép hai lựa chọn của tham lam đầu: đặt vào vị trí đỉnh của một tháp, hoặc vào tháp cao nhất có ít hơn \(B-1\) khối. Khi đó chỉ một tháp có thể có chiều cao khác \(0,B-1,B\). Không chọn tham lam mà để DP chọn giữa hai phương án. Cách này đủ nhanh và đạt khoảng \(96\%S\), chưa đủ Test Set 2 nhưng gần hơn.

Nếu tương tự nhưng để hai vị trí trên cùng cho DP tối ưu, điểm vượt \(99{,}5\%S\) và qua Test Set 2.

Vị trí đỉnh chiếm gần \(90\%\) giá trị nên tối ưu nó đạt khoảng \(90\%\) điểm; hai vị trí trên chiếm gần \(99\%\). Xét hai bài sửa đổi giữ giá trị ở đỉnh hoặc hai vị trí trên và đặt mọi vị trí khác bằng \(0\). Các lời giải đạt điểm kỳ vọng tối đa \(S_1,S_2\) cho hai bài đó, với \(S_1>0{,}9S\), \(S_2>0{,}99S\). Vì vậy kỳ vọng được bảo đảm trên các ngưỡng tương ứng; điểm thêm từ vị trí thấp tạo khoảng an toàn. Ước lượng xác suất thất bại mỗi lời giải nhỏ hơn \(10^{-10}\).

Dựa trên phân tích chính thức của Google Code Jam 2021, Vòng 1B, bài Digit Blocks.