Chỉ phần dư modulo \(P\) là quan trọng

Quan sát đầu tiên là kích thước đoàn chỉ quan trọng theo modulo \(P\). Có thể thay mỗi kích thước bằng đại diện nhỏ nhất tương đương trong \([1,P]\), hoặc tiện hơn là phần dư trong \([0,P-1]\) dù 0 không phải kích thước đoàn thật.

Với \(P=2\), bộ test được mô tả bởi hai số: số đoàn lẻ và số đoàn chẵn. Tổng quát, chỉ cần bộ \(P\) số \(a_0,a_1,\ldots,a_{P-1}\), trong đó \(a_i\) là số đoàn có kích thước đồng dư \(i\) modulo \(P\).

Các đoàn thuộc \(a_0\) đơn giản nhất: phục vụ lúc nào cũng không thay đổi lượng sô-cô-la thừa sau đoàn so với trước đoàn. Vị trí của chúng không ảnh hưởng việc các đoàn khác có nhận toàn đồ mới hay không. Luôn tối ưu khi đặt chúng vào chỗ không có đồ thừa; đặt tất cả lên đầu làm mỗi đoàn loại 0 đều nhận đồ mới và không để lại đồ thừa. Vì vậy bỏ \(a_0\) khỏi phần còn lại rồi cộng thẳng \(a_0\) vào đáp án; chỉ còn \(P-1\) số cần xét.

Test Set 1

Với \(P=2\), chỉ còn \(a_1\) và không có quyết định nào vì mọi đoàn đều tương đương. Các đoàn lẻ luân phiên giữa nhận toàn đồ mới và nhận một miếng thừa. Nếu số đoàn lẻ là lẻ, đoàn cuối cũng nhận đồ mới; đóng góp là \(\lceil a_1/2\rceil\).

Với \(P=3\), còn \(a_1,a_2\). Trực giác cho thấy nên ghép đoàn loại 1 với loại 2 để trở về trạng thái không còn đồ thừa sớm nhất, và điều đó thật sự tối ưu. Ghép \(\min(a_1,a_2)\) cặp xen kẽ, đóng góp từng ấy đoàn nhận đồ mới. Sau đó còn \(M=|a_1-a_2|\) đoàn cùng loại; trong số này có \(\lceil M/3\rceil\) đoàn nhận đồ mới, tương tự trường hợp đoàn lẻ khi \(P=2\). Ta sẽ chứng minh tính tối ưu bên dưới.

Test Set 2 và lập luận bằng các khối

Trường hợp \(P=4\) phức tạp hơn việc ghép trực tiếp các trực giác của \(P=2\) và \(P=3\). Gọi một đoàn là fresh nếu chỉ nhận sô-cô-la mới, và không fresh nếu nhận ít nhất một miếng thừa. Đoàn có kích thước đồng dư \(k\) modulo \(P\) được gọi là đoàn loại \(k\).

Với một thứ tự cố định, chia nó thành các khối, mỗi khối là một đoạn liên tiếp bắt đầu bằng một đoàn fresh và không chứa đoàn fresh nào khác; tức mở khối mới ngay trước mỗi đoàn fresh. Bài toán trở thành cực đại hóa số khối. Một đoàn fresh khi và chỉ khi tổng số người trong các đoàn đứng trước nó chia hết cho \(P\).

Đổi thứ tự bên trong một khối không làm các khối khác mất hợp lệ, nên không thể làm nghiệm xấu đi; thậm chí có thể tách khối đó thành nhiều khối. Ngoại trừ khả năng khối cuối, đổi thứ tự các khối cũng không làm mất tính tối ưu.

Xét một thứ tự tối ưu sau khi bỏ đoàn loại 0. Nếu một khối chứa một đoàn loại \(k\) và một đoàn khác loại \(P-k\), khối đó chỉ có thể gồm đúng hai đoàn ấy: nếu còn đoàn khác, đưa cặp này lên đầu sẽ tạo tổng chia hết cho \(P\) và tách thêm một khối, mâu thuẫn tối ưu.

Hơn nữa, luôn tối ưu khi ghép một đoàn loại \(k\) với một đoàn loại \(P-k\). Chọn trong các thứ tự tối ưu một thứ tự có nhiều khối cặp như vậy nhất. Giả sử đoàn \(k\) ở khối \(A\) không có đoàn \(P-k\), còn đoàn \(P-k\) ở khối \(B\) không có đoàn \(k\). Tạo khối \(C\) từ hai đoàn đó và khối \(D\) từ hợp các phần còn lại của \(A,B\). Nếu tổng của \(D\) không chia hết cho \(P\), thì ban đầu ít nhất một trong \(A,B\) cũng không có tổng chia hết; đặt \(D\) ở cuối thay cho khối đó. \(C\) có thể đặt ở đâu cũng được. Ta nhận một nghiệm vẫn tối ưu nhưng có thêm một cặp, mâu thuẫn cách chọn. Điều này cũng chứng minh công thức \(P=3\).

Với \(P=4\), định lý trên cho biết phải ghép \(2+2\) nhiều nhất có thể và ghép \(1+3\) nhiều nhất có thể. Sau đó còn nhiều nhất một đoàn loại 2, và có thể còn đoàn loại 1 hoặc loại 3 nhưng không đồng thời cả hai. Cần bốn đoàn loại 1 (hoặc bốn đoàn loại 3) để tạo một khối không phải khối cuối; một đoàn loại 2 có thể kết hợp với chỉ hai đoàn cùng loại 1/3. Vì vậy luôn tối ưu khi đặt đoàn loại 2 còn dư trước các đoàn 1/3 còn dư.

Tổng đáp án cho \(P=4\) là

Dù phần chứng minh hình thức có vẻ nặng, hoàn toàn có thể tìm ra công thức bằng trực giác; mã nguồn rất ngắn. Nếu khó chứng minh một công thức ứng viên, có thể so nó với lời giải vét cạn cho \(N\) nhỏ để tăng độ tin cậy.

Lời giải quy hoạch động

Nhận xét một bộ test được biểu diễn bởi một bộ \(P\) số cũng đủ cho một lời giải DP chuẩn. Dùng trạng thái gồm bộ số lượng còn lại và một số nguyên biểu diễn lượng đồ thừa hiện tại; thử mỗi loại đoàn làm đoàn kế tiếp, tối đa \(P\) lựa chọn. Cộng 1 nếu trước đoàn này không có đồ thừa, rồi cập nhật phần dư. Ghi nhớ đệ quy.

Miền trạng thái bằng tích các số lượng ban đầu nhân \(P\). Lớn nhất khi số lượng các loại cân bằng, cho cận \((N/P)^P P\). Mỗi trạng thái thử \(P\) lựa chọn, nên tổng thời gian là \(O((N/P)^P P^2)\). Ngay cả bộ test lớn nhất cũng gần như tức thì trong ngôn ngữ nhanh và đủ dư địa dùng từ điển hay ngôn ngữ chậm hơn; một cài đặt Python cố tình chưa tối ưu chỉ mất nhiều nhất khoảng nửa giây cho một test trên máy hiện đại. Tách đoàn loại 0 ra trước làm số chiều hữu hiệu giảm một, khiến mọi test chạy tức thì.

Nguồn

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