Test Set nhỏ

Cách tự nhiên đầu tiên là dựng lại lưới bằng vét cạn: thử mọi cách gán các danh sách thành hàng và cột cho đến khi chúng khớp hoàn toàn. Nhưng ở \(N=10\), có thể có 19 danh sách cần biến thành mảng \(10\times10\). Thử cả \(20!\approx2{,}4\times10^{18}\) cách gán 19 dòng cùng một dòng trống vào 20 hàng/cột là quá lâu.

Ta có thể tận dụng tính chất đặc biệt của lưới. Với trường hợp 19 dòng, giả sử không mất tính tổng quát rằng một cột bị thiếu, nên lưới có đủ 10 hàng. Thử mọi \(\binom{19}{10}=19!/(10!9!)=92378\) cách chọn mười danh sách làm hàng. Thứ tự của chúng được xác định: các giá trị ở cột đầu phải tăng nghiêm ngặt. Nếu hai “hàng” đã chọn bắt đầu bằng cùng số, tập đó sai; nếu không, sắp hàng theo số đầu tiên sẽ cho một lưới ứng viên hoàn chỉnh. Kiểm tra mười cột xem chín cột có trùng chín danh sách chưa dùng không; nếu có, cột còn lại là đáp án.

Test Set lớn

Với tối đa 99 danh sách, cách trên không được vì \(\binom{99}{50}\) xấp xỉ \(5\times10^{28}\). Có thể viết lời giải dựng cả lưới lớn, nhưng bài chỉ hỏi hàng hoặc cột bị thiếu chứ không cần toàn bộ lưới.

Trong bộ đầy đủ các hàng và cột, mỗi ô xuất hiện đúng hai lần: một lần trong hàng và một lần trong cột chứa nó. Dù cùng một số có thể xuất hiện ở nhiều ô, tổng số lần xuất hiện của mỗi giá trị trong toàn bộ các danh sách vẫn là số chẵn.

Khi thiếu một hàng hoặc cột, các số trong danh sách bị thiếu đôi một khác nhau và mỗi số xuất hiện trong đầu vào ít hơn bộ đầy đủ đúng một lần. Vì vậy tất cả các số ấy có số lần xuất hiện lẻ. Hơn nữa, chúng chính là những số duy nhất xuất hiện lẻ lần.

Do đó không cần dựng lưới: đếm mọi số trong mọi danh sách, lấy đúng \(N\) số có tần suất lẻ, rồi sắp tăng nghiêm ngặt để thu được đáp án. Và ta không phải chống đẩy lần nào!

Nguồn

Bản dịch dựa trên phân tích chính thức Google Code Jam 2016 - Round 1A - Rank and File, kho Google Coding Competitions (Apache-2.0).