Test Set 1

Có vài cách giải Test Set 1. Vì chỉ có \(44\) trường hợp, ta có thể tạo mọi đáp án bằng tay hoặc bằng một chương trình chạy cục bộ, rồi nộp chương trình xuất các đáp án đó. Cách khác là nhận thấy số hình vuông Latinh khi \(N\le5\) không nhiều (xem số lượng tại đây) và kiểm tra tất cả.

Để sinh mọi hình vuông Latinh, ta đệ quy điền từng ô. Tại mỗi ô, thử cả \(N\) giá trị và bảo đảm giá trị đang thử không xung đột với ô nào cùng hàng hoặc cột. Chỉ có tối đa \(161280\) hình vuông Latinh cần xét nên cách này khá nhanh.

Test Set 2

Khi \(N\) lớn hơn một chút, số hình vuông Latinh đã quá lớn để sinh hết. Chẳng hạn, với \(N=11\) có \(776966836171770144107444346734230682311065600000\) hình vuông Latinh khác nhau.

Có nhiều cách sáng tạo để giải Test Set này; diễn đàn Code Jam là nơi chia sẻ và thảo luận các lời giải. Ví dụ, ta có thể trực tiếp tạo hình vuông Latinh có vết phù hợp bằng cách biến đổi các hình vuông có cấu trúc, như hình vuông Latinh tuần hoàn. Sau đây là một ý tưởng dễ cài đặt nhưng hơi khó nghĩ ra, có dùng một thuật toán đồ thị.

Trước tiên xét các trường hợp không thể. Nếu \(K=N+1\), đường chéo duy nhất có tổng đó phải chứa đúng một số 2 và \(N-1\) số 1. Nhưng nếu \(N-1\) phần tử đường chéo là 1, vị trí duy nhất cho số 1 trong hàng còn lại cũng phải nằm trên đường chéo, nên không thể có tổng \(N+1\). Tương tự, không thể tạo tổng \(N^2-1\), vì đường chéo duy nhất có thể gồm một số \(N-1\) và \(N-1\) số \(N\).

Ta sẽ dựng được mọi trường hợp khác, ngoại trừ hai trường hợp nhỏ bổ sung nêu dưới đây. Nhận xét chính là mọi tổng khả thi đều đạt được bằng đường chéo có gần như mọi giá trị giống nhau. Cụ thể, có thể giả sử ít nhất \(N-2\) giá trị bằng nhau, tức đường chéo có dạng AAAA ... AABC với \(A,B,C\) không nhất thiết khác nhau.

Ví dụ, với \(N=10,K=20\), chọn \(A=2,B=2,C=2\); với \(N=10,K=55\), chọn \(A=6,B=4,C=3\). Như đã chỉ ra, \(A=B\) khi và chỉ khi \(A=C\). Việc chứng minh mọi \(K\) từ \(N\) đến \(N^2\) đều biểu diễn được dưới các điều kiện này được để lại như một bài tập. Cần cẩn thận khi \(N=3\): nếu \(B=C\) thì, vì lý do tương tự, \(A=B=C\); do đó \(K=5\) và \(K=7\) đều không có lời giải. Ta có thể duyệt mọi bộ ba \(A,B,C\) và kiểm tra đường chéo được chọn.

Khi đã biết đường chéo, ta điền các ô trống theo từng hàng bằng ghép cặp hai phía. Một phía có \(N\) đỉnh ứng với \(N\) ô của hàng; phía kia có \(N\) đỉnh ứng với \(N\) số. Nối ô đường chéo với số đã ấn định. Với mỗi ô khác, nối nó với một số nếu đặt số đó vào ô không phá vỡ tính chất hình vuông Latinh.

Ta có thể chọn tham lam một ghép cặp hoàn hảo bất kỳ cho từng hàng, bắt đầu bằng hai hàng có \(B\) và \(C\) trên đường chéo. Sau khi điền hai hàng này, định lý hôn nhân Hall chứng minh rằng ta không bao giờ gặp bế tắc, miễn các điều kiện về \(A,B,C\) được thỏa mãn.

Định lý Hall

Phần này chứng minh khẳng định trên và giả sử người đọc đã quen với định lý Hall. Nhắc lại: đồ thị có ghép cặp hoàn hảo khi và chỉ khi mọi tập con của một phía có tập hàng xóm lớn ít nhất bằng chính tập con đó.

Đặt hai hàng có \(B,C\) trên đường chéo làm hai hàng đầu. Giả sử chúng đã được điền; việc chứng minh luôn điền được hai hàng này dành cho người đọc. Điều quan trọng là ma trận con \(2\times2\) góc trên trái có dạng CA/AB. Giả sử đã điền \(N-k\) hàng và còn \(k\) hàng gần như trống. Ví dụ sau có \(N=8,k=3\); ? là ô đã điền nhưng giá trị không quan trọng, còn _ là ô chưa điền.

CA??????
AB??????
??A?????
???A????
????A???
_____A__
______A_
_______A

Trong \(N-1\) "đỉnh ô" không phải A, \(N-k\) đỉnh bên trái đường chéo có bậc \(k\), còn \(k-1\) đỉnh bên phải có bậc \(k-1\) vì số A cũng bị cấm. Trong \(N-1\) "đỉnh số" không phải A, ban đầu mỗi số có bậc \(N\) và ít nhất \(N-k\) cạnh đã bị loại vì số đó xuất hiện một lần trong \(N-k\) hàng trên. Vì vậy, bậc tối đa của đỉnh số là \(k\).

Ta bỏ qua đỉnh ô và đỉnh số ứng với phần tử đường chéo bắt buộc, vì chúng buộc phải ghép với nhau và việc bỏ chúng làm phép tính đơn giản hơn.

Gọi \(X\) là tập con các đỉnh ô và \(m=|X|\). Để dùng định lý Hall, cần chứng minh \(|N(X)|\ge m\), với \(N(X)\) là tập đỉnh số kề ít nhất một đỉnh trong \(X\). Có hai trường hợp.

Trường hợp 1: \(m\le k-1\). Mỗi đỉnh trong \(X\) có bậc ít nhất \(k-1\), nên ít nhất \(m(k-1)\) cạnh đi ra khỏi \(X\). Mỗi đỉnh số có bậc tối đa \(k\), nên ít nhất \(m(k-1)/k\) đỉnh số nhận các cạnh này. Do đó

Vì \(m\le k-1\) nên \(m/k<1\), suy ra \(|N(X)|>m-1\). \(|N(X)|\) là số nguyên, vì thế \(|N(X)|\ge m\).

Trường hợp 2: \(m\ge k\). Trong \(X\), nhiều nhất \(k-1\) đỉnh có bậc \(k-1\), các đỉnh còn lại có bậc \(k\). Vậy số cạnh đi ra ít nhất là

Do bậc tối đa của đỉnh số là \(k\), số đỉnh số nhận các cạnh ít nhất bằng biểu thức trên chia cho \(k\). Vì vậy

Vì \(1-1/k<1\), ta có \(|N(X)|>m-1\); tính nguyên suy ra \(|N(X)|\ge m\).

Trong mọi trường hợp, điều kiện của định lý Hall được thỏa mãn. Do đó tồn tại ghép cặp hoàn hảo và ta có thể lần lượt hoàn thiện hình vuông Latinh.

Khuyến nghị: hãy luyện tập gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

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