Tìm độ lớn của các phần tử

Gọi \(x\) là phần tử lớn nhất của \(S'\). Khi đó \(x\) là tổng của tất cả phần tử dương trong \(S\) và không chứa phần tử âm nào.

Gọi \(y\) là phần tử lớn thứ hai của \(S'\). Hoặc \(y\) là tổng của tất cả phần tử không âm trừ đi phần tử không âm nhỏ nhất, hoặc \(y\) là tổng của mọi phần tử không âm cộng với phần tử âm nhỏ nhất về trị tuyệt đối. Vì thế, nếu \(d=x-y\) thì trị tuyệt đối nhỏ nhất của một phần tử trong \(S\) là \(d\): hoặc \(d\in S\), hoặc \(-d\in S\).

Hai trường hợp về cơ bản giống hệt nhau. Khi xây dựng một tập con của \(S\), với mỗi phần tử ta chọn đưa nó vào hoặc không. Nếu đưa vào, tổng tăng bằng giá trị của phần tử; nếu không, tổng tăng 0. Nếu \(d\in S\), ta chọn giữa cộng 0 và cộng \(d\). Nếu \(-d\in S\), ta chọn giữa cộng \(-d\) và cộng 0. Hai tình huống tương đương, ngoại trừ mọi phần tử của \(S'\) bị lệch bởi một hằng số tùy theo \(d\) hay \(-d\) thuộc \(S\).

Do đó, có thể quét \(S'\) và ghép các phần tử thành từng cặp cách nhau \(d\), có tính đúng số lần xuất hiện, rồi chỉ giữ phần tử nhỏ hơn của mỗi cặp. Áp dụng đệ quy quy trình này cho đa tập còn lại để tìm trị tuyệt đối của tất cả các phần tử khác trong \(S\).

Xác định dấu

Sau bước trên, ta biết trị tuyệt đối của mọi phần tử trong \(S\) và cần xác định phần tử nào dương, phần tử nào âm. Trước hết coi tất cả chúng là âm; khi ấy phần tử lớn nhất trong đa tập tổng tập con là 0. Ta phải chọn một số phần tử để đổi từ âm sang dương sao cho phần tử lớn nhất của \(S'\) trở thành \(x\).

Đây là bài toán Subset Sum với tổng đích \(x\) và các phần tử là những trị tuyệt đối vừa tìm được. Có thể giải bằng quy hoạch động. Số tổng khác nhau, và do đó số trạng thái của quy hoạch động, được bảo đảm là nhỏ vì số giá trị khác nhau trong \(S'\) nhỏ. Khi có nhiều cách gán dấu, chọn cách tạo ra \(S\) sớm nhất theo định nghĩa của đề.

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