Meet in the Middle

Meet in the Middle (MITM — "gặp nhau ở giữa") là kỹ thuật chia tập đối tượng thành hai nửa, liệt kê vét cạn từng nửa một cách độc lập, rồi ghép hai nửa lại để được lời giải toàn cục. Nhờ đó, một bài toán brute force $O(2^N)$ được hạ xuống $O(2^{N/2}·\log )$ — đủ để xử lý $N\le 40$ thay vì chỉ $N\le 20$ như vét cạn thông thường.

Bài toán điển hình: cho mảng $n$ số, đếm số tập con có tổng đúng bằng $K$. Vét cạn $2^{40}\approx {10}^{12}$ là quá chậm, nhưng $2^{20}\approx {10}^6$ thì chạy thoải mái. MITM khai thác chính khoảng cách đó.

Ý tưởng / Trực giác

Tại sao $2^N$ lại đắt đến vậy? Vì mỗi phần tử có 2 lựa chọn (chọn / không chọn), và ta xét mọi tổ hợp của cả $N$ phần tử cùng lúc. Số tổ hợp nhân lên theo cấp số nhân.

Mấu chốt là: một tập con bất kỳ của toàn mảng luôn tách được thành "phần nằm ở nửa trái" cộng "phần nằm ở nửa phải". Hai phần này độc lập — chọn gì ở nửa trái không ràng buộc chọn gì ở nửa phải. Do đó:

$$\text{tổng tập con}=(\text{tổng phần trái})+(\text{tổng phần phải}).$$

Thay vì sinh $2^N$ tổ hợp đầy đủ, ta:

1. Sinh mọi tổng con của nửa trái → tập $L$, kích thước $2^{N/2}$.
2. Sinh mọi tổng con của nửa phải → tập $R$, kích thước $2^{N/2}$.
3. Với mỗi tổng $\ell \in L$, ta cần phần phải có tổng đúng bằng $K-\ell$. Đếm xem trong $R$ có bao nhiêu giá trị bằng $K-\ell$.

Bước 3 nếu duyệt thô là $|L|·|R|=2^N$ — vẫn chậm! Bí quyết để "gặp nhau ở giữa" thật sự nhanh là sắp xếp $R$ (hoặc bỏ vào bảng băm). Khi đó mỗi truy vấn $K-\ell$ chỉ tốn $O(\log )$ bằng tìm kiếm nhị phân. Tổng cộng $2^{N/2}·\log (2^{N/2})=O(N·2^{N/2})$.

Tóm lại: ta đổi một bài toán "nhân" ($2^{N/2}\times 2^{N/2}$) thành "cộng rồi tra cứu" ($2^{N/2}+2^{N/2}\log$). Đó chính là cú hạ bậc thần kỳ.

Ví dụ chạy tay

Mảng $a=[3,1,4,2]$, cần đếm số tập con có tổng $K=5$. Chia $n=4$ thành nửa trái {a[0]=3, a[1]=1} và nửa phải {a[2]=4, a[3]=2}.

Bước 1 — sinh mọi tổng nửa trái (4 mặt nạ bit $00,01,10,11$):

mask  chọn       tổng
 00   {}          0
 01   {3}         3
 10   {1}         1
 11   {3,1}       4
L = [0, 3, 1, 4]

Bước 2 — sinh mọi tổng nửa phải, rồi sắp xếp:

mask  chọn       tổng
 00   {}          0
 01   {4}         4
 10   {2}         2
 11   {4,2}       6
R (đã sort) = [0, 2, 4, 6]

Bước 3 — với mỗi $\ell \in L$, đếm số phần tử trong $R$ bằng $K-\ell =5-\ell$:

 ℓ=0 → cần 5 trong R=[0,2,4,6] → có 0
 ℓ=3 → cần 2 trong R=[0,2,4,6] → có 1   (cặp: trái{3} + phải{2} = 5) ✓
                                    ^
 ℓ=1 → cần 4 trong R=[0,2,4,6] → có 1   (cặp: trái{1} + phải{4} = 5) ✓
                                       ^
 ℓ=4 → cần 1 trong R=[0,2,4,6] → có 0

