+1

Duyệt phân đôi tập hợp (Meet In The Middle)

I. Giới thiệu chung

1. Phát biểu bài toán

Trong các kì thi lập trình, những bài toán liên quan tới duyệt toàn bộ nghiệm không hề hiếm. Đôi khi, chúng ta sẽ gặp phải những bài toán mà bắt buộc phải duyệt toàn bộ các cấu hình nghiệm để tìm ra các nghiệm thỏa mãn yêu cầu đề bài. Cùng xét một bài toán ví dụ sau:

Cho một tập hợp AA gồm nn phần tử a1,a2,,ana_1, a_2, \dots, a_n. Hãy xác định có bao nhiêu tập hợp con của tập AA có tổng đúng bằng giá trị ss cho trước?

Input:

  • Dòng đầu tiên chứa hai số nguyên dương nnss.
  • Dòng thứ hai chứa nn số nguyên dương a1,a2,,ana_1, a_2, \dots, a_n phân tách nhau bởi dấu cách.

Ràng buộc:

  • 1n401 \le n \le 40.
  • 1s10181 \le s \le 10^{18}.
  • 1ai1012;i:1in1 \le a_i \le 10^{12}; \forall i: 1 \le i \le n.

Output:

  • Một số nguyên là số lượng tập hợp con tìm được.

Sample Input:

5 10
1 9 8 2 1

Sample Output:

4

2. Kĩ thuật Duyệt phân đôi tập hợp

Ý tưởng

Đối với những bài toán như trên, cách làm quen thuộc nhất là duyệt quay lui thử chọn ra tất cả các tập hợp khác nhau và tính tổng của chúng. Mô hình như sau (sử dụng kĩ thuật duyệt nhị phân 010 - 1):

void backtrack(int i, int subset_sum, vector < int > &a, int s, int &res)
{
    for (int j = 0; j <= 1; ++j)
    {
        subset_sum += a[i] * j;

        if (i == n)
            res += (subset_sum == s);
        else 
            backtrack(i + 1, subset_sum a, s, res);

        subset_sum -= a[i] * j;
    }
}

Tuy nhiên, giới hạn nn của bài toán là 40,40, đồng nghĩa với việc thuật toán trên sẽ có độ phức tạp lên tới O(240),O(2^{40}), máy tính thông thường khó có thể chạy được trong thời gian cho phép.

Kĩ thuật Duyệt phân đôi tập hợp ra đời để giải quyết những bài toán như vậy. Đây là kĩ thuật sử dụng cho các bài toán có giới hạn nhỏ, tuy nhiên lại không đủ nhỏ để áp dụng kĩ thuật duyệt toàn bộ nghiệm thông thường. Trong kĩ thuật này, chúng ta chia tập hợp ban đầu thành hai phần, duyệt sinh toàn bộ các cấu hình ở mỗi phần rồi kết hợp hai bên lại để tạo thành nghiệm của bài toán. Ý tưởng sẽ như sau:

  • Bước 11: Chia tập hợp AA ban đầu thành hai tập con: a[1...n+12]a\left[1...\frac{n + 1}{2}\right]a[n+12+1...n]a\left[\frac{n + 1}{2} + 1...n\right].
  • Bước 22: Sử dụng quay lui để sinh tất cả các tổng ở mỗi tập con, lưu vào hai mảng là sum_left\text{sum\_left}sum_right\text{sum\_right}. Chú ý, ta sẽ lưu cả tổng 00 (không chọn phần tử nào) để phục vụ cho quá trình xử lý tiếp theo.
  • Bước 33: Sắp xếp lại các giá trị trong mảng sum_left\text{sum\_left} tăng dần.
  • Bước 44: Duyệt các tổng s1s_1 trên dãy tổng sum_right\text{sum\_right}. Ứng với mỗi tổng s1,s_1, ta cần xác định có bao nhiêu tổng s2s_2 trên dãy tổng sum_left\text{sum\_left} thỏa mãn: s1+s2=ss_1 + s_2 = s. Vì dãy tổng sum_left\text{sum\_left} đã sắp xếp tăng dần, nên bước này có thể làm bằng tìm kiếm nhị phân. Ngoài ra ta đã lưu cả cách lựa chọn tập rỗng ở hai dãy, nên sẽ tính được cả những trường hợp từng giá trị của mỗi bên bằng đúng ss.

Như vậy, độ phức tạp của giải thuật sẽ chỉ còn là O(2n2.log(2n2)),O\big(2^{\frac{n}{2}}.\log(2^{\frac{n}{2}})\big), hoàn toàn đáp ứng được thời gian chạy của các kì thi lập trình.

