Chia đôi tập (Meet-in-the-middle)

Đỗ Thị Hồng Ngát 23/09/2023
Chia đôi tập
23
Th9

Ta xem xét bài toán sau.

Đề bài

Cho một dãy số gồm (n) phần tử (a_1, a_2, …, a_n) nguyên dương và một số (X) . Hãy tìm số dãy (i_1, i_2, … i_k) thỏa mãn (a_{i_1} + a_{i_2} + … + a_{i_k} = X) ((1 le i_1 < i_2 < … < i_k le n)). Nói cách khác, hãy tìm số tập con của dãy (a) thỏa mãn tổng các phần tử của tập con đó có tổng bằng (X).

Giới hạn

  • Với mọi test, (-10^9 le a_i, X le 10^9).
  • Subtask (1): (n le 20).
  • Subtask (2): (n le 36).

Nhận xét và lời giải

Với Subtask (1), ta có thể dễ dàng tìm tất cả các tập con của dãy (a) bằng thuật toán quay lui với độ phức tạp (2^n) và kiểm tra xem tổng mỗi tập con có bằng (X) không

long long ans = 0;
int n, a[n + 1], X;
void backtrack(int i, long long sum){
    if (i == n + 1){
        if (sum == X) ans++;
        return;
    }
    backtrack(i + 1, sum + a[i]);
    backtrack(i + 1, sum);
}

Tuy nhiên đối với Subtask (2), việc quay lui với độ phức tạp (2^n) sẽ chạy quá lâu so với thời gian cho phép ((2^{36} approx 7e10)). Đây chính là lúc meet-in-the-middle xuất hiện.

Meet-in-the-middle cũng là một thuật toán để duyệt với những bộ input có (n) nhỏ, tuy nhiên không đủ nhỏ để duyệt toàn bộ các trường hợp bài toán (quay lui). Cũng tương tự với chia để trị, ta sẽ chia đôi bài toán và giải chúng độc lập, sau đó sẽ kết hợp cả hai để giải bài toán tổng quát (tuy nhiên chỉ chia đôi bài toán một lần)

Quay lại bài toán trên, ta sẽ chia dãy (a) thành hai tập nhỏ, tập (A) gồm (n/2) phần tử và tập (B) gồm các phần tử còn lại.

Ta sẽ quay lui để tìm tất cả các tổng có thể của mỗi tập con của (A) và (B), mỗi tập có tối đa (2^{n/2}) tập con. Gọi (cntA[x]) là số tập con của tập (A) có tổng là (x), (cntB[x]) là số tập con của (B) có tổng là (x). Việc bây giờ sẽ là tìm cách kết hợp các tổng của hai tập con (A) và (B).

Ta sẽ duyệt tất cả tổng của các tập con của tập (A). Giả sử tổng hiện tại đang xét là (x), để đạt được tổng (X), ta sẽ phải kết hợp với một tập con của tập (B) có tổng là (X – x). Ta sẽ cộng vào kết quả một lượng (cntA[x] * cntB[X – x]).

Độ phức tạp: (O(2^{n/2} times log(2^{n/2}))). (Mất thêm (log) vì ta sẽ phải sử dụng (map) để lưu (cntA) và (cntB)).

#include <bits/stdc++.h>
#define ll long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())

using namespace std;

int n, a[45], m, b[45], X;
ll res = 0;
map<ll, int> cntA, cntB;


void backtrackA(int i, ll sum){
    if (i == n + 1){
        cntA[sum]++;
        return;
    }
    backtrackA(i + 1, sum + a[i]);
    backtrackA(i + 1, sum);
}
void backtrackB(int i, ll sum){
    if (i == m + 1){
        cntB[sum]++;
        return;
    }
    backtrackB(i + 1, sum + b[i]);
    backtrackB(i + 1, sum);
}

