Phân tích: Mystery Square

Tổng quan

Bài toán này có vẻ có đề bài đơn giản, nhưng đừng nhầm lẫn: nó thực sự rất khó. Trừ khi bạn có một đội quân máy tính làm việc song song, không có cách nào để thử tất cả \(2^{40}\) giá trị có thể. Bạn cần một cách để giới hạn phạm vi tìm kiếm của mình.

Quan sát then chốt là phần lớn thời gian, một số chính phương được xác định duy nhất bởi cả nửa đầu của các chữ số của nó, và bởi nửa sau. Một trong hai nửa là đủ. Vì vậy, ý tưởng cấp cao là chọn nửa nào có ít dấu chấm hỏi hơn, thử tất cả các cách điền dấu chấm hỏi có thể, suy luận xem phần còn lại của số đó phải là gì, sau đó kiểm tra xem nó có khớp không. Tuy nhiên, trước khi đi sâu vào chi tiết, hãy nói về một chi tiết cài đặt khó chịu mà bạn không thể không nhận ra.

Xử lý số nguyên lớn

Nếu một số nhị phân có 120 chữ số, rõ ràng không có cách nào để khớp nó vào một số nguyên 64-bit tiêu chuẩn! Và điều đó có nghĩa là các phép toán số học có thể gây phiền toái. Dưới đây là một vài cách bạn có thể xử lý sự phức tạp này:

• Sử dụng Java và tận dụng lớp BigInteger.
• Trong g++, bạn có thể sử dụng kiểu dữ liệu ít được biết đến là __uint128_t.
• Tự viết các hàm BigInteger cho 128 bit. Trong thực tế, bạn chỉ cần Square (Bình phương) và SquareRoot (Căn bậc hai). Phép đầu tiên có thể thực hiện được bằng các công thức nhân dài ở trường tiểu học và một chút cẩn thận. Phép thứ hai có thể được thực hiện bằng tìm kiếm nhị phân.
• Sử dụng một thư viện bên ngoài như GMP.

Hy vọng bạn đã nhớ lời cảnh báo từ năm ngoái và đã chuẩn bị sẵn sàng! Mặc dù vậy, chúng tôi rất muốn để bạn chỉ làm việc trên các số nguyên 64-bit nếu có thể, nhưng hóa ra máy tính ngày nay nhanh đến mức bạn có thể chỉ cần lặp qua TẤT CẢ các số chính phương 64-bit trong vài giây. Bài toán sẽ trở nên khá nhàm chán trong trường hợp đó.

Điền số chính phương từ trên xuống (Top-down)

Được rồi, với chi tiết đó đã xong, hãy đi vào giải pháp. Nếu bạn biết nửa đầu của các chữ số trong một số chính phương, làm thế nào bạn có thể dễ dàng tìm ra phần còn lại? Ví dụ, hãy xem xét 10110????? (ở hệ nhị phân).

Lưu ý rằng căn bậc hai phải ít nhất là \(\sqrt{1011000000_2}\) và tối đa là \(\sqrt{1011011111_2}\). Thực tế, chỉ có một số nguyên nằm giữa hai giá trị này, và đó là \(11011_2\)! Vì vậy, chúng ta chỉ cần xem liệu \(11011_2^2\) có khớp với 10110????? hay không, và thế là xong. Và điều này luôn hiệu quả. Nếu một số \(X\) có \(2t\) chữ số, thì căn bậc hai \(Y\) của nó có \(t\) chữ số, và \((Y+1)^2 = Y^2 + 2Y + 1\), giá trị này đã khác với \(Y^2\) ở nhiều hơn \(t\) chữ số cuối cùng.

Tóm lại: một khi chúng ta biết nửa đầu của các chữ số trong \(N\), chúng ta chỉ cần thay các ký tự '?' bằng '1', lấy căn bậc hai rồi làm tròn xuống; đó là lựa chọn khả thi duy nhất.

Điền số chính phương từ dưới lên (Bottom-up)

Nửa còn lại của giải pháp không khó hơn nhiều về mặt khái niệm, nhưng rắc rối nằm ở chi tiết. Nếu bạn biết nửa sau của các chữ số trong một số chính phương, làm thế nào bạn có thể dễ dàng tìm ra phần còn lại? Ví dụ, hãy xem xét ????011001.

Bắt đầu thực sự khó khăn, nhưng giả sử chúng ta đã tìm ra hai chữ số nhị phân cuối cùng của căn bậc hai là 01.