Cài đặt

#include <bits/stdc++.h>
#define int long long

using namespace std;

void enter(int &n, int &s, vector < int > &a)
{
    cin >> n >> s;

    a.resize(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
}

void generate_set(int i, int limit, int sum, vector < int > &a, vector < int > &subset_sum)
{
    for (int j = 0; j <= 1; ++j)
    {
        sum += a[i] * j;

        if (i == limit)
            subset_sum.push_back(sum);
        else
            generate_set(i + 1, limit, sum, a, subset_sum);

        sum -= a[i] * j;
    }
}

void solution(int n, int s, vector < int > &a)
{
    vector < int > sum_left, sum_right;
    generate_set(1, (n + 1) / 2, 0, a, sum_left);
    generate_set((n + 1) / 2 + 1, n, 0, a, sum_right);
    sort(sum_left.begin(), sum_left.end());

    int res = 0;
    for (int cur_s: sum_right)
    {
        if (cur_s > s)
            continue;

        auto p = equal_range(sum_left.begin(), sum_left.end(), s - cur_s);

        if (*p.first == s - cur_s)
            res += distance(p.first, p.second);
    }

    cout << res;
}

main()
{
    int n, s;
    vector < int > a;

    enter(n, s, a);
    solution(n, s, a);

    return 0;
}

II. Một số bài toán minh họa

1. Tổng vector

Đề bài

Trên mặt phẳng tọa độ Oxy,Oxy, cho trước nn vectors. Mỗi một vectors được cho bởi hai chỉ số xxyy. Ta định nghĩa vector tổng của hai vector (x1,y1)(x_1, y_1)(x2,y2)(x_2, y_2) là vector (x1+x2,y1+y2)(x_1 + x_2, y_1 + y_2). Bây giờ, cần chọn ra một số vectors trong số nn vectors cho trước, sao cho vector tổng của chúng là vector (u,v)(u, v).

Yêu cầu: Biết trước vector tổng (u,v),(u, v), hãy đếm số cách chọn thỏa mãn yêu cầu trên?

Input:

  • Dòng đầu tiên chứa số nguyên dương nn.
  • nn dòng tiếp theo, dòng thứ ii chứa hai số nguyên xi,yix_i, y_i thể hiện một vector trên mặt phẳng tọa độ.
  • Dòng cuối cùng chứa hai số nguyên u,vu, v - vector tổng.

Ràng buộc:

  • 1n301 \le n \le 30.
  • xi,yi100;i:1in|x_i|, |y_i| \le 100; \forall i: 1 \le i \le n.
  • u,v109|u|, |v| \le 10^9.

Output:

  • In ra một số nguyên là số lượng cách chọn thỏa mãn.

Sample Input:

4
0 0
-1 2
2 5
3 3
2 5

Sample Output:

4

Ý tưởng

Sử dụng quay lui thông thường trong bài này sẽ không thể đáp ứng thời gian chạy, vì độ phức tạp sẽ lên tới O(230)O(2^30).

Ta sử dụng kĩ thuật duyệt phân đôi tập hợp để giải quyết bài toán này. Chia tập các vector ban đầu thành hai phần, duyệt quay lui để sinh ra tất cả các vector tổng trên mỗi phần. Bước này ta sẽ kết hợp thêm map để đếm số lần xuất hiện của các vector tổng trên từng phần tạo ra, lưu vào hai mapcnt1cnt1cnt2cnt2.

Kế đến, duyệt qua tất cả các vector tổng (x0,y0)(x_0, y_0) trên cnt1,cnt1, và đi tìm xem có bao nhiêu vector bằng (ux0,vy0)(u - x_0, v - y_0) trên cnt2cnt2. Bước này ta làm dễ dàng bằng map. Kết quả sẽ tăng thêm một lượng là cnt1[(x0,y0)]×cnt2[(ux0,vy0)]cnt1\big[(x_0, y_0)\big] \times cnt2\big[(u - x_0, v - y_0)\big].

Độ phức tạp: O(2n2)O\left(2^{\frac{n}{2}}\right).

Cài đặt

#include <bits/stdc++.h>
#define int long long
#define task "vector_sum."

using namespace std;

void enter(int &n, vector < pair < int, int > > &vectors, int &u, int &v)
{
    cin >> n;

    vectors.resize(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> vectors[i].first >> vectors[i].second;

    cin >> u >> v;
}

void generate_set(int i, int limit, pair < int, int > vector_sum,
                  vector < pair < int, int > > &vectors,
                  map < pair < int, int >, int > &cnt)
{
    for (int j = 0; j <= 1; ++j)
    {
        vector_sum.first += vectors[i].first * j;
        vector_sum.second += vectors[i].second * j;

        if (i == limit)
            ++cnt[vector_sum];
        else
            generate_set(i + 1, limit, vector_sum, vectors, cnt);

        vector_sum.first -= vectors[i].first * j;
        vector_sum.second -= vectors[i].second * j;
    }
}

void solution(int n, vector < pair < int, int > > &vectors, int u, int v)
{
    // Duyệt sinh tất cả các vector tổng từ hai nửa tập hợp, đếm phân phối bằng map.
    map < pair < int, int >, int > cnt_left, cnt_right;
    generate_set(1, (n + 1) / 2, {0, 0}, vectors, cnt_left);
    generate_set((n + 1) / 2 + 1, n, {0, 0}, vectors, cnt_right);

    int res = 0;
    for (auto v1: cnt_right)
    {
        // Xét vector tổng tạo ra là (x, y) trên tập bên phải, thì vector 
        // cần tìm trên tập bên trái là (u - x, v - y).
        pair < int, int > v2 = {u - v1.first.first, v - v1.first.second};

        if (cnt_left.count(v2))
            res += (cnt_left[v2] * v1.second);
    }

    cout << res;
}

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

    int n, u, v;
    vector < pair < int, int > > vectors;

    enter(n, vectors, u, v);
    solution(n, vectors, u, v);

    return 0;
}

2. Ước số

Đề bài

Một số nguyên dương nn được phân tích thành thừa số nguyên tố như sau:

n=p1k1×p2k2××pmkmn = p_1^{k_1} \times p_2^{k_2} \times \cdots \times p_m^{k_m}

Yêu cầu: Cho hai số nguyên không âm A,B (AB),A, B \ (A \le B), đếm số lượng ước của nn thuộc đoạn [A,B]?[A, B]?

Input:

  • Dòng đầu tiên chứa số nguyên dương mm.
  • Tiếp theo là mm dòng, dòng thứ ii chứa hai số nguyên dương pip_ikik_i thể hiện phân tích nguyên tố của n,n, trong đó các giá trị pip_i đôi một khác nhau.
  • Ba dòng cuối cùng tương ứng với ba câu hỏi, mỗi dòng chứa hai số nguyên không âm (A,B)(A, B) tương ứng với một câu hỏi.

Ràng buộc:

  • 1m251 \le m \le 25.
  • 1pi,ki109;i:1im1 \le p_i, k_i \le 10^9; \forall i: 1 \le i \le m.
  • 0AB1090 \le A \le B \le 10^9.

Output:

  • Trên ba dòng, mỗi dòng ghi một số nguyên là đáp án tương ứng với câu hỏi ở đầu vào.

Sample Input:

3
2 4
3 4
5 4
1 5
1 10
1 5 

Sample Output:

5
9
5

Ý tưởng

Đây là một bài không đơn giản, cần sử dụng kĩ thuật duyệt phân đôi tập hợp, kết hợp cùng kĩ thuật nhánh và cận. Về cơ bản, chúng ta vẫn tiến hành chia đôi tập các số nguyên tố ra và tạo tất cả các tích có thể giữa chúng, rồi ghép các tập con của hai bên lại để tạo thành các ước trong đoạn [A,B][A, B].

Đối với công việc đầu tiên là sinh mọi tập con của tập các số nguyên tố ban đầu, ta sẽ có ba bước:

  • Bước 1: Tạo một vector expo[i]expo[i]: Là lũy thừa lớn nhất của số nguyên tố thứ ii và không vượt quá giá trị BB (có chứa cả giá trị 11).
  • Bước 2: Chia tập các số nguyên tố ra làm hai nửa. Áp dụng kĩ thuật duyệt phân đôi tập hợp, sinh ra mọi tập con của hai nửa đó và lưu tích của tập con vào hai tập hợp là left_set\text{left\_set}right_set\text{right\_set}. Kĩ thuật ở đây là với mỗi số nguyên tố i,i, ta sẽ lựa chọn lần lượt các lũy thừa của nó: p[i]0,p[i]1,...,p[i]max;p[i]^0, p[i]^1,...,p[i]^{max}; các lũy thừa này đều đã được tính sẵn bằng vector expo[i]expo[i] mà bước 11 vừa tính. Thêm một lưu ý, là mặc dù số lượng tập con có thể rất lớn, nhưng khoảng giá trị [A, B] thì chỉ là 10^9. Vì thế ta áp dụng thêm kĩ thuật nhánh cận trong quá trình sinh, nếu thấy tích hiện tại đã vượt quá B thì không cần nhân thêm các lũy thừa của các số nguyên tố sau vào nữa.
  • Bước 3: Sắp xếp lại hai tập hợp lớn left_set\text{left\_set}right_set,\text{right\_set}, giờ hai tập này chứa các tích sinh ra của hai nửa.

Công việc cuối cùng là ghép các giá trị của hai tập. Ứng với mỗi tích mulmul trên tập left_set,\text{left\_set}, chặt nhị phân tìm đoạn vị trí [pos_l, pos_r][\text{pos\_l, pos\_r}] trên tập right_set\text{right\_set} sao cho tích mul nhân với bất kỳ tích nào từ pos_l\text{pos\_l} tới pos_r\text{pos\_r} đều không bị nằm ngoài đoạn [A,B][A, B]. Khi đó, số lượng ước của nn trong đoạn [A,B][A, B] sinh ra bởi mulmul là: (pos_rpos_l+1)(\text{pos\_r} - \text{pos\_l} + 1). Chúng ta cũng không cần xét riêng các tích trên từng tập hợp, vì mỗi tập hợp đều chứa một giá trị 1,1, nên sẽ xét được luôn các tập con thuộc từng tập có là ước của nn thuộc đoạn [A,B][A, B] hay không.

Cài đặt

#include <bits/stdc++.h>
#define task "divisors."
#define inf 1e9 + 7
#define x first
#define y second

using namespace std;
const int maxm = 26;
int M;
long long product = 1;
pair < int, int > prime[maxm], q[4];
vector < long long > expo[maxm], left_set, right_set;

void enter()
{
    cin >> M;

    for (int i = 1; i <= M; ++i)
        cin >> prime[i].first >> prime[i].second;

    for (int i = 1; i <= 3; ++i)
        cin >> q[i].first >> q[i].second;
}

void create_exponentiation(int max_value)
{
    for (int i = 1; i <= M; ++i)
    {
        expo[i].push_back(1);

        for (int j = 1; j <= prime[i].second && expo[i][j - 1] * prime[i].first <= max_value; ++j)
            expo[i].push_back(expo[i][j - 1] * prime[i].first);
    }
}

void recursion(int i, int limit, int max_value, vector < long long > &current_set)
{
    if (i > limit)
        return;

    if (product * expo[i][0] > max_value)
        return;

    for (int j = 0; j < (int)expo[i].size(); ++j)
    {
        product *= expo[i][j];

        if (i == limit)
            current_set.push_back(product);
        else
            recursion(i + 1, limit, max_value, current_set);

        product /= expo[i][j];
    }
}

void solution()
{
    // Create all exponentiations p[i]^j such that p[i]^j  does not 
    // exceed the greatest value of B.
    int max_value = max(q[1].second, max(q[2].second, q[3].second));
    create_exponentiation(max_value);

    // Generate two sets of products can be formed by the prime factorization
    recursion(1, (M + 1) / 2, max_value, left_set);
    recursion((M + 1) / 2 + 1, M, max_value, right_set);
    sort(left_set.begin(), left_set.end());
    sort(right_set.begin(), right_set.end());

    // Separately handle the case that the prime factorization only 
    // consists of 1 prime.
    if (right_set.empty()) 
        right_set.push_back(1);

    // Answer the 3 queries.
    for (int i = 1; i <= 3; ++i)
    {
        int res = 0;

        // For each generated product in the left set, find the position range [pos_l, pos_r] 
        // in the right set that can be paired with it to create a product belonging to the 
        // range [A,B]. The product has a form of A <= x * y <= B.
        for (int j = 0; j < (int)left_set.size(); ++j)
        {
            int mul = left_set[j];
            if (mul > max_value)
                break;

            auto it1 = lower_bound(right_set.begin(), right_set.end(), (q[i].first + mul - 1) / mul);
            auto it2 = upper_bound(right_set.begin(), right_set.end(), q[i].second / mul) - 1;

            // If at least one position exists, get the length of the segment which can be paired.
            if (it1 != right_set.end()) 
            {
                int pos_l = it1 - right_set.begin(), pos_r = it2 - right_set.begin();
                res += (pos_r - pos_l + 1);
            }
        }

        cout << res << endl;
    }
}

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

    enter();
    solution();

    return 0;
}

III. Tài liệu tham khảo


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.