void PROGRAM(int _){
    cin >> n >> X;
    m = n - n / 2;
    n /= 2;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];

    backtrackA(1, 0);
    backtrackB(1, 0);

    for (auto [x, cnt] : cntA){
        res += cnt * cntB[X - x];
    }

    cout << res << endl;

}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int test = 1;
    for (int _ = 1; _ <= test; _++){
        PROGRAM(_);
    }

    return 0;
}

Ta sẽ cùng tìm hiểu một vài ví dụ tiếp theo

Ví dụ 1. VNOJ – Phân tập

Tóm tắt đề bài

Cho (N) người, mỗi người có sức mạnh là (a_i), cần chia (N) người vào hai nhóm sao cho chênh lệch tổng sức mạnh của hai nhóm là nhỏ nhất. Hãy tìm chênh lệch nhỏ nhất và số cách để có được chênh lệch nhỏ nhất. ((N le 32))

Nhận xét và lời giải

Với (N le 20), ta vẫn sẽ có lời giải tương đối dễ dàng

long long res = 1e18, cnt = 0;
void backtrack(int i, long long diff){
    if (i == n + 1){
        if (abs(diff) < res){
            res = abs(diff);
            cnt = 1;
        }
        
        else if (abs(diff) == res){
            cnt++;
        }
        // lưu ý với mỗi cách chia sẽ bị 
        // tính làm 2 lần, nên đáp án cuối cùng sẽ là cnt / 2
        return;
    }
    backtrack(i + 1, diff - a[i]);
    backtrack(i + 1, diff + a[i]);
}

Ta sẽ thử giải bài toán bằng meet-in-the-middle. Chia tập (a) thành hai dãy (A) và (B), tương tư như trên, ta quay lui mỗi tập (A) và (B) để tìm các chênh lệch có thể. Việc của ta là sẽ tìm cách để gộp hai tập.

Với mỗi chênh lệch của tập (A), tạm gọi là (x), ta sẽ tìm chênh lệch của (B) là (y) sao cho (|x – y| ; min), hay (x – y ; min) với (x geq y), (y – x ; min) với (y > x). Tương đương với việc tìm (y ; max) với (x geq y), (y ; min) với (y > x). Sắp xếp dãy chênh lệch của (B) tăng dần rồi sử dụng hàm (upper_bound) để tìm (y).

#include <bits/stdc++.h>
#define ll long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())

using namespace std;

int n, a[45], b[45], m;
map<ll, ll> A, B;

void backtrackA(int i, ll diff){
    if (i == n + 1){
        A[diff]++;
        return;
    }

    backtrackA(i + 1, diff + a[i]);
    backtrackA(i + 1, diff - a[i]);
}

void backtrackB(int i, ll diff){
    if (i == m + 1){
        B[diff]++;
        return;
    }

    backtrackB(i + 1, diff + b[i]);
    backtrackB(i + 1, diff - b[i]);
}

void PROGRAM(int _){
    cin >> n;
    m = n - n / 2;
    n /= 2;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];

    backtrackA(1, 0);
    backtrackB(1, 0);

    ll res = 1e18, sl = 0;

    for (auto [val, cnt] : A){
        auto k = B.upper_bound(val);
        if (k != B.end()){
            if (abs(k->st - val) < res){
                res = abs(k->st - val);
                sl = cnt * k->nd;
            }
            else if (abs(k->st - val) == res) sl += cnt * k->nd;
        }

        if (k == B.begin()) continue;
        k--;
        if (abs(k->st - val) < res){
                res = abs(k->st - val);
                sl = cnt * k->nd;
        }
        else if (abs(k->st - val) == res) sl += cnt * k->nd;
        
    }
    cout << res << " " << sl / 2 << endl;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int test = 1;

    for (int _ = 1; _ <= test; _++){
        PROGRAM(_);
    }

    return 0;
}

Ví dụ 2. Bedao Mini Contest 07 – Market

Tóm tắt đề bài

