Test Set 1

Trong Test Set 1, mọi thứ đều nhỏ. Một lời giải là mô phỏng quá trình. Không bao giờ có lý do để không biến đổi các nguyên tố khác chì, nên cứ áp dụng các phép biến đổi cho đến khi không thể tạo thêm chì. Nếu sau một thời gian dài lượng chì vẫn tăng thì tổng lượng chì không bị chặn. Phần Test Set 2 sẽ phân tích cận chặt chẽ; ở đây một định nghĩa trực quan về "rất nhiều" là đủ. Nếu lượng chì bị chặn, 1 gram kim loại biến thành nhiều nhất 512 gram chì, vì nó chỉ trải qua được 9 lần tách trước khi vào chu trình. Do đó, nếu từng thấy hơn 5120 gram chì thì lượng chì không bị chặn.

Tuy nhiên, ví dụ đầu cho thấy cần làm thêm một bước. Nếu chính chì có thể được dùng để tạo thêm chì thì sao? Nếu điều đó khả thi và ta có thể thu được bất kỳ lượng chì dương nào, kết quả chắc chắn không bị chặn. Nếu không, chẳng có lý do để tiêu thụ chì. Có thể kiểm tra bằng mô phỏng trên, khởi đầu với 1 gram của mỗi kim loại trong hai sản phẩm mà chì biến thành. Nếu quá trình cho 0 hoặc 1 gram chì thì không thể dùng chì để tạo thêm chì; nếu nhiều hơn thì có thể.

Test Set 2

Test Set 2 lớn hơn nhiều, nên phân tích và cài đặt cảm tính sẽ không được. Ta vẫn có thể dùng ý tưởng trên cẩn thận hơn. Vì mỗi kim loại cần nhiều nhất \(M\) bước để biến thành chì, chỉ cần \(M\) lượt mô phỏng; mỗi lượt duyệt mọi kim loại không phải chì và biến đổi toàn bộ số gram của chúng. Độ phức tạp là \(O(M^2)\). Để số không tăng quá lớn, thực hiện quá trình này hai lần: lượt đầu tạo nhiều chì nhất có thể từ các nguồn không có chu trình; nếu lượt hai còn tạo thêm thì lượng đó phải đến từ nguồn có chu trình, cuối cùng cho lượng chì không bị chặn. Phần kiểm tra chì tạo thêm chì giữ nguyên như trước.

Kết quả không vừa số nguyên 64 bit, và lấy modulo liên tục như thường lệ chưa dùng được ngay: không thể đánh đồng "không có X" với "có \(10^9+7\) gram X" nếu X có khả năng tạo lượng chì không bị chặn (X có thể là chì hoặc kim loại khác). Có nhiều cách khắc phục: dùng số nguyên lớn; lưu thêm một bit cho mỗi kết quả để chỉ ra nó có thực sự bằng 0; hoặc tính modulo \(10^9+7\times K\) với số nguyên tố ngẫu nhiên lớn \(K\) cho đến bước cuối.

Còn có những lời giải khác chỉ dùng được cho Test Set 1 và 2; chúng là các cách cài đặt kém hiệu quả hơn của lời giải Test Set 3 dưới đây.

Test Set 3

Lời giải Test Set 3 trông khá khác nhưng thực ra tương tự. Ta kiểm tra những chu trình có thể tạo lượng chì không bị chặn; nếu không có, có thể mô phỏng trong một lượt khi sắp xếp kim loại thích hợp. Tất cả đều làm được trong thời gian tuyến tính như sau.

Một nhận xét hữu ích: nếu xác định được lượng chì bị chặn, chỉ những công thức cuối cùng có thể tạo chì (có thể kết hợp với công thức khác) mới đáng dùng. Hơn nữa, không có ích khi dùng chì làm đầu vào, vì ngay cả trường hợp tốt nhất, mỗi đơn vị chì chỉ thành một đơn vị chì và một đơn vị thứ khác không thể đổi thành chì. (Nếu không, chỉ cần lặp chuỗi công thức ấy để tạo lượng chì tùy ý.)

Do đó, chỉ có thể thu được lượng chì vô hạn nếu một kim loại nào đó đồng thời tạo được chính nó và chì: phải có chuỗi công thức biến một đơn vị X thành một đơn vị X và một đơn vị chì. Có thể sinh thêm kim loại khác nhưng chúng không quan trọng. Nếu X trực tiếp sinh A và B, thì cần A sinh X và B sinh chì, hoặc ngược lại. Ngay cả khi X là chì và A hoặc B cũng là chì, nếu bỏ qua sản phẩm kia thì chỉ phá hủy 1 đơn vị chì để nhận lại 1 đơn vị chì, tổng lượng chì không đổi. Vì vậy trong trường hợp vô hạn, sau mỗi công thức phải xử lý cả hai đầu ra, không chỉ một.

