Phân tích: Squary

Khai triển đa thức của lũy thừa bậc hai là chìa khóa của bài toán. Với danh sách \(X\) gồm các phần tử \(X_1,X_2,\ldots,X_N\), bình phương của tổng được khai triển như sau:

Gọi \(S(X)\) là tổng các phần tử, \(SQ(X)\) là tổng bình phương các phần tử, và \(SP(X)\) là tổng tích của mọi cặp phần tử trong danh sách \(X\). Đẳng thức trên có thể viết lại thành

Ta cũng có thể quan sát sự thay đổi của ba đại lượng này khi thêm một phần tử \(n\) vào \(X\):

Mục tiêu là đạt \(S(E')^2=SQ(E')\), trong đó \(E'\) là danh sách mở rộng thu được bằng cách thêm các phần tử vào \(E\). Nói cách khác, ta cần làm cho \(SP(E')=0\).

Test Set 1: \(K=1\)

Khi chỉ được phép thêm một phần tử, ta phải chọn \(n\) sao cho \(SP(E+[n])=0\):

Nếu \(S(E)\ne0\), ta có thể tạo một danh sách squary khi và chỉ khi \(-SP(E)/S(E)\) là số nguyên, tức là khi và chỉ khi \(S(E)\) chia hết \(SP(E)\). Khi đó, đáp án là \(-SP(E)/S(E)\).

Nếu \(S(E)=0\) thì \(S(E+[n])=n\). Vì cần \(S(E+[n])^2=SQ(E+[n])\), ta phải có \(SQ(E+[n])=n^2\). Điều này chỉ có thể xảy ra nếu \(SQ(E)=0\), tức là mọi phần tử của \(E\) đều bằng \(0\). Trong trường hợp ấy, ta có thể chọn bất kỳ giá trị hợp lệ nào làm đáp án. Nếu \(E\) có ít nhất một phần tử khác \(0\), không thể tạo danh sách squary chỉ bằng một lần thêm.

Test Set 2: \(K>1\)

Ban đầu, không gian tìm kiếm có vẻ rộng đến mức vô vọng. Tuy nhiên, ta có thể nhận ra — hoặc phỏng đoán rồi kiểm chứng — rằng luôn có thể tạo một danh sách squary chỉ bằng cách thêm hai phần tử:

Sau khi thêm \(n_1\), ta có

Sau khi thêm tiếp \(n_2\), ta có

Vì thế, hai số trên thỏa điều kiện \(SP(E')=0\). Hơn nữa, do độ lớn mỗi số trong danh sách ban đầu không vượt quá \(10^3\), ta có \(|n_1|\le10^6+1\) và \(|n_2|\le2\cdot10^{12}\); cả hai đều nằm thoải mái trong giới hạn cho phép.

Dữ liệu kiểm thử

Google khuyến nghị bạn luyện gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Phân tích chính thức của Google Code Jam 2022, Vòng 1C, bài Squary.