Biến đổi bài toán

Mỗi phép trong quy trình kiểm thử có thể được xem là một vector \(M\) chiều; trạng thái kho nguyên liệu hiện tại của Edythe cũng là một vector \(M\) chiều, ban đầu là vector không. Thi triển một phép tương đương cộng vector của phép vào vector kho, rồi đổi mọi tọa độ âm của kho thành 0; thao tác này chính là lấy đúng lượng còn thiếu từ kho Merlin. Mục tiêu là cực đại hóa tổng mọi tọa độ ở cuối.

Ngay cả nếu cho phép Edythe đặt một tọa độ của vector kho về 0 vào bất kỳ lúc nào, cô không bao giờ được lợi khi đặt một tọa độ dương về 0, và không bao giờ bị thiệt khi đặt một tọa độ âm về 0. Vì vậy đáp án không đổi nếu cho cô toàn quyền chọn lúc nào và tọa độ nào được đặt về 0. Từ đây, ta giải bài toán ít ràng buộc hơn này.

Không có lý do đặt cùng một tọa độ về 0 quá một lần, vì lần cuối sẽ khiến mọi lần trước đó trở nên vô nghĩa. Do đó ta có bài toán tương đương: với danh sách phép thuật, được đặt mỗi tọa độ của tổng tích lũy về 0 đúng một lần, tại bất kỳ thời điểm nào trong quá trình cộng, hãy cực đại hóa tổng tọa độ cuối. Một phương án được mô tả bởi một hoán vị của \(N\) phép cùng các thời điểm đặt từng tọa độ về 0.

Duyệt thứ tự đặt 0

Cố định thứ tự các tọa độ được đặt về 0; sau đó sẽ duyệt tất cả \(M!\) thứ tự. Xét một phép cụ thể và tìm thời điểm tốt nhất để thi triển nó. Nếu thi triển trước khi tọa độ nào được đặt về 0, kết quả cuối giống như không thi triển phép ấy, vì mọi tọa độ đều sẽ bị xóa sau đó.

Giả sử thi triển khi đúng \(k\) tọa độ đã được đặt về 0 và các tọa độ còn lại thì chưa. So với việc không thi triển phép, các giá trị của phép trên \(k\) tọa độ đã được đặt 0 sẽ được cộng vào giá trị cuối của chúng; do đó tổng các giá trị này được cộng vào kết quả cuối. Với mỗi phép, thử cả \(M+1\) khả năng của \(k\) và chọn khả năng đóng góp lớn nhất.

Thuật toán là: duyệt mọi hoán vị \(P\) của \(M\) chiều. Với từng \(P\), duyệt mọi phép; với mỗi phép, tìm trong \(M+1\) giá trị \(k\) giá trị tạo đóng góp lớn nhất. Tổng đóng góp tốt nhất của mọi phép là điểm tối ưu cho thứ tự \(P\). Lấy điểm lớn nhất qua mọi thứ tự làm đáp án.

Độ phức tạp

Thời gian là \(O((M+1)!N)\), đủ nhanh với \(N=100\) và \(M=8\).

Nguồn

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