Phân nhóm 1

Nhìn chung, ta sẽ xây dựng tất cả các lưới có tổng hàng và cột đúng, rồi kiểm tra từng lưới xem có hình vuông hay không. Trong Phân nhóm 1, kích thước đầu vào nhiều nhất là \(6\times6\). Như vậy có \(2^{36}\) lưới khác nhau, quá nhiều để sinh hết, nên phải tận dụng các ràng buộc về tổng hàng.

Ta xây dựng lưới từng ô một. Khi điền mỗi ô, phải bảo đảm rằng vẫn có thể đạt được tổng hàng và cột tương ứng. Ví dụ, nếu tổng hàng cần bằng \(3\) nhưng hàng đã có ba dấu /, ta không thể đặt thêm /. Tương tự, nếu tổng hàng cần bằng \(3\) nhưng hàng đã có \(R-3\) dấu \, ta không thể đặt thêm \. Khi điền xong lưới, ta kiểm tra lưới vừa tạo có hình vuông nào không. Nếu không có, ta đã hoàn tất. Nếu có, chuyển sang lưới khả dĩ kế tiếp. Nếu đã tìm hết mọi lưới khả dĩ mà vẫn không thấy đáp án, kết quả là IMPOSSIBLE.

Liệu cách này có đủ nhanh? Mỗi hàng cần \(0,1,2,3,4,5\) hoặc \(6\) dấu /. Số lựa chọn tương ứng lần lượt là

Do đó mỗi hàng có nhiều nhất \(20\) lựa chọn hợp lệ, và thuật toán duyệt nhiều nhất \(20^6\) lưới. Trên thực tế, ta không tới gần cận này. Đặc biệt, hàng dưới cùng có nhiều nhất một lựa chọn hợp lệ vì phải thỏa các tổng cột. Chỉ riêng điều đó đã giảm không gian tìm kiếm xuống nhiều nhất \(20^5\), và đây vẫn là đánh giá quá cao vì quá trình tìm kiếm còn được cắt tỉa rất nhiều.

Có nhiều cách kiểm tra hình vuông. Cách dễ nhất là duyệt mọi vị trí có thể của hàng trên cùng của hình vuông (và hai cột liên tiếp chứa cặp /\). Sau đó, với mỗi kích thước hình vuông khả dĩ (\(1,2,3\)), chỉ cần kiểm tra các ô tương ứng trên bốn cạnh của hình vuông.

Phân nhóm 2

Giới hạn của Phân nhóm 2 quá lớn để tìm vét cạn mọi lưới, nên cần một nhận xét. Ta gọi một lưới thỏa các ràng buộc hàng và cột là một cấu hình. Trước tiên, hãy bàn cách tìm một cấu hình bất kỳ (có thể square free hoặc không). Ta mô hình hóa thành đồ thị và chạy luồng cực đại. Có \(R\) đỉnh biểu diễn các hàng và \(C\) đỉnh biểu diễn các cột. Đặt cạnh dung lượng \(1\) giữa mọi cặp đỉnh (hàng, cột). Nối đỉnh hàng thứ \(i\) với một siêu đỉnh hàng bằng cạnh dung lượng \(S_i\), và nối đỉnh cột thứ \(i\) với một siêu đỉnh cột bằng cạnh dung lượng \(D_i\).

Chạy luồng trên mạng với siêu đỉnh hàng làm nguồn và siêu đỉnh cột làm đích. Nếu mạng bão hòa (tức mọi cạnh rời nguồn có luồng bằng dung lượng), ta có một lời giải. Nếu cạnh giữa hàng \(r\) và cột \(c\) có luồng, ô tương ứng là /; nếu không, ô đó là \. Nếu luồng không bão hòa thì không thể tạo lưới có đúng các tổng hàng và cột yêu cầu. Việc chứng minh chính thức song ánh giữa các cấu hình và các luồng hợp lệ trên mạng này được để lại như một bài tập.

Tới đây ta có một cấu hình, nhưng nó có thể chứa hình vuông. Sau đây là ba cách khác nhau để tạo một lưới square free.

Cấu hình nhỏ nhất theo thứ tự từ điển

Nhận xét rằng cấu hình nhỏ nhất theo thứ tự từ điển (coi \ nhỏ hơn / và đọc theo thứ tự hàng trước, cột sau) là square free. Điều này ban đầu không hiển nhiên. Xét hai hàng \(r_i<r_j\) và hai cột \(c_k<c_\ell\). Nếu

