Ta có thể đảo ngược bài toán như sau: Cho các ô vuông, ban đầu chưa được tô màu nào. Bạn có thể thực hiện thao tác sau bất kỳ số lần nào: Chọn ô vuông liên tiếp và tô màu trắng hoặc đen. Tuy nhiên, mỗi ô vuông sẽ mang màu đầu tiên mà nó được tô (các lần tô tiếp theo không thay đổi màu của nó).
Khi đó, với mỗi đoạn ô vuông liên tiếp, ta có thể tô màu trắng hoặc đen cho
ô vuông đó, các ô còn lại đều có thể tô màu trắng hoặc đen tùy ý. Từ đó, ta có thể duyệt qua tất cả các đoạn
ô vuông liên tiếp và tìm cách tô tốt nhất với độ phức tạp
.
Ta có thể sử dụng Tổng tiền tố (Prefix Sum) để tính toán trong .
Comments