Cho một dãy số gồm (n) phần tử (a_1, a_2, …, an) và số (x), đếm số dãy con của (a) thỏa mãn (frac{a{i1} + a{i2} +. .. + a{i_k}}{k} = x). ((n le 36))

Nhận xét và lời giải

Ta có nhận xét sau:
()frac{a_{i1} + a{i2} +. .. + a{i_k}}{k} = x()

() leftrightarrow a_{i1} + a{i2} +. .. + a{i_k} = x times k()

() leftrightarrow (a_{i1} – x) + (a{i2} – x) +. .. + (a{i_k} – x) =0()

Đặt (b_i = ai – x), bài toán trở thành tìm số dãy của của (b) sao cho (b{i1} + b{i2} + … + b{i_k} = 0). Đây chính là bài toán đã được giải ở bài tập giới thiệu.

#include <bits/stdc++.h>
#define int long long
#define endl "n"
#define ii pair<int,int>
#define st first
#define nd second
#define fastIO ios_base::sync_with_stdio(false);cin.tie(nullptr);
using namespace std;
const int MAXN = 1e5 + 5;
int n, m, x, a[MAXN], b[MAXN], l[MAXN], r[MAXN], ans = 0;
unordered_map<int, int> le,ri;
void leftSolve(){
    int sum = 0;
    for (int i = 1; i <= m; i++){
        if (l[i]) sum += a[i];
    }
    le[sum]++;
}
void rightSolve(){
    int sum = 0;
    for (int i = 1; i <= n; i++){
        if (r[i]) sum += b[i];
    }
    ri[sum]++;
}
void backtrackL(int j){
    for (int i = 0; i <= 1; i++){
        l[j] = i;
        if (j == m) leftSolve();
        else backtrackL(j + 1);
    }
}
void backtrackR(int j){
    for (int i = 0; i <= 1; i++){
        r[j] = i;
        if (j == n) rightSolve();
        else backtrackR(j + 1);
    }
}
signed main(){
    cin >> n >> x;
    if (n == 1){
        int inp;
        cin >> inp;
        if (inp == x) cout << 1;
        else cout << 0;
        return 0;
    }
    m = n - n / 2;
    n /= 2;

    for (int i = 1; i <= m; i++) cin >> a[i], a[i] -= x;
    for (int i = 1; i <= n; i++) cin >> b[i], b[i] -= x;
    backtrackL(1);
    backtrackR(1);

    for (auto i : le){
        ans += i.nd * ri[-i.st];
    }
    cout << ans - 1 << endl;

}

Ví dụ 3. Bedao Mini Contest 19 – Military

Tóm tắt đề bài

Cho đồ thị gồm (n) đỉnh và (m) cạnh, mỗi cạnh có trọng số là (c_i), hãy tìm một tập các đỉnh sao cho có tổng trọng số lớn nhất và giữa hai đỉnh bất kì của tập đỉnh đó không có cạnh nối.((n le 40))

Nhận xét và lời giải

Chia tập đỉnh thành hai phần gồm tập (A) và tập (B). Với tập (A), ta lưu (sumA[maskA]) là tổng sức mạnh nếu chọn các đỉnh có bit được bật trong (maskA), (sumA[maskA] = -inf) nếu trong các đỉnh được chọn có ít nhẩt một cặp đỉnh có cạnh nối.
Với tập (B), ta sẽ tương tự có mảng (sumB[maskB]) và (ban[maskB]) lưu những đỉnh thuộc tập (A) mà có cạnh nối đến ít nhất một đỉnh thuộc tập (B) đã chọn ở (maskB). Từ đó, với mỗi (maskB), ta cần ghép với (maskA) có (sumA[maskA] ; max) thỏa mãn (maskA) là tập con của (rev(ban[maskB])) với (rev(mask)) là dãy bit bị đảo ngược lại từ (mask) ((1)).

