Test Set 1

Số gam trong một gói tự nó không quan trọng; điều quan trọng là gói ấy dùng được cho những bội số nào của công thức. Chẳng hạn, nếu công thức cơ sở cần 10 g cà chua thì gói 201 g có thể dùng để làm 19, 20, 21 hoặc 22 lần công thức, nhưng không dùng được cho bội số khác. Ta biểu diễn gói này bằng khoảng nguyên đóng \([19,22]\).

Làm sao tìm các khoảng? Gọi \(Q\) là lượng trong gói, \(R\) là lượng nguyên liệu đó cần cho công thức cơ sở. Một bội số \(m\) hợp lệ phải thỏa

Biến đổi cho ta

Mọi giá trị nguyên \(m\) thỏa bất đẳng thức thuộc khoảng; hai đầu mút có thể tính trong thời gian hằng số. Một khoảng có thể không chứa số nguyên nào, ví dụ \(R=10,Q=15\). Có thể dùng phép chia nguyên và tránh hoàn toàn số thực.

Test Set 1 có nhiều nhất hai nguyên liệu. Nếu chỉ có một nguyên liệu, mỗi gói có khoảng không rỗng tạo được một kit, còn gói có khoảng rỗng thì không.

Nếu có hai nguyên liệu, ta phải ghép các gói thành kit và không phải phép ghép nào cũng tối ưu. Ví dụ, công thức cần 5 g A và 10 g B; ta có các gói A là 45, 50 và các gói B là 110, 111. Các khoảng tương ứng của A là \([9,10]\), \([10,11]\); của B là \([10,12]\), \([11,12]\). Nếu ghép \([10,11]\) của A với \([10,12]\) của B, ta còn \([9,10]\) của A và \([11,12]\) của B, không thể ghép với nhau. Nhưng có thể tạo hai kit bằng cách ghép \([9,10]\) của A với \([10,12]\) của B, và \([10,11]\) của A với \([11,12]\) của B.

Có thể giải bằng ghép cặp hai phía, nhưng không cần thiết. Vì mỗi nguyên liệu có nhiều nhất 8 gói trong Test Set 1, thử vét cạn mọi phép ghép trong số \(8!\) hoán vị rồi chọn số kit lớn nhất là đủ.

Test Set 2

Chiến lược tham lam sau hoạt động với mọi số lượng nguyên liệu:

• Luôn tạo bội số nhỏ nhất của công thức mà ta có thể tạo.
• Khi có nhiều gói để chọn, chọn gói có đầu phải của khoảng nhỏ nhất. Vì ta luôn tạo bội số nhỏ nhất có thể, phần khoảng không vượt quá bội số hiện tại không còn quan trọng; chỉ độ lớn của đầu phải còn quan trọng. Do các khoảng liên tục, khoảng có đầu phải lớn hơn linh hoạt hơn hẳn cho những phép ghép về sau.

Chiến lược này không nhất thiết tối ưu với các khoảng tùy ý, nhưng tối ưu ở đây nhờ tính chất sau. Nếu \(I_1,I_2\) là hai khoảng bội số hợp lệ của cùng một nguyên liệu và \(I_1\subseteq I_2\), thì chúng có ít nhất một đầu mút chung. Thật vậy, nếu \(I_i\) sinh từ gói kích thước \(S_i\) và \(S_1\le S_2\), đầu trái của \(I_1\) không thể lớn hơn đầu trái của \(I_2\). Nếu không thì \(S_1>S_2\), và đầu phải của \(I_1\) không thể nhỏ hơn đầu phải của \(I_2\). Gọi đây là tính chất 0.

Trước khi chứng minh chính, cần hai tính chất của thuật toán tham lam:

• Tính chất 1: mỗi khi thuật toán bỏ một khoảng, không còn kit hợp lệ nào có thể dùng khoảng đó. Điều này suy ra trực tiếp từ điều kiện bỏ khoảng.
• Tính chất 2: mỗi khi thuật toán chọn một tập khoảng làm kit, gọi \(M\) là đầu trái của giao tất cả các khoảng đó; không còn tập khoảng nào khác có thể tạo kit với bội số nhỏ hơn hẳn \(M\). Điều này suy ra trực tiếp từ thứ tự xét các khoảng.

Kết hợp các tính chất và chứng minh phản chứng. Gọi \(M_1,M_2,\ldots,M_k\) là các bội số nhỏ nhất của các kit do thuật toán tham lam tạo ra, theo thứ tự không giảm. Giả sử tồn tại một cách gán tạo được thêm một kit, và gọi \(N_1,N_2,\ldots,N_k,N_{k+1}\) là các bội số nhỏ nhất của các kit trong cách gán đó, cũng theo thứ tự không giảm.

• Trường hợp A: gọi \(i\) là chỉ số nhỏ nhất sao cho \(N_i<M_i\). Theo tính chất 2, điều này chỉ có thể xảy ra nếu không còn tập khoảng nào tạo được kit với bội số \(N_i\): thuật toán đã bỏ các khoảng ấy hoặc dùng chúng cho kit trước. Tính chất 1 loại trừ việc bỏ. Tính chất 0 cùng thứ tự xử lý loại trừ việc dùng sai ở trước: khi một khoảng \(R\) được chọn, mọi khoảng còn lại của nguyên liệu đó có đầu phải không nhỏ hơn đầu phải của \(R\), nên lựa chọn ấy không thể ngăn một kit tương lai; các khoảng còn lại ít nhất cũng hữu dụng như \(R\) đối với các bội số lớn hơn.
• Trường hợp B: không có chỉ số \(i\) như vậy. Để không tạo được kit có bội số \(N_{k+1}\), thuật toán vẫn phải thiếu một khoảng nào đó. Nhưng lập luận giống trường hợp A, dùng tính chất 1 và 0, cho thấy không thể đã có một quyết định sai trước đó làm khoảng ấy biến mất.

Vậy giả sử có cách tạo thêm một kit dẫn tới mâu thuẫn; thuật toán tham lam là tối ưu.

Cài đặt bằng một danh sách riêng cho mỗi nguyên liệu, sắp tăng theo đầu trái rồi theo đầu phải. Luôn nhìn các khoảng đầu danh sách. Nếu tất cả có giao không rỗng, dùng chúng tạo kit và xóa chúng. Nếu không, xóa khoảng kém hữu dụng nhất, tức khoảng có đầu phải nhỏ nhất. Có thể dùng hàng đợi ưu tiên để tăng tốc, nhưng với \(N\times P\le1000\) thì không cần.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2017, Round 1A, bài Ratatouille.