Lời giải

Ký hiệu

Gọi ~sum~ là tổng số kẹo của cả ~n~ hộp. Một cách chia là một cặp không thứ tự ~\{A, B\}~ với ~A \cup B~ là toàn bộ các hộp và ~A \cap B = \varnothing~. Đặt ~T = \mathrm{sum}A~, khi đó ~\mathrm{sum}B = sum - T~ và

~\mathrm{diff} = |\mathrm{sum}A - \mathrm{sum}B| = |sum - 2T|~

Tổng số kẹo lên tới ~4 \cdot 10^{10}~ nên không thể quy hoạch động theo tổng, và ~n \le 40~ khiến việc duyệt ~2^n~ tập con là không khả thi. Đây là bài toán mẫu của kỹ thuật chia đôi (meet in the middle).

Bước 1: quy về một phía duy nhất

Trong hai phía của cùng một cách chia, phía có tổng nhỏ hơn luôn thoả ~T \le \lfloor sum/2 \rfloor~. Đặt

~target = \lfloor sum/2 \rfloor~

thì ta chỉ cần liệt kê các tập ~A~ có ~T \le target~ — mọi cách chia đều được đại diện bởi phía nhỏ của nó. Nhờ vậy dấu giá trị tuyệt đối biến mất:

~\mathrm{diff} = sum - 2T~, giảm dần khi ~T~ tăng.

Bước 2: chia đôi mảng

Chia ~n~ hộp thành nửa trái ~a_1 \ldots a_{\lfloor n/2 \rfloor}~ và nửa phải ~a_{\lfloor n/2 \rfloor + 1} \ldots a_n~. Liệt kê:

• ~sumX~ = tập tổng của mọi tập con nửa trái (~2^{\lfloor n/2 \rfloor}~ giá trị);
• ~sumY~ = tập tổng của mọi tập con nửa phải (~2^{\lceil n/2 \rceil} \le 2^{20}~ giá trị).

Rồi sắp xếp tăng dần cả hai. Mỗi tập ~A~ tương ứng đúng một cặp (tập con nửa trái, tập con nửa phải); gọi ~X~, ~Y~ là tổng hai phần đó thì ~T = X + Y~.

Lưu ý khi ~n~ lẻ: nửa phải có ~\lceil n/2 \rceil~ phần tử, đừng liệt kê cả hai nửa với cùng số phần tử — đó là lỗi phổ biến nhất ở bài này.

Bước 3: với mỗi ~X~, chỉ cần đúng một ~Y~

Vì ~\mathrm{diff} = sum - 2T~ giảm theo ~T~, giá trị tốt nhất ứng với ~X~ là ~Y~ lớn nhất thoả ~X + Y \le target~ — tìm bằng một phép chặt nhị phân (upper_bound rồi lùi một bước).

Không cần xét các ~Y~ nhỏ hơn: chúng cho ~T~ nhỏ hơn, tức ~\mathrm{diff}~ lớn hơn hẳn.

Bước 4: đếm số cách

Với ~X~ cố định và ~Y~ tối ưu đã xác định, mọi tập con nửa phải có tổng đúng bằng ~Y~ đều cho cùng ~T~ nên cùng ~\mathrm{diff}~. Số lượng đó chính là bội của giá trị ~Y~ trong ~sumY~ — lấy bằng lower_bound để tìm vị trí đầu tiên của giá trị ~Y~, rồi trừ chỉ số.

Bội của ~X~ không cần xử lý riêng: vòng lặp đi qua từng phần tử của ~sumX~, nên các tập con nửa trái trùng tổng đã được tính đủ số lần.

Kết thúc vòng lặp, ta có số tập ~A~ có tổng đúng bằng ~T_{\min} = (sum - \mathrm{diff}_{\min}) / 2~.

Bước 5: trừ trùng

Chuyển từ "số tập ~A~" sang "số cách chia" — đây là chỗ tinh tế nhất của bài:

• ~\mathrm{diff}_{\min} > 0~: hai phía có tổng khác nhau, chỉ phía nhỏ hơn thoả ~T \le target~, nên mỗi cách chia được đếm đúng một lần — giữ nguyên.
• ~\mathrm{diff}_{\min} = 0~: cả tập ~A~ và phần bù của nó đều có tổng ~= target~, đều thoả ~T \le target~, nên mỗi cách chia được đếm hai lần — phải chia đôi kết quả.

