Phân tích: Fair and Square

Việc đầu tiên, như với nhiều bài khác, là đọc đề thật kỹ. Nhiều thí sinh tưởng 676 là số fair and square vì nó vừa là số chính phương vừa là palindrome. Nhưng nó không phải bình phương của một palindrome; ví dụ này còn được nêu rõ trong đề.

Dữ liệu nhỏ

Duyệt mọi số Little John xét và kiểm tra từng số \(X\): \(X\) có phải palindrome và có phải bình phương của một palindrome không.

Để kiểm tra palindrome, đổi \(X\) thành xâu rồi so sánh ký tự đầu với cuối, thứ hai với áp cuối, v.v.

Để kiểm tra \(X\) có phải bình phương của palindrome, có nhiều cách. Có thể tính căn bậc hai, kiểm tra căn là số nguyên rồi kiểm tra nó là palindrome. Hoặc duyệt mọi số đến \(X\), bình phương từng số palindrome và so với \(X\). Cách sau hoàn toàn đủ cho dữ liệu nhỏ nhưng quá chậm cho dữ liệu lớn.

Dữ liệu lớn thứ nhất

Ta phải xử lý số đến \(10^{14}\) và 10.000 test. Không thể tìm tuyến tính đến \(10^{14}\). Tuy nhiên chỉ cần xét các căn có bình phương nằm trong \([A,B]\), nên trong trường hợp xấu nhất chỉ duyệt đến \(\sqrt B=10^7\).

\(10^7\) số có thể xử lý trong giới hạn thời gian, nhưng lặp lại cho 10.000 test vẫn rủi ro. Có hai mẹo tăng tốc.

Thứ nhất, ta chỉ quan tâm palindrome, không phải mọi số đến \(10^7\). Lấy mọi số đến \(10^4\) rồi nối với ảnh gương của nó, có hoặc không lặp chữ số cuối, để sinh mọi palindrome dài tối đa 8; bình phương từng số và kiểm tra kết quả có fair and square và thuộc đoạn cần xét không. Mỗi test chỉ xét khoảng 10.000 số, đủ nhanh trong bốn phút ngay cả trên máy chậm, miễn là dùng ngôn ngữ tương đối hiệu quả.

Phương án khác là sinh trước mọi số fair and square đến \(10^{14}\) rồi mới xử lý test. Chỉ có 39 số như vậy. Nếu tìm chúng bằng bất kỳ cách nào trước khi tải input, ta có thể trả lời mọi test rất dễ dàng. Tuy nhiên phải nộp cả mã dùng để sinh danh sách, không chỉ mã chứa danh sách đã tính sẵn.

Dữ liệu lớn thứ hai

Ngay cả kết hợp hai mẹo trên cũng chưa đủ: phải duyệt hơn \(10^{25}\) palindrome để tiền xử lý. Hãy sinh vài số fair and square đầu tiên cùng căn của chúng để quan sát:

• Mọi số fair and square đều có số chữ số lẻ.
• Các chữ số đều khá nhỏ. Ngoại trừ một trường hợp, căn bậc hai của mọi số fair and square chỉ gồm 0, 1 và 2.

Ta sẽ giải thích hai hiện tượng này.

Vì sao số chữ số là lẻ

Bình phương một số \(N\) chữ số có \(2N-1\) hoặc \(2N\) chữ số, tùy có phát sinh nhớ ở vị trí đầu hay không. Ta chứng minh phép nhớ ấy không xảy ra. Gọi \(X\) là số fair and square, \(Y=\sqrt X\), và chữ số đầu của \(Y\) là \(c\). Hai chữ số đầu của \(X\) nằm giữa \(c^2\) và \((c+1)^2\):

