Ma trận tốt

Hướng tiếp cận

Quan sát rằng hai ô kề nhau khác nhau khi và chỉ khi ít nhất một thuộc tính của chúng khác nhau. Cách đơn giản nhất là làm cho tính chẵn lẻ (parity) của hai ô kề nhau khác nhau — vì nếu chúng có parity khác nhau thì chắc chắn giá trị khác nhau.

Nhận xét quan trọng

1. Ô bàn cờ kề nhau có $(i+j)$ khác parity. Nếu ta ép $b_{i,j}$ có parity bằng $(i+j)mod2$, thì hai ô kề nhau có parity khác nhau, tự khắc khác nhau.
2. Với mỗi ô, ta có hai lựa chọn $a_{i,j}$ hoặc $a_{i,j}+1$, parity của chúng khác nhau. Vậy luôn chọn được giá trị có parity mong muốn.
3. Bài toán liên hệ với CRT thông qua module $2$: sau phép biến đổi, mỗi ô $b_{i,j}\equiv (i+j)\left(\mathrm{mod}2\right)$.

Thuật toán

Với mỗi ô $(i,j)$:

1. Gọi $p=(i+j)mod2$.
2. Nếu $a_{i,j}mod2=p$, đặt $b_{i,j}=a_{i,j}$.
3. Ngược lại, đặt $b_{i,j}=a_{i,j}+1$ (parity đảo).

In ra ma trận $b$.

Độ phức tạp

• Thời gian: $O(nm)$ cho mỗi bộ test.
• Bộ nhớ: $O(nm)$.