Tổng số tập con có tổng $5$ là $0+1+1+0=\mathbf{2}$. Kiểm chứng tay: $\{3,2\}$ và $\{1,4\}$ — đúng 2 tập.

Cài đặt

Đếm số tập con có tổng bằng $K$ (đáp án cho bài meetmiddle):

#include <bits/stdc++.h>
using namespace std;

// Sinh mọi tổng con của a[from..to-1]
vector<long long> gen(const vector<long long>& a, int from, int to) {
    int len = to - from;
    vector<long long> sums;
    sums.reserve(1 << len);
    for (int mask = 0; mask < (1 << len); mask++) {
        long long s = 0;
        for (int i = 0; i < len; i++)
            if (mask >> i & 1) s += a[from + i];   // bit i bật => lấy phần tử
        sums.push_back(s);
    }
    return sums;
}

long long count_subsets(const vector<long long>& a, long long K) {
    int n = a.size();
    int half = n / 2;                  // chia đôi: trái [0,half), phải [half,n)

    vector<long long> L = gen(a, 0, half);
    vector<long long> R = gen(a, half, n);

    sort(R.begin(), R.end());          // sort để tra cứu O(log) bằng nhị phân

    long long cnt = 0;
    for (long long ls : L) {
        long long need = K - ls;       // phần phải phải bù đúng K - ls
        // số phần tử của R đúng bằng need = upper_bound - lower_bound
        cnt += upper_bound(R.begin(), R.end(), need)
             - lower_bound(R.begin(), R.end(), need);
    }
    return cnt;
}

int main() {
    int n; long long K;
    scanf("%d %lld", &n, &K);
    vector<long long> a(n);
    for (auto& x : a) scanf("%lld", &x);
    printf("%lld\n", count_subsets(a, K));
}

Biến thể "tổng gần $K$ nhất" — thay vì đếm bằng nhau, ta tìm tổng $\le$ hoặc $\ge$ gần nhất bằng lower_bound:

long long closest_subset_sum(const vector<long long>& a, long long K) {
    int n = a.size(), half = n / 2;
    auto L = gen(a, 0, half);
    auto R = gen(a, half, n);
    sort(R.begin(), R.end());

    long long best = LLONG_MAX;        // |tổng - K| nhỏ nhất
    for (long long ls : L) {
        long long need = K - ls;
        auto it = lower_bound(R.begin(), R.end(), need);
        if (it != R.end())                       // ứng viên >= need
            best = min(best, llabs(ls + *it - K));
        if (it != R.begin())                     // ứng viên < need (sát bên trái)
            best = min(best, llabs(ls + *prev(it) - K));
    }
    return best;
}

Độ phức tạp

• Thời gian: Sinh mỗi nửa tốn $O(\frac{N}{2}·2^{N/2})$ (mỗi trong $2^{N/2}$ mặt nạ phải cộng tới $N/2$ phần tử). Sắp xếp $R$ tốn $O(2^{N/2}\log 2^{N/2})=O(N·2^{N/2})$. Vòng ghép cũng $O(N·2^{N/2})$. Tổng cộng $O(N·2^{N/2})$. Với $N=40$ thì $2^{20}\approx {10}^6$, nhân hằng số nhỏ — chạy trong vài trăm mili-giây.
• Bộ nhớ: $O(2^{N/2})$ để lưu hai mảng tổng. Với $N=40$, mỗi mảng có $\approx {10}^6$ số long long (~8 MB) — chấp nhận được. Đây chính là cái giá phải trả: brute force tốn $O(1)$ bộ nhớ nhưng $O(2^N)$ thời gian, còn MITM "mua" tốc độ bằng bộ nhớ.

So sánh nhanh:

⚠️ Lỗi thường gặp