• Căn bậc hai khi đó phải là \(4A + 1\) cho một số nguyên \(A\) nào đó. Bình phương của nó là \(16A^2 + 8A + 1 \equiv 8A + 1 \pmod{16}\). Tuy nhiên, chúng ta biết rằng số chính phương đó là \(9 \pmod{16}\) (từ 1001 cuối), và do đó \(A\) phải là số lẻ. Vì vậy, căn bậc hai phải kết thúc bằng 101.
• Bây giờ chúng ta biết căn bậc hai phải là \(8B + 5\) cho một số nguyên \(B\) nào đó. Bình phương của nó khi đó là \(64B^2 + 80B + 25 \equiv 16B + 25 \pmod{32}\). Tuy nhiên, chúng ta biết rằng số chính phương đó là \(25 \pmod{32}\), và do đó \(B\) phải là số chẵn. Vì vậy, căn bậc hai phải kết thúc bằng 0101.
• Tiếp tục theo cách này, chúng ta có thể sử dụng \(k+1\) chữ số cuối cùng của \(N\) để tính \(k\) chữ số cuối cùng của căn bậc hai của nó. Nếu bạn biết hơn một nửa số chữ số trong \(N\), điều này là đủ để xác định hoàn toàn căn bậc hai. Như trên, bây giờ chúng ta chỉ cần kiểm tra xem nó có hoạt động không, và thế là xong.

Kỹ thuật này luôn hoạt động, với hai điều kiện: (a) \(N\) phải là số lẻ, và (b) bạn phải biết trước hai chữ số cuối của căn bậc hai. Bạn có thể thử viết công thức trong cả hai trường hợp thất bại và xem điều gì xảy ra.

Hãy nghĩ về (b) trước. Nếu \(N\) lẻ, thì căn bậc hai cũng phải lẻ, và do đó chữ số cuối cùng phải là 1. Không có cách nào dễ dàng để xác định trước chữ số áp chót phải là gì, nhưng ai quan tâm chứ? Chỉ cần thử cả hai khả năng (01 hoặc 11) và xem cái nào hoạt động!

Tiếp theo, giả sử \(N\) chẵn. Vì nó là một số chính phương, nó thực sự phải là bội số của 4, và \(N/4\) cũng là một số chính phương. Vì vậy, chúng ta chỉ cần cắt bỏ hai chữ số cuối của \(N\), lặp lại cho đến khi \(N\) trở thành số lẻ, rồi giải như trên. Trên thực tế, mẹo này gần như là bắt buộc. Nếu \(N\) lẻ, thì \(k\) chữ số cuối là đủ để tìm \(k-1\) chữ số trong căn bậc hai. Tuy nhiên, nếu \(N\) chẵn, thì \(k\) chữ số cuối có thể chỉ đủ để tìm \(k/2\) chữ số trong căn bậc hai.

Tất nhiên, chúng ta có thể không biết trước \(N\) là chẵn hay lẻ. Nếu chữ số cuối cùng là một ký tự '?', thì chúng ta chỉ cần thử cả hai khả năng và xem điều gì xảy ra.

Nhận xét: Toàn bộ cách tiếp cận này chỉ hoạt động vì 2 là số nguyên tố. Nếu chúng ta làm việc trong hệ cơ số 10, thì một số chẵn không phải là bội số của 10 sẽ khá khó xử lý!

Tổng hợp lại

Đây là giải pháp đầy đủ:

• Giả sử rằng \(N\) là lẻ, nếu có thể.
• Nếu \(N\) có nhiều dấu chấm hỏi ở nửa dưới hơn nửa trên, thì hãy lặp qua tất cả các cách có thể để điền vào các dấu chấm hỏi ở nửa trên, suy luận ra toàn bộ số và xem nó có hoạt động không.
• Nếu \(N\) có nhiều dấu chấm hỏi ở nửa trên hơn nửa dưới, thì hãy lặp qua tất cả các cách có thể để điền vào các dấu chấm hỏi ở nửa dưới, suy luận ra toàn bộ số và xem nó có hoạt động không.
• Bây giờ giả sử rằng \(N\) là chẵn, nếu có thể. Điền hai chữ số cuối là số không, và lặp lại từ đầu (có khả năng giải theo kiểu top-down hoặc bottom-up) cho \(N/4\).

Lưu ý trong phần cuối thực sự khá quan trọng! Ví dụ, hãy xem xét đầu vào sau: 10010000010000011100000110110010001???????????????????????????????????000000000??000000000000000?0000000000000000000000??00. Hầu hết các ký tự '?' đều ở nửa đầu, vì vậy rất hấp dẫn nếu chỉ bắt đầu từ phía sau và không bao giờ đánh giá lại quyết định của bạn. Tuy nhiên, chỉ có các ký tự '0' ở phía sau, và chúng sẽ không cung cấp cho bạn nhiều thông tin. Để chạy đủ nhanh trong trường hợp này, bạn cần bắt đầu từ phía trước sau khi loại bỏ một số số 0.

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