Xây dựng mảng (sumA, sumB, ban) trong độ phức tạp (O(2^{n/2})). Để tìm ((1)), ta sẽ duyệt qua các tập con của (rev(ban[maskB])) trong độ phức tạp (O(3^{n/2})).

Dễ dàng nhận thấy việc duyệt qua các tập con sẽ không đủ thời gian, ở đây ta có thể cải tiến bằng DP SOS, nếu chưa biết về DP SOS bạn có thể đọc ở đây.

#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())

using namespace std;

const int MAXN = 45;
const int oo = 1e18;

int n, m;
int c1[MAXN], c2[MAXN];

int g1[MAXN], g2[MAXN], ng1[MAXN], ng2[MAXN];

int res[(1 << 20) + 10][2];
int banned[(1 << 20) + 10];

int f[(1 << 20) + 10];
int f_half, s_half;

void ql2(int i, int sum, int used, int ban, int ban1){
    if (i == s_half  + 1){
        res[used][1] = sum;
        banned[used] = ban1;
        return;
    }

    ql2(i + 1, sum, used, ban, ban1);

    if (ban >> i & 1) return;

    ql2(i + 1, sum + c2[i], used | (1 << i), ban | g2[i], ban1 | ng2[i]);
}

void ql1(int i, int sum, int used, int ban){
    if (i == f_half + 1){
        res[used][0] = sum;
        return;
    }
    ql1(i + 1, sum, used, ban);

    if (ban >> i & 1) return;

    ql1(i + 1, sum + c1[i], used | (1 << i), ban | g1[i]);
}



void PROGRAM(int _){
    // freopen("gen.inp", "r", stdin);
    cin >> n >> m;

    f_half = (n - 1) / 2, s_half = (n - 1) - (f_half + 1);
    for (int i = 0; i < n; i++){
        if (i <= f_half) cin >> c1[i];
        else cin >> c2[i - f_half - 1];
    }

    for (int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        u--, v--;
        if (u > v) swap(u, v);
        bool tu = u <= f_half, tv = v <= f_half;
        if (tu == tv && tu == 1){
            g1[u] |= (1 << v);
            g1[v] |= (1 << u);
        }
        else if (tu == tv && tu == 0){
            u -= (f_half + 1);
            v -= (f_half + 1);
            g2[u] |= (1 << v);
            g2[v] |= (1 << u);
        }
        else{
            v -= (f_half + 1);
            ng1[u] |= (1 << v);
            ng2[v] |= (1 << u);
        }
    }

    for (int i = 0; i < (1 << (f_half + 1)); i++){
        res[i][0] = res[i][1] = -oo;
    }

    ql1(0, 0, 0, 0);
    ql2(0, 0, 0, 0, 0);

    f_half++, s_half++;

    for (int i = 0; i < (1 << f_half); i++){
        f[i] = res[i][0];
    }

    for (int i = 0; i < f_half; i++){
        for (int mask = 0; mask < (1 << f_half); mask++){
            if (mask >> i & 1) f[mask] = max(f[mask], f[mask ^ (1 << i)]);
        }
    }
    int ans = 0;

    for (int mask = 0; mask < (1 << s_half); mask++){
        int ban = banned[mask];
        int nmask = ((1 << f_half) - 1) ^ ban;
        ans = max(ans, f[nmask] + res[mask][1]);
    }
    cout << ans << endl;

    

}


signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int test = 1;

    for (int _ = 1; _ <= test; _++){
        PROGRAM(_);
    }

    return 0;
}

Ví dụ 4. Codeforces – Prime Gift

Tóm tẳt đề bài

Cho tập (n) số nguyên tố (p_1, p_2, …, p_n) ((p_i le 100)). Hãy tìm số nhỏ thứ (k) thỏa mãn tất cả các ước nguyên tố của số đó thuộc tập số nguyên tố trên. Dữ liệu đảm bảo đáp án nhỏ hơn (10^{18}). ((n le 16))

Nhận xét và lời giải