• Nếu chữ số đầu của \(Y\) là 1, chữ số đầu của \(X\) nằm giữa 1 và 4, nên không có nhớ.
• Nếu là 2, chữ số đầu của \(X\) nằm giữa 4 và 9, nên không có nhớ.
• Nếu là 3, phần đầu của \(X\) nằm giữa 9 và 16, nên chữ số đầu là 9 hoặc 1. Vì \(Y\) là palindrome, chữ số cuối cũng là 3, nên chữ số cuối của \(X\) là 9. \(X\) là palindrome nên chữ số đầu cũng phải là 9; không có nhớ.
• Nếu chữ số đầu và cuối của \(Y\) là 4, chữ số cuối \(X\) là 6 trong khi chữ số đầu là 1 hoặc 2, nên \(X\) không thể fair and square.
• Tương tự với 5 (chữ số cuối \(X\) là 5, đầu là 2 hoặc 3), 6 (cuối 6, đầu 3 hoặc 4), 7 (cuối 9, đầu 4, 5 hoặc 6), 8 (cuối 4, đầu 6, 7 hoặc 8), và 9 (cuối 1, đầu 8 hoặc 9), \(X\) cũng không thể fair and square.

Vậy không có phép nhớ ở chữ số đầu, nên bình phương có \(2N-1\) chữ số, một số lẻ.

Vì sao không có phép nhớ nào

Nếu bình phương một palindrome mà không có nhớ, kết quả cũng là palindrome; điều này sẽ cho một đặc trưng đẹp. Thật vậy, mọi số fair and square đều không có phép nhớ trong phép nhân dài.

Viết các chữ số của \(Y\) là \((a_d)(a_{d-1})\ldots(a_0)\) và đặt

\(b_i\) chính là giá trị ở vị trí thứ \(i\) của \(X=Y^2\) trong phép nhân dài trước khi truyền nhớ. Do \(a_j=a_{d-j}\), ta có \(b_i=b_{2d-i}\).

Giả sử phép nhân có nhớ, tức một \(b_j>9\), và xét vị trí \(i\) nhận một số nhớ nhưng không có vị trí lớn hơn nào nhận nhớ. Hai chữ số ở vị trí \(i\) và \(2d-i\) của palindrome \(X\) bằng nhau. Chữ số tại \(i\) là \(b_i\) cộng phần nhớ đi vào. Vì không truyền nhớ sang \(i+1\), \(b_i\le9\).

Chữ số tại \(2d-i\) phải bằng \(b_{2d-i}=b_i\). Muốn khác đi thì phải có nhớ truyền vào \(2d-i\), nghĩa là tồn tại \(j<2d-i\) với \(b_j>9\). Nhưng khi đó \(b_{2d-j}>9\), gây một phép nhớ sau vị trí \(i\), trái với cách chọn \(i\). Vì \(X\) đối xứng, chữ số tại \(i\) phải bằng \(b_i\), tức không có nhớ truyền vào \(i\)—mâu thuẫn. Vậy toàn bộ phép nhân dài không có phép nhớ.

Do đó, các số fair and square chính xác là các bình phương palindrome không phát sinh nhớ. Đặc biệt, chữ số giữa của \(X\) là tổng bình phương mọi chữ số của \(Y\), nên tổng ấy không vượt quá 9. Suy ra trong \(Y\) chỉ có thể xuất hiện 0, 1, 2, 3.

Vì vậy chỉ cần xét các palindrome tạo bởi bốn chữ số này và có tổng bình phương chữ số không quá 9. Tập đó đủ nhỏ để duyệt trực tiếp, sinh toàn bộ số fair and square đến \(10^{100}\) trong vài giây và giải được dữ liệu lớn nhất.

Những bài học rút ra

• Đọc đề cẩn thận là cực kỳ quan trọng.
• Đôi khi bài không có cấu trúc quen thuộc gồm đúng một Small và một Large. Quy tắc xử lý các bộ dữ liệu vẫn giữ nguyên, trừ khi đề nói rõ khác đi.
• Đôi khi bài yêu cầu số nguyên rất lớn. Code Jam từng cảnh báo điều này qua bài Fair Warning, nhưng vẫn đáng nhắc lại.
• Nếu dùng tiền xử lý, phải nộp không chỉ mã giải bài chứa các giá trị tiền xử lý mà cả mã đã dùng để tạo chúng.

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