Phân tích: The Paths of Yin Yang

Ấn tượng ban đầu

Người ta có thể khám phá ra một loạt các quan sát khi giải bài toán này. Một số quan sát là hiển nhiên, trong khi những quan sát khác đòi hỏi sự nỗ lực và cảm hứng. Thuật toán của chúng tôi tìm kiếm tất cả các giải pháp khả thi và đếm chúng. Hãy tưởng tượng bạn là một thám tử đối mặt với một bảng hình chữ nhật trống. Công việc của bạn là tiết lộ tất cả các giải pháp có thể, một cách nhanh chóng.

Đối với bất kỳ giải pháp nào, như đề bài đã nêu, hầu hết các điểm đều có bậc (số ô láng giềng cùng màu với chính nó) là 2; và có đúng 4 điểm có bậc là 1. Hãy gọi các điểm có bậc 1 là điểm đầu mút.

Một khi chúng ta đã quyết định tất cả các bậc, chúng ta có thể thử khôi phục màu sắc của mỗi ô bằng cách tìm kiếm vét cạn. Giả sử trong một trường hợp tổng quát, chúng ta đã tô màu một ô A, và chúng ta cũng đã tô màu tất cả trừ một ô láng giềng B của nó, thì chúng ta không cần phải thử cả đen và trắng cho B, nó đã được quyết định bởi màu của các ô khác và bậc của A.

Điều này mang lại cho chúng ta một cách nhanh hơn nhiều để khôi phục tất cả các giải pháp so với việc tìm kiếm mù quáng. Có thể thấy rằng nếu tất cả các màu của hàng đầu tiên được quyết định, và chúng ta tiến hành từ trên xuống dưới, thì ở mỗi bước chúng ta luôn có một ô (thực tế là gần M ô) ở trong tình huống giống như ô A ở trên. Vì vậy, một khi chúng ta quyết định tổ hợp (màu của hàng đầu tiên, vị trí của 4 điểm đầu mút), tất cả những gì chúng ta phải làm là kiểm tra trong thời gian \(O(NM)\) xem một giải pháp có xuất hiện hay không.

Có \(2^M\) cách để tô màu hàng đầu tiên, và \(\Theta((NM)^4)\) cách để chọn các điểm đầu mút. Cả hai con số này đều quá lớn. Người ta có thể dễ dàng thấy hầu hết các cách tô màu \(2^M\) của hàng đầu tiên sẽ rõ ràng thất bại trong việc đưa ra giải pháp, như chúng ta sẽ thảo luận trong phần tiếp theo. Sau đó, chúng ta sẽ nghiên cứu cách giảm số lượng vị trí cho các điểm đầu mút.

Một chút về Topo

Thay vì nhìn vào hàng đầu tiên, hãy xem xét vòng ngoài của bảng. Đó là các vị trí trên biên. Dễ dàng thấy rằng chúng không thể cùng một màu -- vòng ngoài phải chứa cả ô đen và ô trắng.

Chúng ta có thể nói nhiều hơn về vòng ngoài. Nó phải là chính xác một đoạn các ô đen, và phần còn lại là chính xác một đoạn các ô trắng! Lý do có thể được nhìn thấy từ hình bên trái phía dưới. Nếu có ít nhất hai đoạn đen (và do đó ít nhất hai đoạn trắng), không có cách nào người ta có thể kết nối cả các mảnh đen và các mảnh trắng từ bên trong bảng.

Hình thứ hai cho thấy một cấu hình bị cấm đối với một hình vuông \(2 \times 2\). Nếu chúng ta có tình huống giống như bàn cờ, không có cách nào để kết nối cả hai ô đen và cả hai ô trắng.

Vị trí cho các điểm đầu mút

Giả sử A là một điểm đầu mút trắng, và B là láng giềng trắng duy nhất của nó, như trong hình dưới đây.

• Vì A không có láng giềng trắng nào khác, nên các vị trí được đánh dấu 1 phải là màu đen.
• Để tránh bàn cờ \(2 \times 2\), các vị trí được đánh dấu 2 cũng phải là màu đen.
• Vì hàng đầu tiên được đánh dấu 1 và 2 không có láng giềng đen nào khác, nên các vị trí được đánh dấu 3 phải là màu trắng.
• Để tránh bàn cờ \(2 \times 2\), các vị trí được đánh dấu 4 cũng phải là màu trắng.

Suy luận này có thể tiếp tục cho đến khi chúng ta chạm vào biên của bảng. Trong hình của chúng ta, X là một điểm trên biên, và nó cũng là nơi các ô đen và trắng gặp nhau trên biên. Tuy nhiên, chúng ta có thể tiếp tục suy luận theo hướng khác, cho đến khi chúng ta cũng nhận được một điểm Y trên biên.

Điều này mang lại một mối liên hệ tốt đẹp giữa các điểm đầu mút và vòng ngoài. Từ một điểm đầu mút, chúng ta vẽ hai tia chéo (cả hai đều tạo góc 135 độ với láng giềng cùng màu của nó), cả hai tia đều chạm vào biên tại một góc, hoặc tại một điểm nơi các ô đen và trắng gặp nhau trên vòng ngoài.

Hãy tóm tắt thuật toán của chúng tôi. Chúng ta bắt đầu bằng cách cố định vòng ngoài là một đoạn các ô đen và phần còn lại màu trắng. Sau đó, từ mỗi góc chúng ta vẽ một đường chéo; cũng từ mỗi điểm trên vòng ngoài nằm cạnh một màu khác trên vòng, chúng ta vẽ một đường chéo đi xa khỏi láng giềng có màu khác đó. Như vậy chúng ta có 8 đường chéo. Các đường chéo này sẽ tạo ra không quá 16 giao điểm. Đó là tất cả các vị trí khả thi cho các điểm đầu mút.

Có \(O((N+M)^2)\) cách để cố định vòng ngoài, và do đó có \(O((N+M)^2)\) cách để cố định vòng ngoài và các điểm đầu mút. Với mỗi cách này, người ta có thể kiểm tra xem một giải pháp có xuất hiện hay không trong thời gian \(O(MN)\). Vì vậy, thời gian chạy là \(O(MN(N+M)^2)\). Hằng số không phải là rất nhỏ, nhưng có thể chấp nhận được. Và người ta có thể giảm nó bằng cách sử dụng tính đối xứng.

Dưới đây là một trong những giải pháp tốt. Chúng ta có thể thấy các điểm đầu mút và vòng ngoài được kết nối bởi các đường chéo như thế nào.

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