thì lưới chưa phải nhỏ nhất theo thứ tự từ điển. Ta có thể đổi cả bốn ký hiệu mà không phá vỡ ràng buộc hàng hay cột, đồng thời thu được cấu hình nhỏ hơn:

Vì vậy, cấu hình nhỏ nhất theo thứ tự từ điển không có hình vuông: hàng trên cùng của một hình vuông phải chứa /\ tại chính hai cột mà hàng dưới cùng chứa \/.

Làm sao tìm cấu hình nhỏ nhất theo thứ tự từ điển? Có hai cách:

1. Gán cạnh giữa hàng \(r\) và cột \(c\) chi phí \(2^{r-1+(c-1)R}\) rồi chạy luồng cực đại chi phí nhỏ nhất. Cách này chắc chắn tìm được cấu hình nhỏ nhất, nhưng chi phí cạnh sẽ rất lớn, tới \(2^{RC-1}\).
2. Chạy luồng cực đại lặp lại. Sau khi đã chạy luồng, duyệt các cạnh theo thứ tự hàng trước, cột sau của ô tương ứng. Nếu một cạnh không có luồng thì ô là \; đây đã là giá trị nhỏ nhất có thể, nên xóa cạnh khỏi đồ thị để khóa giá trị. Nếu cạnh có luồng, ta “đẩy ngược” luồng trên cạnh đó (giảm luồng từ đích tới đỉnh cột, tới đỉnh hàng, rồi tới nguồn đi \(1\)), và tạm đặt dung lượng cạnh bằng \(0\). Chạy luồng lại. Nếu mạng vẫn bão hòa, tồn tại cấu hình mà ô này là \, nên có thể xóa cạnh vĩnh viễn. Nếu không bão hòa, phải đặt cạnh trở lại; ô này buộc phải là /.

Lần chạy luồng cực đại đầu tiên mất \(O((RC)^2)\). Sau đó, mỗi lần chạy chỉ cần đẩy thêm một đơn vị luồng, tức chỉ cần một đường tăng luồng và mất \(O(RC)\) cho mỗi cạnh. Vì vậy tổng thời gian là \(O((RC)^2)\). Cũng có thể chạy lại toàn bộ luồng cực đại cho mỗi cạnh nếu cài đặt luồng đủ tối ưu.

Luồng cực đại chi phí nhỏ nhất

Trong cách trên, ta đã dùng luồng cực đại chi phí nhỏ nhất với chi phí cạnh hàm mũ. Ở đây ta chỉ dùng chi phí có kích thước đa thức. Ý tưởng vẫn giống trước: ta muốn tránh mẫu

nhưng ngoài việc đó ra, không cần cấu hình nhỏ nhất theo thứ tự từ điển. Nếu đặt chi phí cạnh giữa hàng \(r\) và cột \(c\) bằng \(r\times c\), cấu hình này sẽ không xuất hiện, vì đổi bốn ký hiệu không ảnh hưởng tổng hàng/cột nhưng làm tổng chi phí giảm nghiêm ngặt. Chi phí giảm \(i\times k+j\times\ell\) và tăng \(i\times\ell+j\times k\), nên mức giảm ròng là

do \(i<j\) và \(k<\ell\).

Lật qua lật lại!

Một lời giải khác là tìm một cấu hình bất kỳ rồi kiểm tra hình vuông. Nếu không có hình vuông, ta hoàn tất. Nếu có một hình vuông, xét hàng trên cùng và hàng dưới cùng của nó. Đổi cặp /\ ở trên với cặp \/ ở dưới. Thao tác này không thay đổi tổng hàng/cột. Nó phá hình vuông hiện tại nhưng có thể tạo ra hình vuông khác. Ta tiếp tục phá hình vuông cho tới khi không còn cái nào. Quá trình chắc chắn kết thúc vì mỗi lần đổi luôn làm lưới nhỏ hơn theo thứ tự từ điển. Không bao giờ cần quá \(O((RC)^2)\) phép đổi dạng này.

Lỗi thường gặp

Hãy cẩn thận: chỉ vì tổng các \(S_i\) bằng tổng các \(D_i\) không có nghĩa là tồn tại một cấu hình. Ví dụ sau có hai tổng bằng nhau nhưng không có lưới nào thỏa mọi yêu cầu theo hàng và cột:

4 6
2 0 6 6
4 2 2 2 2 2

Nguồn

Google Code Jam 2021, Vòng 3, bài Square Free.

Phân tích chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.