Phân tích

Test Set 1

Có nhiều nhất \(10\) lá, nên vét cạn mọi kịch bản. Với mỗi lá, chọn nó vào nhóm tổng hoặc nhóm tích. Tính tổng nhóm thứ nhất, tích nhóm thứ hai; nếu bằng nhau, đó là một điểm ứng viên. Sau mọi cách chia, in ứng viên lớn nhất, hoặc \(0\) nếu không có. Phải bảo đảm hai nhóm đều không rỗng.

Tích có thể tràn kiểu số nguyên: tệ nhất là \(10\) lá đều ghi \(499\). Một cách tránh tràn là tính tổng trước rồi lần lượt chia nó cho các số ở nhóm tích; nếu có bước không chia hết hoặc kết quả cuối khác \(1\), cách chia không hợp lệ. Cách khác: tổng không quá \(4990\), nên có thể tính tích bằng số thực; cận nhỏ khiến sai số không gây vấn đề.

Có \(2^N\) cách chia và mỗi cách được tính bằng một lượt tuyến tính, nên độ phức tạp \(O(2^NN)\). Có thể bỏ thừa số tuyến tính nhưng không cần.

Test Set 2

Với tối đa \(100\) lá, không thể vét cạn. Tuy nhiên nhóm tích không thể có nhiều số vì tích các số lớn hơn \(1\) tăng rất nhanh. Tổng nhóm thứ nhất không quá \(49900\), và \(2^{16}>49900\), nên nhóm tích có nhiều nhất \(15\) lá.

Xét tập trạng thái sau \(i\) lá theo một thứ tự bất kỳ. Không lưu cách chia cụ thể mà lưu cặp \((x,y)\): tổng nhóm thứ nhất và tích nhóm thứ hai. Với lá kế tiếp có giá trị \(b\), từ \((x,y)\) tạo hai lựa chọn \((x+b,y)\) và \((x,yb)\). Loại trạng thái nếu tích vượt \(49900\). Sau mọi lá, lấy giá trị lớn nhất của trạng thái có \(x=y\), hoặc \(0\).

Có thể nghĩ có tới \({100\choose15}\) cách, nhưng tích nhóm hai không quá \(49900\) và mỗi số có phân tích nguyên tố duy nhất. Do đó mỗi tích xác định duy nhất nhóm tích theo số lượng từng nguyên tố, phần còn lại thuộc nhóm tổng. Sau mỗi lá có nhiều nhất \(49900\) trạng thái, cho cận khoảng \(49900\cdot100\approx5\cdot10^6\) thao tác.

Tính duy nhất của phân tích nguyên tố còn cho lời giải khác. Chỉ có \(49900\) điểm ứng viên. Với mỗi điểm, phân tích ra thừa số nguyên tố. Nếu nguyên tố \(p\) xuất hiện \(q\) lần, đầu vào phải có ít nhất \(q\) lá \(p\) để nhóm tích tồn tại. Tổng nhóm đầu bằng tổng mọi lá trừ tổng các thừa số đã dùng và phải đúng bằng điểm ứng viên. Hai điều kiện này dễ kiểm tra; cách này tổng quát tốt sang Test Set 3.

Test Set 3

Số lá có thể tới \(10^{15}\) và tổng nhóm đầu tới \(4{,}99\cdot10^{17}\). Tuy vậy nhóm tích vẫn nhỏ: \(2^{60}>4{,}99\cdot10^{17}\), nên có nhiều nhất \(60\) lá. Tổng các số trong nhóm tích không quá \(60\cdot499=29940\); cực đại thật dưới ràng buộc là \(3025\), nhưng cận thô đủ dùng.

Gọi \(X\) là tổng mọi lá. Tổng nhóm đầu nằm trong \([X-29940,X]\), nên chỉ có \(29941\) điểm ứng viên. Ta muốn áp dụng cách phân tích ứng viên của Test Set 2.

Phân tích một số cỡ \(10^{17}\) nói chung không dễ; thử tới căn bậc hai quá chậm. Nhưng ta không quan tâm nguyên tố lớn hơn \(499\): nếu ứng viên có thừa số khác các nguyên tố đầu vào, nó không thể là tích nhóm hai. Chỉ cần thử chia \(29940\) ứng viên cho \(95\) nguyên tố từ \(2\) đến \(499\), với tổng nhiều nhất \(60\) thừa số.

Việc phân tích cần khoảng \(29940(95+60)\approx4{,}6\cdot10^6\) thao tác. Có thể dùng cách giống sàng để giảm xuống \(29940\log\log499\approx10^5\), nhưng không cần. Sau phân tích, kiểm tra số mũ từng nguyên tố so với số lá và tính tổng các thừa số; việc này tốn \(29940\cdot95\approx3\cdot10^6\) thao tác.

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