Phân tích: Havannah

Thoạt nhìn, bài toán này có lẽ hơi đáng sợ với nhiều thí sinh. (Riêng tác giả còn nhớ vài bài lục giác rất khó ở các cuộc thi khác.) Tuy nhiên, bài này không tệ như vẻ ngoài của nó.

Trước hết, hãy xem trên bàn cờ có những loại ô nào và cách phân biệt chúng:

• Ô bên trong: không thuộc biên bàn cờ và có 6 ô kề.
• Ô góc: nằm tại nơi hai cạnh của bàn cờ gặp nhau và có 3 ô kề.
• Ô cạnh: không phải ô bên trong cũng không phải ô góc và có 4 ô kề.

Điều hơi trái trực giác là ô góc không được tính là ô cạnh, dù trên thực tế nó nằm trên các cạnh. Tuy nhiên đề đã quy định rõ: “Các góc không được tính là cạnh.”

Ta có thể đánh số riêng sáu cạnh và sáu góc từ \(0\) đến \(5\). Để thuận tiện về sau, giữ chỉ số \(0\) đến \(5\) cho góc và cộng \(6\) vào chỉ số cạnh, nên các cạnh có chỉ số \(6\) đến \(11\). Ô nào không phải góc và không thuộc cạnh nào được đánh dấu \(-1\). Như vậy, ta xây dựng hàm int checkType(row, col) cho biết ô \((row,col)\) là góc nào, thuộc cạnh nào, hay không thuộc loại nào trong hai loại đó.

Các góc là
\(\{(1,1),(1,S),(S,2S-1),(2S-1,2S-1),(2S-1,S),(S,1)\}\).

Các ô cạnh gồm \((1,X)\), \((X,1)\), \((X,2S-1)\), \((2S-1,X)\) với \(X\) nguyên, cùng mọi ô thỏa \(|row-col|=S-1\). Đừng quên loại các góc khi kiểm tra cạnh.

Các hình chiến thắng

• Cầu (Bridge): đơn giản nhất; một tập quân nối hai ô góc bất kỳ. Số quân ít nhất để tạo cầu là \(2\) trên bàn \(S=2\), cũng là bàn nhỏ nhất có thể.
• Nĩa (Fork): phức tạp hơn một chút; một tập quân nối ba cạnh phân biệt. Số quân ít nhất là \(5\) trên bàn \(S=3\) (bàn \(S=2\) không có ô cạnh).
• Vòng (Ring): phức tạp nhất; một tập quân bao quanh một ô trống. Vì “bao quanh” có thể chưa rõ, đề bài đã giải thích chi tiết và cho ví dụ. Số quân ít nhất là \(6\) trên bàn \(S=3\). Trên bàn \(S=2\), vòng là không thể vì nó tất yếu tạo cầu trước.

Nhiều thí sinh có thể nhận ra cầu và nĩa tương đối dễ phát hiện. Có thể tìm kiếm nhị phân nước đi tạo ra chúng rồi kiểm tra xem cầu hoặc nĩa đã tồn tại chưa. Cách này đúng cho hai hình đó nhưng không dùng được cho vòng. Một số người dùng lời giải ấy cho cầu và nĩa, rồi một lời giải khác cho vòng; tuy nhiên, điều đó đòi hỏi thêm mã nguồn, hiếm khi là ý hay trong một cuộc thi tốc độ.

Một lời giải \(O(M^2)\) thực ra cũng đủ nhanh. Dù vậy, ta sẽ mô tả lời giải \(O(M)\), vừa rất nhanh vừa không khó cài hơn nhiều.

Trước tiên nên lưu bàn cờ theo cách tiết kiệm cả bộ nhớ lẫn thời gian. Khi bàn rất lớn, nó cũng rất thưa: chỉ có \(10000\) quân trên hơn \(9000000\) ô. Vì vậy, hãy dùng một cấu trúc tập hợp của ngôn ngữ. Trong C++, bảng băm là nhanh nhất nhưng cây cân bằng như std::set cũng đủ. Thêm quân tốn thời gian hằng số với bảng băm và logarithm với cây cân bằng.

Ta đặt các quân theo thứ tự đã cho và cần nhanh chóng kiểm tra liệu quân mới có tạo hình chiến thắng hay không. Cầu và nĩa yêu cầu các ô thuộc cùng một thành phần liên thông; vòng cũng vậy. Đây là bài toán điển hình cho union-find. Nhắc lại, union-find hỗ trợ:

• tạo một nút mới trong nhóm kích thước \(1\);
• gộp hai nhóm thành một;
• tìm nhóm chứa một nút.

Nếu cài đặt đúng, cả ba thao tác đều cực nhanh.

Ta thêm một chút thông tin vào union-find. Khi đặt quân, kiểm tra những ô kề đã có quân. Nếu không có, tạo thành phần riêng cho quân mới; nếu có, gộp tất cả thành phần ấy cùng quân mới. Mỗi thành phần còn lưu các loại ô mà nó chứa. Vì chỉ quan tâm \(12\) loại, ta dùng mặt nạ \(12\) bit tương ứng với các chỉ số \(0\) đến \(11\). Khi gộp thành phần \(A\) vào \(B\), OR mặt nạ của \(A\) vào mặt nạ của \(B\). Nếu sau khi gộp, thành phần có ít nhất hai bit bật trong sáu bit đầu hoặc ít nhất ba bit bật trong sáu bit sau, ta vừa tạo lần lượt một cầu hoặc một nĩa.

Phát hiện vòng

Ta vẫn cần xử lý vòng. Muốn tạo vòng, quân vừa thêm phải nối một thành phần với chính nó. Tuy nhiên, chỉ điều đó chưa chắc đã tạo vòng. Ta kiểm tra mọi ô kề quân mới và tìm hai ô có quân thuộc cùng một thành phần.

Biểu diễn sáu ô kề như sau:

# 1 2
6 * 3
5 4 #

Đi hai vòng theo chiều kim đồng hồ — hoặc ngược chiều, không có khác biệt — qua dãy \(12\) ô kề lặp lại. Ta cần tìm một trong các dãy con sau:

• \(\{C,X_1,C,Y_1,Y_2,Y_3\}\);
• \(\{C,X_1,X_2,C,Y_1,Y_2\}\);
• \(\{C,X_1,X_2,X_3,C,Y_1\}\),

trong đó hai ô \(C\) thuộc cùng một thành phần; mỗi ô \(X\) và \(Y\) hoặc trống, hoặc thuộc một thành phần bất kỳ — không nhất thiết là thành phần của \(C\), cũng không nhất thiết giống các \(X\), \(Y\) khác.

Sau nước đi này, một vòng được tạo ra khi và chỉ khi:

• ít nhất một ô \(X\) là ô trống;
• ít nhất một ô \(Y\) là ô trống.

Nếu có dãy \(\{C,X_1,C,Y_1,Y_2,Y_3\}\) thì cũng sẽ có một dãy \(\{C,X_1,X_2,X_3,C,Y_1\}\); ta vẫn liệt kê cả hai để diễn giải rõ hơn.

Vì sao phép kiểm tra đúng? Nếu không có ô \(X\) trống hoặc không có ô \(Y\) trống, hai ô \(C\) vốn đã nối với nhau “từ phía đó”; thêm quân mới hiển nhiên không biến đường nối ấy thành vòng. Ngược lại, nếu cả phía \(X\) lẫn phía \(Y\) đều có ô trống, ta vừa bao quanh ít nhất một trong chúng. Hãy hình dung đường tròn có hai phía: trong và ngoài. Ta biết mình vừa tạo một đường tròn vì đang nối một thành phần với chính nó, nhưng chưa biết phía nào là trong. Khi cả hai phía đều chứa ô trống, chắc chắn phía trong chứa ít nhất một ô trống.

Độ phức tạp

Phép OR tốn thời gian hằng số; kiểm tra cầu hoặc nĩa chỉ xét một số bit cố định; kiểm tra vòng cũng chỉ thực hiện số thao tác cố định bằng số ô kề. Vì vậy độ phức tạp do các thao tác union-find chi phối: \(O(M\,\alpha(M))\), với \(\alpha\) là hàm nghịch đảo Ackermann. Hàm này tăng chậm đến mức có thể xem thuật toán gần như \(O(M)\) dưới các ràng buộc đã cho.

Ghi chú

Một mẹo hay khác để xử lý vòng là bắt đầu từ trạng thái đã đặt mọi quân rồi đi ngược thời gian, luôn theo dõi những ô trống nào nối với nhau. Bỏ một quân có thể nối hai thành phần ô trống, nên lại có thể dùng union-find để cập nhật nhanh. Cách này đơn giản hơn về mặt ý tưởng, nhưng chậm hơn vì ban đầu phải tìm tất cả thành phần liên thông sau khi mọi quân đã được đặt.

Dựa trên phân tích chính thức của Google Code Jam.