Lời giải

Điều kiện của bảng nhìn qua có vẻ phụ thuộc vào từng ô, nhưng thật ra mỗi ô chỉ so sánh tổng hàng của nó với tổng cột của nó. Vì vậy ta thử quên từng ô riêng lẻ đi và gom các hàng, cột theo tổng của chúng.

Gọi ~r_i~ là tổng hàng ~i~, ~c_j~ là tổng cột ~j~. Với một giá trị ~v~, đặt ~R_v~ là số hàng có tổng bằng ~v~, và ~C_v~ là số cột có tổng bằng ~v~.

Nếu một hàng có tổng ~v~, những ô sáng trên hàng đó là những cột có tổng cũng bằng ~v~. Số ô sáng trên hàng này vì thế bằng ~C_v~. Nhưng tổng hàng lại đang là ~v~, nên ta bắt buộc có:

~C_v = v~.

Lập luận tương tự cho một cột có tổng ~v~ cho ta:

~R_v = v~.

Vậy mỗi giá trị dương ~v~ xuất hiện trong bảng phải tạo thành đúng ~v~ hàng và đúng ~v~ cột cùng tổng ~v~. Giao của chúng là một khối ~v \times v~ toàn số ~1~, đóng góp ~v^2~ vào độ sáng.

Còn các hàng hoặc cột có tổng ~0~ thì sao? Chúng được phép tồn tại ở phía dư ra. Nhưng không thể có đồng thời một hàng tổng ~0~ và một cột tổng ~0~, vì ô giao của chúng có hai tổng bằng nhau nên phải là ~1~, làm cho hàng và cột đó không còn tổng ~0~ nữa.

Do đó phía nhỏ hơn giữa số hàng và số cột phải được phủ hết bởi các nhóm dương. Nếu đặt:

~K = \min(N,M)~,

bài toán còn lại là chọn các số nguyên dương phân biệt có tổng ~K~, sao cho tổng bình phương của chúng nhỏ nhất.

Tại sao các số phải phân biệt? Vì mỗi giá trị tổng ~v~ chỉ có một nhóm gồm ~v~ hàng và ~v~ cột. Hai nhóm cùng kích thước ~v~ thật ra sẽ gộp thành ~2v~ hàng có cùng tổng ~v~, mâu thuẫn với yêu cầu ~R_v=v~.

Bây giờ ta chỉ còn bài toán số học. Muốn tổng bình phương nhỏ, các phần nên càng nhỏ và càng cân bằng càng tốt. Vì các phần dương phân biệt, cách lấy được nhiều phần nhất là bắt đầu từ:

~1,2,\ldots,p~,

với ~p~ lớn nhất thỏa:

~\frac{p(p+1)}{2} \le K~.

Gọi:

~rem = K - \frac{p(p+1)}{2}~.

Ta cộng thêm ~1~ vào ~rem~ số lớn nhất trong dãy ~1,2,\ldots,p~. Làm vậy vẫn giữ các phần phân biệt, đồng thời phân phối phần dư cân bằng nhất có thể.

Đáp án ban đầu là:

~1^2 + 2^2 + \cdots + p^2~.

Khi tăng các số ~p-rem+1,p-rem+2,\ldots,p~ thêm ~1~, tổng bình phương tăng thêm:

~\sum_{k=p-rem+1}^{p} ((k+1)^2-k^2) = \sum_{k=p-rem+1}^{p} (2k+1)~.

Công thức này chính là phần được cộng thêm trong chương trình.

Chứng minh đúng đắn

Xét một bảng đồng bộ bất kỳ. Với mỗi giá trị dương ~v~, mọi hàng có tổng ~v~ chỉ sáng ở các cột có tổng ~v~, nên số ô sáng trên hàng đó là ~C_v~. Vì tổng hàng bằng ~v~, suy ra ~C_v=v~. Tương tự, từ phía cột suy ra ~R_v=v~. Vì thế mỗi giá trị dương ~v~ tạo ra đúng một khối ~v \times v~ toàn số ~1~ và đóng góp ~v^2~.

Không thể còn dư cả hàng tổng ~0~ và cột tổng ~0~, vì ô giao giữa chúng phải sáng do hai tổng bằng nhau, mâu thuẫn với tổng ~0~. Do đó tổng kích thước các nhóm dương phải bằng ~\min(N,M)~. Mọi bảng hợp lệ vì thế tương ứng với một cách phân tích ~K~ thành các số dương phân biệt, và độ sáng bằng tổng bình phương của các số đó.

Ngược lại, với bất kỳ phân tích ~K~ thành các số dương phân biệt, ta có thể tạo bảng bằng cách đặt một khối ~v \times v~ toàn số ~1~ cho mỗi phần ~v~, các ô còn lại bằng ~0~. Nếu ~N \ne M~, các hàng hoặc cột dư nằm ở phía lớn hơn và có tổng ~0~. Bảng này thỏa điều kiện đồng bộ, nên bài toán đúng là tối thiểu hóa tổng bình phương.

Trong các phân tích của ~K~ thành số dương phân biệt, số phần càng nhiều thì các phần càng nhỏ. Cấu hình có nhiều phần nhất bắt đầu từ ~1,2,\ldots,p~ với ~p~ lớn nhất thỏa ~p(p+1)/2 \le K~. Sau khi cố định số phần, nếu có hai phần có thể đưa gần nhau hơn mà vẫn giữ phân biệt, chuyển ~1~ từ phần lớn sang phần nhỏ làm giảm tổng bình phương vì:

~(a+1)^2 + (b-1)^2 < a^2 + b^2~

khi ~b-a \ge 3~. Vì vậy phần dư phải được dồn vào các phần lớn nhất, mỗi phần tăng không quá ~1~, đúng như thuật toán.

Chi tiết cài đặt

• Tìm ~p~ bằng vòng lặp tăng dần vì ~N,M \le 5000~ nên ~p~ rất nhỏ.
• Tính ~1^2+2^2+\cdots+p^2~ bằng công thức ~p(p+1)(2p+1)/6~.
• Nếu ~rem~ số lớn nhất được tăng thêm ~1~, phần tăng là ~rem(2p-rem+2)~.

Độ phức tạp

Mỗi bộ test được xử lý trong ~O(\sqrt K)~ nếu tìm ~p~ bằng vòng lặp như code, với ~K=\min(N,M)~. Bộ nhớ sử dụng là ~O(1)~.