Diễn giải bằng quân cờ

Bối cảnh có phần lạ của đề bài thực chất che giấu một dạng bài cờ kinh điển: đặt các quân sao cho chúng không tấn công nhau. Bài toán tám hậu là một ví dụ nổi tiếng. Bài này phức tạp hơn vì có tới ba loại quân, và các quy tắc của chúng được diễn giải theo ngôn ngữ cờ vua như dưới đây.

Mô hình + hoạt động như tượng: không có hai mô hình cùng đường chéo. Mô hình x như xe: không cùng hàng hay cột. Mô hình o như hậu, tức đồng thời có cả hai tính chất. Khác cờ vua thông thường, quân nằm giữa không che được nhau, còn xe và tượng vẫn có thể cùng hàng hoặc cột vì chúng kiểm soát các loại đường độc lập. Cụ thể, một xe và một tượng nằm chung hàng hoặc chung cột vẫn hợp lệ. Ngược lại, hai tượng nằm trên cùng một đường chéo vẫn bị coi là đe dọa nhau ngay cả khi có một xe đứng giữa chúng; quân xe đó không thể che đường như trong cờ vua thông thường.

Tách bài toán

Tách mỗi o thành một xe và một tượng, rồi giải hai bài toán độc lập:

• giữ và bổ sung các thành phần xe sao cho mỗi hàng, mỗi cột dùng nhiều nhất một lần;
• giữ và bổ sung các thành phần tượng sao cho mỗi đường chéo của mỗi hướng dùng nhiều nhất một lần.

Cuối cùng, ô có cả hai thành phần trở lại thành o; chỉ có xe là x, chỉ có tượng là +. Việc ghép không thể sinh xung đột mới, vì mọi xung đột hàng/cột đã bị loại ở bài xe và mọi xung đột đường chéo đã bị loại ở bài tượng. Chẳng hạn, không cần lo phép ghép tạo ra một hậu nằm cùng đường chéo với một tượng: điều đó chỉ có thể xảy ra nếu nghiệm của bài tượng vốn đã có hai tượng trên cùng đường chéo, trái với điều kiện của bài con. Điểm cũng cộng tuyến tính: o được \(2\) điểm đúng bằng một xe cộng một tượng. Do đó tối ưu riêng từng phần cho tổng điểm tối ưu.

Bài toán xe

Mỗi xe chiếm đúng một hàng và một cột. Đánh dấu các hàng và cột đã bị mô hình x hoặc o ban đầu dùng; ghép tùy ý từng hàng trống với một cột trống. Mọi chiến lược tham lam hợp lệ đều đặt được tổng cộng \(N\) thành phần xe.

Tượng: Test Set nhỏ

Các mô hình đặt sẵn đều ở hàng trên. Tượng trong cùng hàng không đe dọa nhau, nên có thể lấp đầy hàng trên bằng tượng. Sau đó lấp hàng dưới, trừ hai ô góc bị hai tượng ở góc hàng trên khống chế. Với \(N>1\), ta được \(2N-2\) tượng; xử lý riêng bàn \(1\times1\).

Tính tối ưu: bàn có \(4N-2\) đường chéo, nhưng hai cặp đường chéo độ dài \(1\) ở các góc đối diện không thể đồng thời hữu ích, nên nhiều nhất \(4N-4\) đường chéo có thể được dùng. Mỗi tượng dùng hai đường chéo, cho cận trên \(2N-2\), đúng bằng cách dựng.

Lập luận đầy đủ cho cách dựng này như sau. Trong Test Set nhỏ, mọi quân đặt sẵn đều ở hàng trên cùng. Các tượng cùng hàng hoặc cùng cột không thể đe dọa nhau, nên ta có thể thêm thành phần tượng vào mọi ô hàng trên chưa có tượng. Vì vậy, chỉ cần một mẫu nghiệm tổng quát luôn lấp kín hàng trên là có thể biến an toàn mọi bố trí đặt sẵn thành một hàng đầy tượng.

