Test Set 1

Trong Test Set 1, ta chỉ cần thực hiện một đường cắt ngang và một đường cắt dọc. Có \(R-1\) vị trí cắt ngang và \(C-1\) vị trí cắt dọc khả dĩ, nên tổng cộng có \((R-1)\times(C-1)\) cách thực hiện hai đường cắt. Vì \(R\) và \(C\) đều không quá 10, số cách nhiều nhất là 81 và ta có thể thử riêng từng cách. Với mỗi cách, đếm số hạt sô-cô-la trong bốn miếng thu được. Nếu từng gặp một cách mà cả bốn miếng có cùng số hạt, đáp án là POSSIBLE; nếu không, đáp án là IMPOSSIBLE.

Test Set 2

Trong Test Set 2, ta có thể phải thực hiện nhiều đường cắt ngang và dọc, và có quá nhiều cách để kiểm tra hết. Trường hợp xấu nhất xảy ra khi \(H\) gần bằng một nửa \(R-1\), còn \(V\) gần bằng một nửa \(C-1\); số cách đặt các đường cắt có thể vượt quá \(10^{57}\)! Vì vậy, ta cần một cách tiếp cận khác.

Trước hết chỉ xét các đường cắt ngang và tạm thời bỏ qua đường cắt dọc. Các đường cắt ngang chia chiếc waffle thành từ hai “lát” ngang trở lên. Mỗi lát này sẽ trở thành đúng \(V+1\) miếng khi ta thực hiện các đường cắt dọc. Đây là quan sát then chốt: nếu đáp án là POSSIBLE, tất cả các miếng phải có đúng cùng số hạt; vì mỗi lát ngang tạo ra đúng cùng một số miếng, tất cả lát ngang cũng phải có đúng cùng số hạt. Hơn nữa, ta biết chính xác con số ấy: nếu toàn bộ chiếc waffle có tổng cộng \(K\) hạt, mỗi trong số \(H+1\) lát ngang phải có đúng \(K/(H+1)\) hạt, nếu không đáp án là IMPOSSIBLE.

Quan sát này mạnh đến mức cho ta biết phải cắt ở đâu nếu đáp án là POSSIBLE! Ta lập danh sách số hạt trên từng hàng, rồi đổi nó thành tổng tích lũy của số hạt đã gặp. Chẳng hạn, với một chiếc waffle có bảy hàng lần lượt chứa \(3,7,6,2,2,0,10\) hạt, danh sách tổng tích lũy là \([3,10,16,18,20,20,30]\). Trong ví dụ này, nếu \(H=2\), ta biết phải cắt ngay dưới các hàng tại đó tổng đạt 10 và 20, tức ngay dưới hàng thứ hai và thứ năm. (Ta cũng có thể đặt đường cắt thứ hai dưới hàng thứ sáu, nhưng điều này không tạo ra khác biệt.) Tuy nhiên, nếu \(H=1\), ta cần đặt đường cắt duy nhất ngay dưới một hàng làm tổng đạt 15, mà không có hàng nào như vậy. Vì thế, sau bước này, hoặc ta biết đáp án là IMPOSSIBLE, hoặc biết chính xác nơi đặt các đường cắt ngang.

Tiếp đó, ta chỉ xét các đường cắt dọc bằng phương pháp tương tự, rồi hoặc tìm được vị trí cần cắt, hoặc kết luận IMPOSSIBLE. Tuy nhiên, ngay cả khi đã biết vị trí các đường cắt ngang và dọc, ta vẫn chưa xong! Những đường cắt đó có thể không thực sự tạo ra các miếng có cùng số hạt. Chẳng hạn, với \(H=1\), \(V=1\) và chiếc waffle sau:

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

ta suy ra rằng nếu đáp án là POSSIBLE, phải cắt ngang dưới hàng thứ hai và cắt dọc bên phải cột thứ hai. Nhưng cách này tạo ra hai miếng có bốn hạt mỗi miếng và hai miếng hoàn toàn không có hạt, nên đáp án phải là IMPOSSIBLE.

Để kiểm tra mỗi miếng có cùng số hạt, trước hết ta có thể biến danh sách đường cắt ngang thành danh sách các đoạn. Ví dụ, nếu cắt dưới hàng thứ hai và thứ năm trong ví dụ \([3,10,16,18,20,20,30]\) ở trên, ta có các đoạn đóng \([1,2]\), \([3,5]\), \([6,7]\). Làm tương tự với các đường cắt dọc, rồi lặp hai vòng trên hai tập đoạn này và kiểm tra từng ô trong mỗi cặp đoạn. Nếu đáp án là POSSIBLE, mỗi miếng phải có đúng

hạt; vì vậy, nếu gặp một miếng không thỏa điều này, đáp án là IMPOSSIBLE. Nếu không, cuối cùng ta đã chứng minh đáp án thực sự là POSSIBLE. (Một lần nữa, lưu ý rằng nếu có nhiều lựa chọn cho một hay nhiều đường cắt, nguyên nhân chỉ có thể là các hàng hoặc cột trống; chúng không ảnh hưởng đến số hạt trong mỗi miếng.)

(Có những cách khác để kiểm tra các miếng. Chẳng hạn, ta có thể duyệt dữ liệu một lần và với mỗi ô, tính số hạt sô-cô-la trong hình chữ nhật có ô đó là góc dưới bên phải và góc trên bên trái của chiếc waffle là góc trên bên trái. Sau đó, để tìm số hạt trong một miếng cụ thể, ta cộng và trừ các hình chữ nhật thích hợp trong tập này.)

Tóm lại, thuật toán gồm các bước:

1. Tạo mảng tổng theo hàng và tổng theo cột. Ta có thể duyệt riêng mọi ô hai lần, hoặc duyệt một lần để tạo đồng thời cả hai mảng.
2. Chuyển các mảng tổng thành mảng tổng tích lũy.
3. Kiểm tra các mảng tổng tích lũy để tìm vị trí cắt.
4. Dùng các mảng tổng tích lũy để tạo các mảng đoạn.
5. Duyệt có định hướng qua mọi ô của chiếc waffle, dùng các mảng đoạn để kiểm tra liệu mọi miếng có cùng số hạt hay không.

Các bước 1 và 5 phải xét từng ô trong số \(R\times C\) ô của chiếc waffle, còn các bước 2, 3 và 4 chỉ xét \(R\) hoặc \(C\) giá trị. Vì vậy, bước 1 và 5 chi phối thời gian chạy, cho độ phức tạp \(O(R\times C)\). (Dù sao ta cũng không thể làm tốt hơn, vì rõ ràng phải xem mỗi ô của chiếc waffle ít nhất một lần để giải bài toán.)

Nguồn

Dịch đầy đủ từ phân tích chính thức của Google Code Jam 2018, Round 1A, bài Waffle Choppers.