Phân tích

Nhận xét đơn giản đầu tiên: ta không bao giờ đổi chỗ hai viên đang hiện cùng màu.

Nhận xét chính khó hơn: bất kể chi phí, mỗi viên hoặc bị lật, hoặc tham gia đổi chỗ, hoặc không làm gì — không bao giờ cả lật lẫn đổi. Xét mọi thao tác ảnh hưởng viên \(a\): nếu có đổi \(a,b\) rồi lật \(a\), hoặc lật \(a\) rồi đổi \(a,b\), có thể đạt cùng hiệu ứng với chi phí thấp hơn bằng cách chỉ lật \(b\) (dù \(b\) có thể đã di chuyển bởi các đổi chỗ xen giữa).

Ta cũng không bao giờ muốn lật cùng một viên quá một lần. Vì mỗi viên chỉ chịu một loại thao tác, có thể giả sử mọi đổi chỗ xảy ra trước mọi lần lật. Sau khi đổi xong, các lần lật được xác định: ô nào khác đích thì lật, ô nào giống thì không.

Test Set 1

Ta còn có thể nhận xét không viên nào cần đổi chỗ hai lần. Vì không đổi hai viên cùng màu, chuỗi đổi \(a,b\) rồi \(b,c\) tương đương lật \(a,c\), cùng chi phí. Do mỗi viên chỉ đổi một lần, chỉ nên đổi cặp nếu thao tác sửa đúng màu của cả hai. Đổi chỗ sửa hai ô, lật sửa một ô, nên ta tối đa hóa số phép đổi hợp lệ rồi lật phần còn lại.

Bài toán trở thành: một số ô cần đổi màu; ghép nhiều nhất các ô đó với ô kề cũng cần đổi sang màu đối diện. Đồ thị ô và cạnh kề là hai phía, nên dùng ghép cặp cực đại trên đồ thị hai phía. Đáp án bằng số ô cần đổi trừ kích thước ghép cực đại.

Test Set 2

Ví dụ bổ sung cho thấy một viên có thể cần nhiều lần đổi. Ta tổng quát lời giải trên. Một viên qua nhiều đổi chỗ thực chất đổi với một viên không nhất thiết kề. Các viên trung gian bị dịch chuyển đều cùng màu, nên sự dịch chuyển không có ảnh hưởng; có thể coi một phép đổi là di chuyển một M sang ô kề, và chuỗi đổi là chuỗi bước di chuyển.

Không mất tính tổng quát, giả sử số M tăng từ trạng thái đầu sang đích; nếu không, xét G. Vì mọi đổi xảy ra trước, ta di chuyển một số M cần biến thành G tới các vị trí đang G nhưng cần thành M. Ghép hai loại ô này mà không cần kề nhau. Mọi vị trí G thành M không được ghép phải lật; số lượng đó do đầu vào cố định.

Với mỗi cặp ghép, chi phí sửa hai vị trí là nhỏ hơn giữa khoảng cách trực giao nhân \(S\) và \(2F\), vì cũng có thể lật cả hai.

Như vậy ta đã dựng một ghép cặp hai phía có trọng số giữa các ô M cần thành G và các ô G cần thành M. Tổng chi phí là chi phí nhỏ nhất của ghép cực đại cộng \(F\) nhân số ô không ghép. Có thể dùng bất kỳ thuật toán ghép cực đại chi phí nhỏ nhất nào, chẳng hạn thuật toán Hungary.

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