Sau khi hàng trên đã kín, hàng dưới cùng nằm xa nhất khỏi các ràng buộc do hàng trên tạo ra. Ta đặt tượng vào mọi ô hàng dưới trừ hai ô đầu mút: hai ô đó lần lượt bị hai tượng ở hai đầu hàng trên đe dọa. Các tượng mới không đe dọa lẫn nhau và cũng không đe dọa tượng nào ở hàng trên, nên bố trí hợp lệ và có tổng cộng \(2N-2\) tượng. Không thể thêm tượng nào khác sau đó, nhưng vẫn cần tự hỏi liệu số lượng ấy đã thực sự là lớn nhất hay chưa.

Có ba cách để đi tiếp tại đây:

1. Thử nghiệm trên nhiều bàn và tự thuyết phục rằng cách dựng có lẽ tối ưu.
2. Tin vào phỏng đoán rồi nộp thử; với Test Set nhỏ của vòng Qualification, gần như không có lý do gì để không tận dụng verdict hiển thị.
3. Chứng minh: bàn \(N\times N\) có \(4N-2\) đường chéo. Hai đường chéo song song độ dài \(1\) tại hai góc đối diện không thể cùng được dùng, đối với cả hai hướng, nên chỉ có tối đa \(4N-4\) đường chéo đồng thời sử dụng được. Mỗi tượng chiếm hai đường chéo, do đó \(2N-2\) là cận trên và cách dựng đạt đúng cận ấy.

Vẫn phải xử lý đúng một xe hoặc hậu đặt sẵn nếu có, rồi ghép nghiệm xe và tượng để tạo hậu khi cần. Cũng phải tách riêng bàn \(1\times1\), vì bàn này không có hàng dưới khác hàng trên. Có thể tìm ra cùng cách dựng mà không nhận ra phép tách xe–tượng, nhưng khi đó việc biện minh tính tối ưu sẽ khó hơn.

Tượng: Test Set lớn

Các ô có \(r+c\) chẵn và lẻ độc lập. Có thể mô hình hóa mỗi màu thành ghép cặp hai phía: một phía là các đường chéo \, phía kia là các đường chéo /; mỗi ô là một cạnh giữa hai đường chéo đi qua ô. Những đường chéo đã có + hoặc o bị loại. Một ghép cặp hai phía cực đại cho số tượng bổ sung tối đa.

Editorial còn đưa ra một tham lam tương đương. Xoay bàn \(45^\circ\) để một họ đường chéo thành hàng và họ kia thành cột. Trong từng màu, tập cột của một hàng ngắn là tập con của mọi hàng dài hơn. Đặt tượng ở một hàng hiện có ít ô nhất, chọn bất kỳ cột còn lại trong hàng ấy, rồi xóa hàng và cột. Lập luận đổi chỗ cho thấy lựa chọn này không làm giảm tối ưu: nếu một nghiệm tối ưu ghép hàng nhỏ với \(C'\) và hàng khác với \(C\), tính bao hàm cho phép hoán đổi \(C,C'\).

Tham lam quét ô từ trái sang phải, trên xuống dưới là sai; nó có thể khóa một cấu hình chỉ còn ba tượng trong khi tối ưu đặt được bốn. Điều quan trọng là ưu tiên đường chéo có ít lựa chọn nhất, hoặc dùng ghép cặp cực đại.

Sau khi ghép hai nghiệm, so với bàn ban đầu và chỉ in các ô đổi loại. Bài xe chạy \(O(N^2)\) hoặc tốt hơn; phần tượng dùng ghép cặp tăng luồng chuẩn trong \(O(VE)\) với \(V,E=O(N)\) và \(O(N^2)\) tương ứng (các cận nhanh hơn cũng đều đủ cho đề).

Ví dụ về phép tách và ghép

