Test Set 1: vét cạn cách điền từng ô

Trong Test Set 1, chiếc bánh có nhiều nhất 12 ô. Một chiến lược vét cạn khả thi là thử mọi cách điền mỗi ô trống bằng từng chữ cái đã có trên bánh. Nếu đã có \(L\) chữ cái thì mỗi trong số \(12-L\) ô còn lại có \(L\) lựa chọn, nên số tổ hợp cần thử là \(L^{12-L}\), nhỏ hơn rất nhiều so với \(12^{12}\). Với \(1\le L\le12\), giá trị lớn nhất là \(5^7=78125\), khá nhỏ đối với máy tính.

Để kiểm tra một chiếc bánh đã điền, có thể quét toàn bộ bánh từ trái sang phải, từ trên xuống dưới và ghi nhận cho mỗi chữ cái: vị trí trên-trái nhất, vị trí dưới-phải nhất và số lần xuất hiện. Sau đó, với từng chữ, kiểm tra hình chữ nhật được xác định bởi hai vị trí ấy chỉ chứa chữ đó và diện tích của nó bằng số lần xuất hiện.

Test Set 1: vét cạn cách mở rộng hình chữ nhật

Một chiến lược khác là bắt đầu tại một chữ cái, vẽ quanh nó một hộp bao chỉ chứa thêm các dấu ?, rồi chuyển sang chữ khác, v.v. Trong Test Set 1 có tương đối ít cách chọn các hộp bao. Chỉ cần dùng các chữ cái có sẵn để cắt tỉa những hộp bao không thể dùng, đồng thời kiểm tra cẩn thận sự chồng lấn và các ô bị bỏ trống, tìm kiếm vét cạn sẽ đủ nhanh.

Tuy nhiên, những chiến lược không vét cạn có vẻ tương tự có thể thất bại. Xét thuật toán sau: với mỗi chữ, bắt đầu bằng hộp \(1\times1\) chỉ chứa chữ đó; kéo hộp xa nhất có thể lên trên và xuống dưới mà không gặp chữ khác, rồi kéo xa nhất có thể sang trái và phải mà không gặp chữ khác. Tùy thứ tự xử lý các chữ, thuật toán có thể thất bại. Chẳng hạn:

A?B
C??
??D
?EF

Nếu xử lý theo thứ tự từ trái sang phải, từ trên xuống dưới, thuật toán sẽ điền lưới như sau và để lại một dấu ? chưa được điền:

AAB
C?B
CDD
CEF

Test Set 2: chia để trị đệ quy

Rất phù hợp với một bài toán về bánh, Test Set 2 có một chiến lược chia để trị đơn giản. Nếu chiếc bánh chỉ có một chữ cái, điền toàn bộ bánh bằng chữ đó. Nếu không, ta có thể thực hiện một đường cắt ngang hoặc dọc chia bánh thành hai chiếc bánh con, sao cho mỗi phần có ít nhất một chữ cái; từ đó tạo ra hai bài toán cùng dạng.

Khi bánh có ít nhất hai chữ cái, luôn tồn tại một đường cắt như vậy. Một cách chắc chắn là chọn một cặp chữ: đặt đường phân chia đi qua biên phải của chữ nằm bên trái hơn; nếu hai chữ cùng cột thì đặt đường cắt qua biên dưới của chữ nằm phía trên.

Test Set 2: tham lam

Cũng có một cách đơn giản không cần đệ quy. Trước hết, trong từng hàng, kéo mỗi chữ cái hiện có sang tất cả các ô bên phải nó cho tới khi gặp chữ cái hiện có tiếp theo hoặc mép bánh. Sau đó, nếu hàng có chữ, kéo chữ hiện có bên trái nhất sang mọi ô phía trái nó.

Lúc này, những hàng ban đầu không có chữ vẫn còn trống. Quét lưới từ hàng thứ hai xuống hàng cuối; mỗi khi gặp hàng trống, thay nó bằng hàng ngay phía trên. Sau đó quét thêm một lượt từ hàng áp chót lên hàng đầu; mỗi khi gặp hàng trống, thay nó bằng hàng ngay phía dưới.

Không khó để chứng minh chiến lược này không thể tạo ra một miền không phải hình chữ nhật cho bất kỳ chữ nào, không thể tạo ra hai miền rời nhau cho cùng một chữ, và cũng không thể để lại ô nào chưa điền.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2017, Round 1A, bài Alphabet Cake.