Gọi \(Q\) là đồ thị có mỗi kim loại là một đỉnh và có cạnh \(u\to v\) nếu tiêu thụ 1 đơn vị \(u\) có thể tạo 1 đơn vị \(v\). Nếu ban đầu không có kim loại \(i\) (\(G_i=0\)), và không thể đi tới \(i\) trong \(Q\) từ một \(j\) có \(G_j>0\), thì không thể tạo \(i\); ta loại các kim loại ấy ngay từ đầu. Sau đây giả sử \(Q\) không còn chúng.

Gọi \(Q'\) là đồ thị chuyển vị của \(Q\), và \(L\) là đỉnh chì. Duyệt \(Q'\) từ \(L\) tạo đồ thị con \(Q'_L\), gồm đúng các kim loại có thể tạo chì qua một chuỗi biến đổi. Gọi \(P_u\) là số đường đi đơn (không có chu trình) từ \(L\) đến \(u\) trong \(Q'_L\). Nếu lượng chì bị chặn, \(P_u\) là số đơn vị chì nhận được từ mỗi đơn vị \(u\). Mỗi cạnh đảo biểu diễn một phép biến đổi hợp lệ từ 1 đơn vị kim loại thành 1 đơn vị kim loại khác; dọc đường đi ta dùng sản phẩm của biến đổi trước, không phải đơn vị kim loại ban đầu. Ví dụ, cho \(Q'_L\):

• \(1\to2\)
• \(1\to3\)
• \(2\to4\)
• \(3\to4\)

Các phép biến đổi tương ứng là:

• 4 biến thành 2 và 3.
• 2 biến thành 1 và một kim loại khác.
• 3 biến thành 1 và một kim loại khác.

Có 2 đường đi đơn từ 1 đến 4: \(1\to2\to4\) và \(1\to3\to4\). Một đơn vị kim loại 4 biến thành 2 đơn vị chì (1) như sau:

• Biến một đơn vị 4 thành một đơn vị 2 và một đơn vị 3.
• Lấy đơn vị 3 ở bước 1, biến nó thành một đơn vị 1 và một đơn vị kim loại khác.
• Lấy đơn vị 2 ở bước 1, biến nó thành một đơn vị 1 và một đơn vị kim loại khác.

Mặt khác, các đỉnh trong cùng một thành phần liên thông mạnh (SCC) của \(Q\) là những kim loại có thể tạo ra lẫn nhau. Chính xác hơn, nếu \(u,v\) cùng SCC, có thể tạo 1 đơn vị \(v\) từ 1 đơn vị \(u\) và ngược lại. Với \(v_1,v_2\) là hai đầu ra của công thức tại một đỉnh \(u\), lượng chì không bị chặn nếu tồn tại \(u\) thỏa một trong hai điều kiện:

• \(v_1\) thuộc \(Q'_L\), còn \(v_2\) và \(u\) cùng SCC; hoặc
• \(v_2\) thuộc \(Q'_L\), còn \(v_1\) và \(u\) cùng SCC.

Nếu không, lượng chì có giới hạn, được tính bằng cách nhân \(P_u\) với lượng ban đầu \(G_u\) cho mỗi \(u\) trong \(Q'_L\).

Có thể tìm mọi SCC trong \(O(M)\) bằng Tarjan hoặc Kosaraju, vì cả số đỉnh và cạnh đều tuyến tính theo \(M\). Duyệt các đồ thị và kiểm tra điều kiện vô hạn cũng tốn \(O(M)\). Mọi \(P_u\) cũng tính được trong \(O(M)\): nếu lượng chì bị chặn thì \(Q'_L\) không có chu trình. (Nếu có chu trình, đảo các cạnh sẽ cho ít nhất một kim loại thỏa điều kiện vô hạn.) Do đó có thể sắp xếp tô-pô các đỉnh \(Q'_L\) và dùng quy hoạch động tính hàm \(F\) — số đường đi đơn — theo:

• \(F(L)=1\).
• \(F(u)=∑ F(v)\) với mọi \(v\) sao cho có cạnh \(v\to u\) trong \(Q'_L\).

Vì số cạnh trong mọi đồ thị trên cũng là \(O(M)\), toàn bộ bài toán được giải trong thời gian tuyến tính.

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2019, Vòng 2 — Contransmutation.