Trường hợp ~A = \varnothing~ (dồn hết kẹo cho một bạn) cũng nằm trong phép liệt kê và cho ~\mathrm{diff} = sum~, nhưng nó không bao giờ tối ưu: với ~n \ge 2~ và ~a_i \ge 1~ thì hộp lớn nhất có ~\max < sum~, nên riêng cách chia ~A = \{\max\}~ đã cho ~\mathrm{diff} = |sum - 2\max| < sum~. Không cần loại bằng tay.

Chương trình

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAX 41

int A[MAX], nArr;
vector<int> sumX, sumY;          // tong moi tap con cua nua trai / nua phai

// liet ke tong moi tap con cua doan [i, s)
void Try(int i, int s, int sum){
    if(i == s){
        (s == (nArr >> 1) ? sumX : sumY).emplace_back(sum);
        return;
    }
    Try(i + 1, s, sum + A[i]);   // lay hop i
    Try(i + 1, s, sum);          // khong lay hop i
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> nArr;
    for (int i = 0; i < nArr; ++i) cin >> A[i];

    Try(0, nArr >> 1, 0);        // nua trai -> sumX
    Try(nArr >> 1, nArr, 0);     // nua phai -> sumY (n le: nhieu hon 1 phan tu)
    sort(sumX.begin(), sumX.end());
    sort(sumY.begin(), sumY.end());

    int sum = accumulate(A, A + nArr, 0LL);
    int target = sum / 2;        // chi xet cac tap A co tong T <= target

    int ansDiff = LLONG_MAX, ansWays = 0;
    for (int X : sumX){
        // Y lon nhat thoa X + Y <= target: diff = sum - 2T giam theo T
        auto it = upper_bound(sumY.begin(), sumY.end(), target - X);
        if (it == sumY.begin()) break;      // target - X < sumY[0] = 0, moi X sau cung vay
        int r = prev(it) - sumY.begin();
        int Y = sumY[r];

        // moi tap con nua phai co dung tong Y deu cho cung T, cung diff
        int l = lower_bound(sumY.begin(), sumY.end(), Y) - sumY.begin();
        int curWays = r - l + 1;

        int T = X + Y;
        int curDiff = sum - 2 * T;
        if (curDiff < ansDiff) { ansDiff = curDiff; ansWays = curWays; }
        else if (curDiff == ansDiff) ansWays += curWays;
    }

    // diff > 0: moi cach chia chi co phia nho hon thoa T <= target -> dem 1 lan
    // diff = 0: ca tap A va phan bu deu co tong = target -> dem 2 lan
    if (ansDiff == 0) ansWays >>= 1;

    cout << ansDiff << ' ' << ansWays << '\n';
    return 0;
}

Độ phức tạp ~O\big(2^{\lceil n/2 \rceil} \log 2^{\lceil n/2 \rceil}\big)~ cho phần sắp xếp và hai phép chặt nhị phân ứng với mỗi ~X~; bộ nhớ ~O(2^{\lceil n/2 \rceil})~. Đo thực tế với ~n = 40~: 0,14 – 0,24 s và 25 MB, so với giới hạn ~1~ s và ~256~ MB.

Bẫy cần tránh

• Kiểm tra it == sumY.begin() là điều kiện an toàn, không phải tối ưu. Nếu ~target - X < 0~ thì upper_bound trả về sumY.begin(), và prev(begin()) là undefined behavior → truy cập ~sumY[-1]~. Bỏ dòng kiểm tra rồi chạy n = 2, a = [10, 1]: chương trình dừng đột ngột (abort). Dùng break được vì ~sumX~ đã sắp tăng, nên một khi ~target - X < 0~ thì mọi ~X~ sau đó cũng vậy.
• ~sumY~ luôn chứa giá trị ~0~ (tập con rỗng). Đây là tiền đề ngầm cho bước 3: khi ~target - X \ge 0~ thì chắc chắn tồn tại ~Y~ dùng được.
• Tràn số: ~sum~ tới ~4 \cdot 10^{10}~ nên accumulate phải khởi tạo bằng 0LL; số cách chia cũng tới cỡ ~2^{39}~ (test lớn nhất của bài cho ~68\,923\,264\,410~), bắt buộc 64 bit.
• ~n~ lẻ: nửa phải nhiều hơn một phần tử, và cách viết Try(i, s, sum) theo nửa khoảng ~[i, s)~ xử lý việc này tự nhiên.
• Đừng chia đôi kết quả trong mọi trường hợp — chỉ chia khi ~\mathrm{diff}_{\min} = 0~ (xem bước 5).
• Nếu code có sẵn khối freopen("*.inp") để chấm offline, hãy bỏ khi nộp online: nó không cần thiết và làm chương trình mở file ngoài ý muốn.