Đây là một bài rất khó với nhiều cạm bẫy cần lưu ý.

Test Set 1 (Hiển thị)

Vét cạn thuần túy là đủ. Có nhiều cách thực hiện; một cách trực quan là liên tục cố tạo thêm một gram chì.

Giả sử Create(i) nhận kim loại \(i\) và trả về đúng nếu tạo được một gram kim loại ấy. Trước hết, nếu lượng kim loại \(i\) hiện còn dương, lấy một gram và trả về đúng. Nếu không, gọi đệ quy Create(P) và Create(Q), với \(P,Q\) là hai nguyên liệu tạo \(i\). Nếu cả hai lời gọi thành công thì trả về đúng, nếu không thì trả về sai. Gọi Create(1) cho đến lần đầu thất bại; số lần thành công, cộng với lượng chì ban đầu đã được lấy qua các lời gọi, là đáp án.

Cần hoàn tác mọi thay đổi kho khi một nhánh thất bại. Ngoài ra, phiên bản ngây thơ có thể không kết thúc khi không còn tạo được chì. Ví dụ có 3 kim loại, mỗi kim loại được tạo từ hai kim loại còn lại, kho đều bằng 0: quá trình sẽ quay lại yêu cầu chì mãi mãi. Có thể đánh dấu kim loại đã xuất hiện trên ngăn xếp gọi hiện tại; nếu lại gặp nó trong lúc đang khai triển nguyên liệu của chính nó thì không thể tạo kim loại ấy. Một cách dễ cài hơn là giới hạn độ sâu đệ quy ở \(M\), vì sau \(M\) bước chắc chắn đã lặp một kim loại.

Ngăn xếp sâu tối đa \(M\) và mỗi mức gọi hai nhánh, nên cây gọi có không quá \(2^M\) lá và dưới \(2^{M+1}\) nút. Một lần Create(1) tốn \(O(2^M)\). Mỗi loại có nhiều nhất 8 gram, nên gọi khoảng \(8M\) lần; với \(M=8\), số phép thực hiện cỡ \(8\cdot8\cdot2^8\), đủ nhỏ.

Test Set 2 (Ẩn)

Cách trên quá chậm. Ta duy trì một “công thức hiện tại” để tạo một gram chì. Ban đầu công thức chỉ yêu cầu 1 gram chì. Bất biến là công thức hiện tại luôn tối ưu: mọi cách khác có thể tạo chì từ kho hiện tại đều là một phép khai triển của công thức này. Khai triển nghĩa là thực hiện không hoặc nhiều lần thao tác thay 1 gram một kim loại trong công thức bằng 1 gram của mỗi nguyên liệu tạo ra nó. Bất biến hiển nhiên đúng với công thức ban đầu.

Ở mỗi bước, tạo nhiều gram chì nhất có thể bằng công thức hiện tại. Sau đó, lượng còn lại của ít nhất một kim loại trong công thức nhỏ hơn lượng mà một bản công thức yêu cầu. Mọi công thức còn khả thi đều phải khai triển một trong các kim loại thiếu ấy thành hai nguyên liệu của nó. Thực hiện một phép thay như vậy để có công thức tối ưu mới rồi lặp lại.

Tổng số gram được yêu cầu trong công thức chỉ tăng, còn tổng số gram trong kho chỉ giảm hoặc giữ nguyên nếu bước đó chưa tạo được chì. Vì vậy, khi tổng yêu cầu vượt tổng kho, chắc chắn không thể tạo thêm một gram chì và có thể dừng.

Gọi \(S=\sum_iG_i\) là tổng số gram ban đầu. Biểu diễn công thức bằng vector độ dài \(M\). Mỗi bước tốn \(O(M)\): một lượt tìm nguyên liệu giới hạn để biết tạo được bao nhiêu chì, một lượt tìm nguyên liệu cần khai triển, còn phép thay một nguyên liệu chỉ sửa hằng số phần tử. Mỗi phép khai triển làm tổng yêu cầu tăng ít nhất 1, nên có nhiều nhất \(S\) bước trước điều kiện dừng. Tổng thời gian \(O(MS)\), đủ cho \(M\le100\) và \(S\le10000\).

Test Set 3 (Ẩn)

Ở đây \(S\) có thể tới \(10^{11}\), nên cần cách có hệ thống hơn. Xét bài toán quyết định liệu có tạo được \(L\) gram chì hay không; tính khả thi đơn điệu theo \(L\), vì vậy tìm kiếm nhị phân trên \([0,S]\) sẽ giải bài toán với thêm hệ số \(\log S\).

Với \(L\) cố định, thay lượng chì trong kho bằng \(G_1-L\); giá trị này có thể âm, tức một khoản nợ chì. Ta liên tục đẩy các khoản nợ sang nguyên liệu cho đến khi không còn nợ hoặc không thể trả. Trong quá trình đó, cả vector kho \(G\) và các công thức \(R\) đều được điều chỉnh, ban đầu đúng như input.

Ở mỗi bước, tìm một kim loại \(i\) có \(G_i<0\). Nếu không có, mọi khoản nợ đã được trả và có thể tạo \(L\) gram chì. Nếu có, xét công thức tạo \(i\). Nếu công thức ấy chứa chính \(i\), không thể trả khoản nợ và kết luận không khả thi. Nếu không, với mỗi \(k\) gram kim loại \(j\) mà công thức yêu cầu, cập nhật

nhớ rằng \(G_i\) âm, tức chuyển khoản nợ của \(i\) thành nợ các nguyên liệu. Sau đó đặt \(G_i:=0\).

Để kim loại \(i\) không bao giờ còn bị yêu cầu, trong công thức của mọi kim loại khác, thay mỗi hệ số \(k\) của \(i\) bằng \(k\) lần toàn bộ công thức của \(i\). Nếu sau này cần tạo \(i\), việc khai triển đã được gộp sẵn vào các công thức này.

Một bước trả nợ tốn \(O(M^2)\): tìm kim loại âm và điều chỉnh các nguyên liệu tốn tuyến tính; thay \(i\) trong một công thức cũng tốn \(O(M)\) và phải làm cho tối đa \(M\) công thức. Mỗi bước loại hẳn một kim loại khỏi mọi công thức. Nhiều nhất \(M-1\) kim loại có thể biến mất; khi chỉ còn một kim loại, công thức không rỗng và chắc chắn chứa chính nó, nên quá trình dừng. Do đó, kiểm tra một \(L\) tốn \(O(M^3)\), và toàn bộ thuật toán tốn \(O(M^3\log S)\).

Khi nhân các hệ số công thức, có thể chặn mọi giá trị lớn hơn \(S\): một lượng yêu cầu vượt toàn bộ kho không thể thay đổi kết luận, và việc chặn tránh tràn số.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2018, Round 1B, bài Transmutation; kho Google Coding Competitions (Apache-2.0).