Xét cách bố trí ban đầu:

+..
+.o
x..

Tách thành bàn xe và bàn tượng tương ứng, trong đó mỗi o đóng góp ở cả hai bàn. Hai bàn tách ra chính xác là bàn xe ở bên trái và bàn tượng ở bên phải:

... +..
..x +.+
x.. ...

Giải độc lập hai bài con cho hai bàn chính xác sau:

.x. +..
..x +.+
x.. +..

+x.
+.o
o..

Lá x cũ ở góc dưới trái đã được nâng thành o. Ví dụ này cũng minh họa rằng việc ghép có thể nâng cấp quân cũ mà không làm thay đổi tính độc lập của hai loại ràng buộc.

Chứng minh tham lam cho tượng

Tách tiếp các ô “trắng” có \(R+C\) chẵn và ô “đen” có \(R+C\) lẻ; tượng không bao giờ đi từ màu này sang màu kia. Khi xoay riêng một màu của bàn \(45\) độ, một họ đường chéo trở thành hàng và họ còn lại thành cột. Trên bàn \(8\times8\) trống, các hàng có độ dài tăng rồi giảm; tập cột khả dụng của mọi hàng ngắn là tập con của mọi hàng dài hơn. Cụ thể, chỉ xét các ô “đen” rồi xoay bàn \(45^\circ\) theo chiều kim đồng hồ, ta được:

@@@..@@@
@@....@@
@......@
........
@......@
@@....@@
@@@..@@@

Trong hình này, mỗi dấu . là một ô đen thật của bàn cờ; các dấu @ không đại diện cho ô nào mà chỉ dùng để giúp định hướng hình đã xoay. Chẳng hạn, bốn ô đen ở hàng thứ hai của hình cũng xuất hiện trong mọi hàng có ít nhất bốn ô đen. Thuộc tính này đúng với mọi \(N\), cả hai màu, và vẫn đúng sau khi đặt tượng: xóa một hàng và một cột khiến mọi hàng còn lại cùng mất cột đó.

Vì thế hãy chọn hàng còn ít ô nhất, đặt vào một cột khả dụng bất kỳ, rồi xóa hàng và cột. Để chứng minh tối ưu, giả sử một nghiệm tối ưu ghép hàng nhỏ \(R\) với cột \(C'\) và hàng khác \(R'\) với cột \(C\) mà thuật toán muốn dùng cho \(R\). Do mọi cột của \(R\) đều có trong \(R'\), ta có thể đổi thành \((R,C)\) và \((R',C')\) mà không mất quân nào. Lập luận đổi chỗ này cho thấy lựa chọn tham lam luôn nằm trong một nghiệm tối ưu.

Không được thay bằng tham lam quét ô trái sang phải, trên xuống dưới. Phân tích đưa ra một bàn năm hàng dạng kim cương mà cách ấy đặt được chỉ ba tượng, trong khi sắp xếp theo hàng ít lựa chọn nhất đặt được bốn. Ba bàn cụ thể trong phản ví dụ đó là bàn ban đầu:

.@@@@
....@
...@@
..@@@
.@@@@

Tham lam sai chỉ đặt được ba tượng:

+@@@@
.+..@
..+@@
..@@@
.@@@@

Trong khi chiến lược đúng đặt được bốn tượng; đây là một bố trí tối ưu:

.@@@@
...+@
..+@@
.+@@@
+@@@@

Số xe tối đa luôn là \(N\), nhưng số tượng tối đa phụ thuộc các tượng đặt trước. Vì vậy hai test có cùng \(N\) vẫn có thể có điểm tối ưu khác nhau. Sau khi ghép, phải so từng ô với bàn ban đầu: chỉ in ô mới hoặc ô được nâng cấp, và không cần tối thiểu hóa số dòng thay đổi.

Phần trình bày dựa trên phân tích chính thức của Google Code Jam 2017, Qualification Round.