• Tràn số (overflow). Tổng của tới $40$ phần tử, mỗi phần tử cỡ ${10}^9$, có thể lên $4\times {10}^{10}$ — vượt int ($\approx 2.1\times {10}^9$). Phải dùng long long cho mọi biến tổng và cho $K$. Triệu chứng: đáp án đúng với test nhỏ nhưng sai/âm với test lớn.
• Đếm "bằng nhau" sai bằng lower_bound đơn lẻ. Khi đếm số phần tử bằng đúng need, phải lấy upper_bound - lower_bound. Nếu chỉ dùng binary_search (trả về true/false) sẽ bỏ sót các giá trị trùng lặp — và trong MITM, tổng trùng lặp xuất hiện rất nhiều. Test có phần tử lặp (ví dụ [1,2,3,2]) sẽ lộ lỗi này.
• Quên rằng tập con rỗng cũng được tính. Mặt nạ mask = 0 sinh ra tổng $0$ và nên nằm trong $L$, $R$. Nếu đề tính cả tập rỗng (như halfblood) mà ta khởi tạo vòng từ mask = 1, đáp án sẽ thiếu. Ngược lại nếu đề yêu cầu tập khác rỗng (như cowsubsets), nhớ trừ đi trường hợp cả hai nửa đều rỗng.
• Chia đôi lệch khi $N$ lẻ. half = n/2 làm tròn xuống; nửa phải có n - half phần tử (nhiều hơn 1 khi $N$ lẻ). Cài đặt phải dùng (1 << (n - half)) cho nửa phải, không tái dùng (1 << half). Sai chỗ này sẽ bỏ sót hoặc duyệt thừa phần tử cuối.
• Sắp xếp nhầm nửa rồi tra cứu nửa kia. Phải sort đúng mảng mà ta sẽ tìm kiếm nhị phân trên đó ($R$), không phải mảng đang duyệt ($L$). Tra lower_bound trên mảng chưa sort cho kết quả vô nghĩa mà không báo lỗi.
• Dùng vét cạn $|L|\times |R|$ ở bước ghép. Nếu quên sort + tìm kiếm và lồng hai vòng for, độ phức tạp trở lại $O(2^N)$ — đúng kết quả nhưng TLE. Triệu chứng kinh điển: "thuật toán đúng mà vẫn quá thời gian".

Biến thể / Mở rộng

• MITM hai chiều (2 ràng buộc). Khi cần khớp đồng thời hai đại lượng (ví dụ halfblood: tổng độ chua $=A$ và tổng độ đắng $=B$), không sort theo một khóa được nữa. Dùng map<pair<long long,long long>, long long> (bảng băm theo cặp $(\text{chua},\text{đắng})$) cho nửa phải, rồi với mỗi cặp ở nửa trái tra $(A-\text{chua},B-\text{đắng})$.
• Chia ba lựa chọn / $3^{N/2}$. Bài "chia tập con thành hai nhóm bằng nhau" (cowsubsets) cho mỗi phần tử 3 trạng thái (nhóm 1 / nhóm 2 / không chọn). Liệt kê nửa trái bằng $3^{N/2}$ tổ hợp, lưu hiệu (nhóm1 − nhóm2), rồi ghép sao cho hiệu hai nửa triệt tiêu.
• MITM trên đồ thị/lời giải (4-Sum, birthday attack). Bài tìm 4 phần tử tổng $=K$ trong $O(N^2\log N)$: sinh mọi tổng đôi (cỡ $N^2$), sort, rồi ghép — chính là MITM trên "nửa cặp".

Bài tập luyện

• Lệnh Robot (robotinst) — (Trung cấp) Với $N\le 40$, đếm số cách chọn $K$ lệnh để robot tới đích; chia đôi tập lệnh rồi ghép theo tọa độ $(x,y)$ — bước nhập môn MITM hai chiều.
• Đếm tập con theo tổng (meetmiddle) — (Kỳ cựu) Đúng bài toán kinh điển: đếm tập con có tổng bằng $x$ với $N\le 40$, áp dụng trực tiếp khung sinh–sort–tra cứu ở trên.
• Hoàng Tử Lai (halfblood) — (Kỳ cựu) Đếm tập con thỏa đồng thời hai ràng buộc tổng $(A,B)$ với $N\le 36$; luyện MITM hai chiều bằng bảng băm theo cặp.
• Tập hợp cân bằng (cowsubsets) — (Kỳ cựu) Đếm tập con chia được thành hai nhóm tổng bằng nhau; mỗi phần tử có 3 trạng thái nên cần MITM dạng $3^{N/2}$ ghép theo hiệu — biến thể nâng cao.