Test Set 1

Thử mọi kiểu trang phục cho mọi vũ công vẫn quá chậm. Thay vào đó, quan sát bài toán tương đương với việc tìm tập con lớn nhất của các vũ công sao cho không có hai người trong tập vừa mặc cùng kiểu trang phục vừa chung hàng hoặc cột.

Nếu tìm được tập ấy, giữ nguyên trang phục của họ và đổi những người còn lại. Duyệt các vũ công theo bất kỳ thứ tự nào, chẳng hạn thứ tự hàng. Với người không thuộc tập, chọn một kiểu mới chưa xung đột. Một vũ công chung hàng hoặc cột với nhiều nhất \(2N-2\) người khác, trong khi có \(2N\) kiểu trang phục gồm \(N\) màu nhân hai chất liệu, nên luôn tồn tại một kiểu hợp lệ.

Do đó, có thể duyệt mọi tập con của \(N^2\) vũ công và kiểm tra trong tập có cặp nào cùng kiểu, cùng hàng hoặc cột hay không. Thời gian là \(O(2^{N^2}N^2)\).

Test Set 2

Cần tìm tập nói trên hiệu quả hơn. Các kiểu trang phục độc lập với nhau. Gọi \(f(x)\) là số vũ công lớn nhất đang mặc kiểu \(x\) có thể giữ lại sao cho không có hai người chung hàng hoặc cột. Kích thước tập cần giữ là

Với mỗi kiểu \(x\), dựng đồ thị hai phía: phía trái có một đỉnh cho mỗi hàng, phía phải có một đỉnh cho mỗi cột; thêm cạnh giữa hàng \(i\) và cột \(j\) khi và chỉ khi \(A_{i,j}=x\). Chọn nhiều ô kiểu \(x\) nhất mà không trùng hàng hoặc cột chính là tìm một matching cực đại trong đồ thị này. Editorial gọi nhầm đây là “maximum independent set”; đối tượng cần tính thực sự là maximum-cardinality bipartite matching.

Cộng kích thước matching cực đại của mọi \(x\) để được số ô tối đa có thể giữ nguyên. Đáp án là \(N^2\) trừ tổng đó. Một thuật toán đường tăng đơn giản cho matching hai phía chạy trong \(O(VE)\). Với mỗi kiểu, \(V=O(N)\), còn tổng số cạnh qua mọi kiểu là đúng \(N^2\), nên tổng thời gian là \(O(N^3)\) và bộ nhớ \(O(N^2)\).

Nguồn

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