Test Set 1

Test Set này có thể được giải bằng vét cạn. Ta thử liệt kê mọi mẫu liên thông có thể có. Với mỗi mẫu liên thông, kiểm tra xem nó có xuất hiện trong lưới đã được đi sâu hơn hai lần hay không. Trong số tất cả các mẫu liên thông xuất hiện trong lưới ấy, chọn mẫu có số ô lớn nhất. Tính đúng đắn của thuật toán sẽ được chứng minh trong phần này.

Lưu ý rằng chỉ kiểm tra mẫu trong lưới đã đi sâu hơn một lần là chưa đủ. Trường hợp mẫu đầu tiên trong đề cho thấy có một mẫu không xuất hiện sau một lần đi sâu, nhưng lại xuất hiện khi lưới đã đi sâu hơn nhiều hơn một lần.

Tại sao kiểm tra lưới đã đi sâu hơn hai lần lại đủ? Trước hết, quan sát rằng một lưới đã đi sâu hơn \(X\) lần gồm các khối ô; mỗi khối là một hình vuông toàn ô cùng màu, có cạnh dài \(2^X\). Do đó, mọi mẫu có kích thước không quá \(3\times4\) đều có thể nằm trong cùng một khối ở lưới đã đi sâu hai lần, trong khi điều này có thể không đúng ở lưới chỉ đi sâu một lần.

Hơn nữa, mọi mẫu có kích thước không quá \(3\times4\) giao với ít nhất một và nhiều nhất bốn khối trong lưới đã đi sâu hai lần. Điều tương tự cũng đúng trong lưới đã đi sâu nhiều hơn hai lần. Vì vậy, tập các mẫu kích thước không quá \(3\times4\) xuất hiện trong lưới đã đi sâu hai lần chính là tập các mẫu kích thước không quá \(3\times4\) xuất hiện trong lưới đã đi sâu \(X\) lần với mọi \(X>2\). Bởi thế, kiểm tra lưới đã đi sâu hai lần là đủ.

Có nhiều nhất \(O(2^{RC})\) mẫu, nên số mẫu liên thông có thể có cũng không vượt quá \(O(2^{RC})\). Với mỗi mẫu, trước tiên kiểm tra tính liên thông; nếu liên thông, tiếp tục kiểm tra nó có xuất hiện trong lưới đã đi sâu hai lần hay không trong thời gian \(O(RC)\). Tổng độ phức tạp là

đủ nhanh cho Test Set 1.

Test Set 2

Vì \(R\) và \(C\) có thể lên đến 20, lời giải số mũ sẽ không chạy kịp. Do đó, ta không thể liệt kê mọi mẫu liên thông. Để giải Test Set này, trước hết quan sát rằng một khối ô trong lưới đã đi sâu ít nhất một googol lần sẽ có cạnh dài hơn kích thước của mọi mẫu có thể có.

Nhận xét trên đảm bảo rằng mọi mẫu có thể có chỉ giao với nhiều nhất bốn khối ô trong lưới sâu hơn. Điều này có nghĩa là mẫu của Codd phải có thể được một đường ngang và một đường dọc chia thành bốn góc phần tư, sao cho mọi ô của mẫu nằm trong cùng một góc phần tư đều có cùng màu. Hơn nữa, tổ hợp cụ thể của bốn màu ấy phải xuất hiện trong lưới ban đầu.

Vì vậy, ta xét mọi tâm góc phần tư và mọi tổ hợp màu có thể có; tổng cộng tối đa \(O(2^4RC)\) trường hợp. Với mỗi tâm và tổ hợp màu, ta cần tìm thành phần liên thông lớn nhất mà mỗi ô trong thành phần có màu đúng bằng màu được gán cho góc phần tư chứa nó.

Với mỗi tâm góc phần tư và tổ hợp màu, cần \(O(RC)\) thời gian để tìm thành phần liên thông lớn nhất. Do đó, lời giải chạy trong

thời gian.

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