Những nhận xét ban đầu

Các nhận xét quan trọng đầu tiên là:

• Một ô chỉ có thể mang giá trị 1, 2 hoặc 3. Các số 4 sẽ phải tiếp tục lan truyền cho tới khi chạm một ô biên, nhưng ô biên chỉ kề ba ô khác.
• Nếu xuất hiện số 3, nó phải nằm trong một dải gồm trọn vẹn hai hàng. Đặt một số 3 trên biên trên của trống: cả ba ô kề nó đều phải là 3, điều này tiếp diễn quanh toàn bộ hàng trên và đồng thời lấp hàng bên dưới. Giả sử tồn tại một bố trí hữu hạn khác của số 3; khi đó phải có một ô 3 cao nhất mà phía trên không thể đặt thêm số 3, nhưng cũng theo lập luận vừa rồi, ô ấy chỉ có thể thuộc một dải hai hàng số 3.
• Nếu xuất hiện số 2, nó phải thuộc một hình vuông \(2\times2\) toàn số 2, hoặc thuộc một đường số 2 (có thể uốn lượn) đi hết một vòng quanh trống rồi nối lại với chính nó.
• Các số 1 chỉ có thể xuất hiện thành những "domino" gồm hai ô kề nhau.

Ngoài các dải số 3, có bốn mẫu dùng số 1 và 2:

I. Dải số 2 dày một hàng:

2...

II. Xen kẽ domino số 1 dựng đứng và hình vuông \(2\times2\) số 2:

122...
122...

III. Một đường số 2 uốn quanh các domino số 1 nằm ngang:

222112...
112222...

IV. Một đường số 2 uốn quanh các domino số 1 dựng đứng:

2212...
1212...
1222...

Không mẫu nào trong bốn mẫu này có thể giáp trực tiếp một mẫu khác, nhưng chúng có thể được ngăn cách bởi các dải số 3. Số cột của trống có thể loại một số mẫu: II, III, IV lần lượt đòi hỏi số cột là bội của 3, 6, 4.

Quy hoạch động theo hàng và chu kỳ

Bây giờ dùng quy hoạch động để gán các mẫu cho trống. Trạng thái trước hết gồm số hàng đã lấp và việc mẫu trước đó có phải một cặp hàng số 3 hay không.

Mỗi trong năm mẫu lặp lại với một chu kỳ \(P\) thuộc \(\{1,3,4,6\}\), nên có \(P\) cách đặt mẫu đó quanh trống.

Mỗi cách gán cho toàn bộ trống cũng có một chu kỳ, là bội chung nhỏ nhất của chu kỳ mọi mẫu có trong nó.

Một rắc rối nữa là các cách gán chỉ khác nhau bởi phép quay phải được tính là một. Vì vậy, trạng thái DP còn phải chứa chu kỳ của cách gán hiện tại. Khi tính đáp án cuối, chia số lời giải trong mỗi trạng thái cho chu kỳ của trạng thái đó. Ví dụ, nếu có 18 cách tạo một lời giải chu kỳ 3, chúng chỉ tương ứng với 6 cách trang trí khác nhau.

Một cách khác để xử lý các mẫu tương đương là dùng bổ đề Burnside. Chi tiết được để lại như một bài tập cho người đọc!

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