Ta thử sinh ra hết các số có dạng (X = p_1^{q_1}p_2^{q_2}…p_n^{q_n}) và (X le 10^{18}). Tuy nhiên tập số này có thể lên tới (8 times 10^8). Ta cần tìm một cách khác tối ưu hơn.

Giờ hãy thử chia đôi tập số nguyên tố ra thành hai phần (A) và (B) như cách chúng ta vẫn đang làm và với mỗi tập, sinh ra các số có thể từ các số nguyên tố trong tập đó mà nhỏ hơn ({10^{18}}).

Để tìm ra số lớn thứ (k), ta sẽ chặt nhị phân đáp án. Với mỗi đáp án, ta cần check xem có bao nhiên số (le) đáp án đó. Duyệt qua các số được sinh ra từ tập (A), và cần tìm số số sinh ra từ tập (B) sao cho hai số nhân lại với nhau nhỏ hơn hoặc bằng đáp án. Ở đây ta có thể sử dụng kĩ thuật hai con trỏ sau khi đã sắp xếp lại các số sinh ra từ hai tập.

Độ phức tạp: (O(log(10^{18}) times sz(A)sz(B))) với (sz()) là số số được sinh ra từ tập nguyên tố đã cho.

Lưu ý: Trong trường hợp xấu nhất, một tập số nguyên tố gồm ({2, 3, 5, 7, 11, 13, 17, 19}) sẽ sinh ra được (7 times 10^6) số thỏa mãn, gây TLE. Để khắc phục, với mỗi dãy, ta sẽ chia hai dãy gồm (p_1, p_3, ..) và (p_2, p_4, …) để đảm bảo (sz(A)) và (sz(B)) không quá (10^6).

#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "n"
#define db long double
#define left daksdjlasjdlasjdlaskjdalsk
#define right daksdjla12dsqqqqq
#define all(v) v.begin(), v.end()

using namespace std;
const int MAXN = 1e18;
int n;
int p[20], k;
void ql(int idx, vector<int> &in, vector<int> &out, int gt){
    if (idx == in.size()){
        out.push_back(gt);
        return;
    }
    int val = gt;
    do{
        ql(idx + 1, in, out, val);

        if (MAXN / in[idx] < val) break;
        val = val * in[idx];
    } while (true);
}
vector<int> left, right, ansL, ansR;
int check(int mid){
    int pt = 0;
    int ans = 0;
    for (int i = 0; i < ansL.size(); i++){
        while (pt < ansR.size() && mid / ansL[i] >= ansR[pt]) pt++;
        ans += pt;
    }
    return ans;
}
void PROGRAM(int iTest){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> p[i];
        if (i & 1) left.push_back(p[i]);
        else right.push_back(p[i]);
    }
    ql(0, left, ansL, 1);
    ql(0, right, ansR, 1);
    sort(all(ansL), greater<int>());
    sort(all(ansR));
    cin >> k;
    int l = 1, r = 1e18, ans = -1;
    while (l <= r){
        int mid = (l + r) >> 1;
        if (check(mid) >= k) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << ans << endl;    
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int test = 1;
    for (int iTest = 1; iTest <= test; iTest++){
        PROGRAM(iTest);
    }
}

Bài tập áp dụng

Lời kết

Có thể thấy meet-in-the-middle rất hữu dụng và phổ biến, đặc biệt trong các kì thi lập trình thi đấu. Một tips hữu dụng cho các bạn: nếu thấy bài tập có giới hạn (n le ; approx 40) và có subtask nhỏ có (n le ; approx 20), hãy nghĩ ngay đến meet-in-the-middle nhé. Chúc các bạn ngày càng tiến bộ!

Xem thêm tại: https://www.facebook.com/codedreamedu/ và https://codedream.edu.vn/hoc-thuat-toan/

Bài viết liên quan:

Bài viết cùng chủ đề:

Đỗ Thị Hồng Ngát

Để lại một bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *