Test Set nhỏ

Gọi \(W\) là số bộ trang phục có thể có, \(W=JPS\). Một cách vét cạn khả thi là sinh toàn bộ \(2^W\) tập con của tập trang phục, kiểm tra vi phạm và lấy một tập lớn nhất không vi phạm. Khi kiểm tra một tập, không cần quan tâm thứ tự mặc: nếu một số trang phục trong tập gây vi phạm thì dù sắp chúng và các bộ còn lại theo thứ tự nào, vi phạm cuối cùng vẫn xảy ra. Một nhận xét hữu ích khác là nếu \(S\le K\) thì đáp án hiển nhiên: dùng mọi bộ trang phục có thể.

Cách trên xử lý được phần lớn nhưng không phải tất cả trường hợp nhỏ. Với 3 3 3 1 và 3 3 3 2, có \(2^{27}\) tập, hơn 100 triệu. Một cách là giải riêng hai “ca khó” trước khi tải dữ liệu. Từ quy luật ở các đáp án khác (sẽ nói thêm bên dưới), ta suy ra số bộ tối đa lần lượt là 9 và 18. Tìm một tập có kích thước cho trước dễ hơn tìm kích thước cực đại; nếu khá chắc đáp án là 18, ta có thể duyệt các tập kích thước 18 cho tới khi thấy một tập hợp lệ, rồi thậm chí kiểm tra mọi tập kích thước 19 để xác nhận không tập nào được. Việc này nhanh hơn nhiều so với kiểm tra mọi kích thước từ 1 đến 19, nhất là vì \(\binom{27}{18}\) nhỏ hơn đáng kể \(\binom{27}{13}\) và \(\binom{27}{14}\).

Thực ra chỉ có 100 bộ tham số đầu vào khác nhau nằm trong giới hạn Test Set nhỏ, nên có thể tính trước đáp án của mọi đầu vào khả dĩ trước cả khi tải dữ liệu.

Test Set lớn

Một lần nữa, nếu \(S\le K\) thì có thể dùng mọi bộ trang phục. Nếu không, nguyên lý Dirichlet cho biết một lời giải không thể có quá

bộ khác nhau. Vì \(J\le P\le S\), cận trên là \(JPK\). Ta cũng có thể suy ra điều này từ đầu ra của lời giải vét cạn.

Một cạm bẫy là tồn tại các tập trang phục cực đại theo nghĩa không thể thêm bộ nào mà không vi phạm, nhưng không phải tập lớn nhất. Chẳng hạn, với \(J=1,P=3,S=3,K=2\), tập 1 1 1, 1 1 2, 1 2 2, 1 2 1, 1 3 3 là cực đại nhưng chỉ có 5 bộ, trong khi kích thước lớn nhất là 6. Vì vậy, chọn ngẫu nhiên các bộ hợp lệ có thể khiến ta mắc kẹt ở một cực đại cục bộ.

May mắn là có nhiều phép dựng tham lam đạt đúng \(JPK\) bộ mà không chọc giận Cảnh sát Thời trang. Vì cận trên cũng là \(JPK\), chỉ cần dựng được tập kích thước đó là xong.

Mỗi cặp áo khoác–quần dùng tối đa \(K\) lần, nên để có \(JPK\) bộ, ta buộc phải dùng mỗi cặp như vậy đúng \(K\) lần. Để công thức gọn hơn, đánh số áo khoác, quần, áo sơ mi từ 0 tới tổng tương ứng trừ 1; khi in thì cộng 1 vào mọi chỉ số.

Cố định áo khoác \(j\) và quần \(p\). Gán cho cặp này các áo sơ mi

Vì \(S>K\), chúng đôi một khác nhau; theo phép dựng, cặp áo khoác–quần được dùng đúng \(K\) lần.

Còn các cặp áo khoác–sơ mi và quần–sơ mi thì sao? Cố định áo khoác \(j\) và áo sơ mi \(s\). Nếu \((j,p,s)\) thuộc tập dựng, thì với một \(d\in[0,K-1]\) ta có

Theo số học mô-đun, đồng thời chú ý \(j\bmod S=j\), \(p\bmod S=p\), \(s\bmod S=s\), suy ra

Mỗi lựa chọn \(d\) xác định duy nhất \(p\), nên số quần đi cùng một cặp \((j,s)\) không vượt quá số lựa chọn của \(d\), tức \(K\). Lập luận đối xứng áp dụng cho mọi cặp quần–sơ mi. Như vậy phép dựng không vi phạm quy tắc nào.

Một cách nhìn khác

Bài toán tương đương chọn nhiều ô nhất trong lưới ba chiều \(J\times P\times S\) sao cho không đường thẳng ô nào theo trục \(x,y,z\) chứa quá \(K\) ô được chọn. Mỗi bộ trang phục tương ứng một ô.

Sau đây là minh họa cho hai trường hợp. Trục trái–phải là áo sơ mi, trục trên–dưới là quần, còn các lớp (hãy hình dung chúng chồng lên nhau) là áo khoác. Mỗi * là một bộ được chọn, mỗi . là một bộ không dùng.

Với \(J=2,P=3,S=4,K=1\):

*... .*..
.*.. ..*.
..*. ...*

Các bộ là 1 1 1, 1 2 2, 1 3 3, 2 1 2, 2 2 3, 2 3 4.

Với \(J=2,P=3,S=4,K=2\):

**.. .**.
.**. ..**
..** *..*

Các bộ là 1 1 1, 1 1 2, 1 2 2, 1 2 3, 1 3 3, 1 3 1, 2 1 2, 2 1 3, 2 2 3, 2 2 4, 2 3 4, 2 3 1.

Ta quan sát được:

• Trong cả hai trường hợp, lớp thứ hai (áo khoác 2) là lớp đầu (áo khoác 1) dịch vòng sang phải một ô.
• Đáp án của trường hợp thứ hai nhận được từ trường hợp thứ nhất bằng cách thêm một * ngay bên phải mỗi * đã có, có quay vòng.
• Theo phép dựng, lớp đầu không có quá \(K\) dấu * trên bất kỳ hàng hay cột nào. Mỗi lớp sau cũng vậy vì chỉ là phép quay của lớp đầu. Hơn nữa, một đường ô song song trục áo khoác, tức xuyên qua các lớp, không thể có quá \(K\) dấu *; với cách dựng các lớp, nếu có thì một hàng của lớp đầu cũng sẽ có quá \(K\) dấu *.

Phép dựng hoạt động với mọi \(J,P,S\) thỏa đề. Điều kiện \(J\le P\le S\) giúp ta khỏi phải viết nhiều nhánh để xác định chiều nào lớn nhất; đội ngũ GCJ yêu thời trang vẫn biết rõ có những tủ đồ chứa nhiều quần hơn áo sơ mi!

Phần trình bày dựa trên phân tích chính thức của Google Code Jam 2016, Vòng 1C.