Bài VOBOARD ban đầu mình chỉ cho K = 2, dùng làm bài dễ ^_^. Sau đó được
alex_pythagore và
flash_mt cải tiến.
Dưới đây là tóm tắt thuật toán:
Mở rộng 1: khi K > 2.
Đổi: 0 → 1, 1 → 2, …, K - 1 → 0
Cách thường O(K(M+N)) (trung bình)
Đầu tiên đổi các hàng sao cho các ô trên cùng cột có giá trị bằng nhau (K cách). Sau đó đổi cột.
Cách O(max (M,N)(M+N)) (cho K = 10^9, khó)
M >= N: nếu tất cả các hàng đều đổi, ta giảm 1 tất cả các hàng. Lúc này số lần đổi cột tăng 1 hoặc giảm K-1 cho mỗi cột. Suy ra cách giảm 1 các hàng tối ưu hơn. Suy ra tồn tại ít nhất 1 hàng ko đổi.
Ngược lại N > M, làm ngược lại, suy ra ít nhất 1 cột không đổi.
Được ưa thích: 0
