Phân tích

Một cách đơn giản để kiểm tra xem các giá trị trong một hàng hoặc một cột có phải là một hoán vị của các giá trị từ \(1\) đến \(N\) hay không là sắp xếp chúng, rồi duyệt qua chúng và kiểm tra xem danh sách đã sắp xếp có bắt đầu từ \(1\) và tăng thêm \(1\) ở mỗi vị trí hay không.

Một lựa chọn khác, không cần sắp xếp và chỉ tốn thời gian tuyến tính theo \(N\), là xét lần lượt từng giá trị và lưu mỗi giá trị vào một cấu trúc dữ liệu dựa trên bảng băm, chẳng hạn như một tập hợp. Nếu gặp một giá trị đã có trong tập hợp, hàng hoặc cột đang xét có chứa giá trị lặp lại. Vì có đúng \(N\) giá trị và đề bài đảm bảo tất cả đều là số nguyên thuộc đoạn từ \(1\) đến \(N\), nên nếu không có giá trị trùng lặp thì các giá trị đó nhất thiết tạo thành hoán vị cần tìm.

Việc tìm vết cũng rất trực tiếp: duyệt qua các hàng, lấy giá trị thứ \(i\) của hàng thứ \(i\) rồi cộng tất cả các giá trị đó lại.

Thuật toán

1. Đọc toàn bộ ma trận \(M\).
2. Khởi tạo \(k = 0\). Với mỗi chỉ số \(i\) từ \(1\) đến \(N\), cộng \(M_{i,i}\) vào \(k\).
3. Khởi tạo \(r = 0\). Với từng hàng, tạo một tập hợp rỗng và duyệt các giá trị trong hàng. Nếu một giá trị đã xuất hiện trong tập hợp thì đánh dấu hàng này có lặp; nếu không, thêm nó vào tập hợp. Tăng \(r\) đúng một lần nếu hàng đã được đánh dấu.
4. Khởi tạo \(c = 0\) và thực hiện phép kiểm tra tương tự cho từng cột. Tăng \(c\) đúng một lần đối với mỗi cột có ít nhất một giá trị lặp lại.
5. In Case #x: k r c.

Chứng minh tính đúng đắn

Với mỗi hàng, thuật toán đánh dấu hàng đó khi và chỉ khi gặp một giá trị đã nằm trong tập hợp các giá trị đứng trước nó. Điều này xảy ra khi và chỉ khi trong hàng tồn tại hai ô có cùng giá trị. Vì biến \(r\) chỉ tăng một lần cho mỗi hàng đã được đánh dấu, sau khi xét hết các hàng, \(r\) chính xác là số hàng chứa giá trị lặp lại. Lập luận hoàn toàn tương tự cho từng cột, nên \(c\) chính xác là số cột chứa giá trị lặp lại.

Ở bước tính vết, thuật toán cộng đúng các phần tử \(M_{i,i}\) với mọi \(i\) từ \(1\) đến \(N\). Theo định nghĩa của vết ma trận, tổng nhận được chính là \(k\). Do đó ba giá trị \(k\), \(r\) và \(c\) mà thuật toán in ra đều đúng.

Hơn nữa, do mỗi hàng hoặc cột có \(N\) phần tử và mọi phần tử đều thuộc tập \(\{1,2,\ldots,N\}\), nếu không có hai phần tử nào trùng nhau thì hàng hoặc cột đó chứa đủ \(N\) giá trị khác nhau trong một tập chỉ có \(N\) giá trị; vì vậy nó là một hoán vị của \(1,2,\ldots,N\). Điều này giải thích vì sao phép kiểm tra trùng lặp cũng chính là phép kiểm tra điều kiện Latin cần thiết.

Độ phức tạp

Với phương án dùng tập hợp, mỗi ô được xét một lần khi kiểm tra hàng và một lần khi kiểm tra cột. Thời gian kỳ vọng là \(O(N^2)\) và bộ nhớ phụ trợ cho tập hợp là \(O(N)\); nếu lưu toàn bộ ma trận để kiểm tra cả cột thì tổng bộ nhớ dùng để chứa dữ liệu là \(O(N^2)\).

Với phương án thay thế là sắp xếp riêng từng hàng và từng cột, thời gian là \(O(N^2 \log N)\), còn bộ nhớ phụ trợ phụ thuộc vào thuật toán sắp xếp được sử dụng.

Phân tích dựa trên lời giải chính thức của Google Code Jam.