Định hướng

Trong bài này, trước hết ta chọn một nửa đầu vào, sau đó giám khảo chọn nửa còn lại, rồi ta phải giải một bài toán phân hoạch NP-đầy đủ trên đầu vào ấy. Vì vậy, cách ta chọn nửa đầu vào của mình phải thật có chủ đích.

Ta chỉ được cung cấp một nửa số lượng số. Do đó, trước tiên nên xem có thể chia riêng các số do giám khảo cung cấp tốt đến đâu, rồi mới dùng các số mình cung cấp để hoàn thiện hai tập.

Một chiến lược tham lam thường dùng cho các bài toán mà ta chưa biết toàn bộ đầu vào là tối ưu cục bộ. Ở đây, ta phân các số vào hai tập sao cho tổng của chúng càng gần nhau càng tốt: lần lượt xét các số nguyên đầu vào và đưa số hiện tại vào tập đang có tổng nhỏ hơn. Sau khi xử lý hết các số của giám khảo, chiến lược này bảo đảm độ chênh giữa hai tổng bị chặn bởi kích thước của một số nguyên duy nhất, tức \(10^9\), thay vì bị chặn bởi tổng của tất cả các số đã thấy, tức \(10^{11}\).

Chọn các số của ta

Các số của ta phải luôn có khả năng bù được độ chênh nói trên, nên ít nhất một số số được chọn phải đủ lớn. Hơn nữa, ta phải bù chính xác độ chênh, vì vậy cần chọn các số có độ tinh dần tăng. Điều này gợi đến hệ nhị phân. Tuy nhiên, trong biểu diễn nhị phân ta cộng một tập con các lũy thừa của \(2\), còn ở đây những số không vào tập này sẽ tự động vào tập kia; vì vậy không thể áp dụng phép viết nhị phân theo cách thông thường để biểu diễn mọi độ chênh. Dẫu vậy, các lũy thừa của \(2\) vẫn dùng được, miễn là ta không diễn giải thao tác theo cách viết nhị phân thông thường.

Sau khi phân xong đầu vào của giám khảo, ta biết độ chênh giữa hai tập không quá \(10^9\). Tiếp tục đặt lũy thừa lớn nhất của \(2\) là \(2^{29}\) vào tập đang có tổng nhỏ hơn theo cùng thuật toán tham lam; khi ấy độ chênh mới không quá \(2^{29}\). Miễn là số tiếp theo luôn ít nhất bằng một nửa số trước, ta duy trì được bất biến rằng độ chênh bị chặn bởi số vừa xử lý. Nếu xử lý các lũy thừa của \(2\) sau cùng, theo thứ tự giảm dần, thì độ chênh cuối cùng không quá \(2^0=1\). Vì đề bảo đảm tổng toàn bộ là số chẵn, độ chênh cũng phải chẵn, nên nó bằng \(0\).

Lập luận trên cho thấy mọi tập số nguyên không vượt quá \(X\), có tổng chẵn và chứa mọi lũy thừa của \(2\) không lớn hơn \(X\), đều có thể chia thành hai tập con có tổng bằng nhau; hơn nữa, có thể tìm cách chia một cách hiệu quả. Có \(30\) lũy thừa của \(2\) nằm trong đoạn từ \(1\) đến \(10^9\), nên ta có thể chọn \(70\) số còn lại trong quyền hạn của mình theo cách tùy ý, miễn vẫn thỏa tính phân biệt và giới hạn đề bài.

Lời giải này được dịch đầy đủ từ bản phân tích chính thức của Google Code Jam 2022, Vòng 1A.