Bài 25.1. Nguyên lý và cách tiếp cận Meet in the middle

Chào mừng bạn đến với một bài viết mới trong chuỗi blog về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ cùng nhau tìm hiểu về một kỹ thuật giải thuật khá thú vị và mạnh mẽ, đặc biệt hữu ích khi đối mặt với các bài toán có độ phức tạp theo cấp số mũ mà phương pháp vét cạn (brute force) thông thường không thể giải quyết kịp thời. Đó chính là kỹ thuật Meet in the middle (Gặp gỡ ở giữa).

Trong thế giới lập trình thi đấu và giải thuật, có những bài toán đòi hỏi chúng ta phải kiểm tra hoặc kết hợp một lượng lớn các khả năng có thể có. Ví dụ điển hình là các bài toán liên quan đến tìm tập con (subset), phân hoạch (partition), hoặc các cấu hình (configurations) khác. Nếu một bài toán yêu cầu chúng ta duyệt qua tất cả $2^N$ tập con của $N$ phần tử, thì với $N$ khoảng 30-40, phương pháp vét cạn sẽ vượt quá giới hạn thời gian cho phép. Meet in the middle xuất hiện như một "cứu cánh" trong nhiều tình huống như vậy.

Nguyên lý hoạt động của Meet in the middle

Nguyên lý cốt lõi của Meet in the middle rất đơn giản: thay vì cố gắng xây dựng một giải pháp hoàn chỉnh từ đầu đến cuối chỉ bằng một "đường đi", chúng ta chia bài toán thành hai nửa, giải quyết độc lập cho mỗi nửa để tạo ra các kết quả trung gian, và sau đó tìm cách để các kết quả từ hai nửa này gặp nhau ở giữa để hình thành giải pháp cuối cùng một cách hiệu quả.

Hãy tưởng tượng bạn cần đi từ điểm A đến điểm B rất xa. Thay vì một người đi bộ toàn bộ quãng đường từ A đến B, hai người bắt đầu đi cùng lúc: một từ A đi về phía B, một từ B đi về phía A. Họ sẽ gặp nhau ở đâu đó trên đường. Tổng thời gian di chuyển của mỗi người chỉ bằng một nửa so với việc một người đi toàn bộ quãng đường (giả sử tốc độ như nhau). Tương tự, Meet in the middle giúp giảm độ phức tạp từ O(k^N) xuống còn khoảng O(k^(N/2)), một sự cải thiện đáng kể!

Cách tiếp cận Meet in the middle

Các bước cơ bản để áp dụng kỹ thuật Meet in the middle thường bao gồm:

Chia đôi dữ liệu hoặc không gian trạng thái: Tách tập hợp đầu vào (ví dụ: mảng các số) hoặc không gian trạng thái của bài toán thành hai nửa gần bằng nhau. Thường thì ta sẽ chia mảng N phần tử thành hai mảng N/2 phần tử.
Giải quyết độc lập cho từng nửa: Đối với nửa đầu tiên, thực hiện vét cạn (hoặc một phương pháp khác) để sinh ra tất cả các kết quả hoặc trạng thái có thể đạt được từ nửa này. Lưu trữ các kết quả này vào một cấu trúc dữ liệu nào đó (ví dụ: vector, set, map). Lặp lại quá trình tương tự cho nửa thứ hai, sinh ra tất cả kết quả/trạng thái từ nửa này và lưu trữ chúng vào một cấu trúc dữ liệu khác.
Kết hợp kết quả (Gặp gỡ): Đây là bước quan trọng nhất. Duyệt qua các kết quả từ nửa đầu tiên. Đối với mỗi kết quả từ nửa đầu, tìm kiếm trong tập kết quả của nửa thứ hai một kết quả phù hợp sao cho khi kết hợp chúng lại sẽ tạo thành giải pháp mong muốn cho bài toán ban đầu. Bước tìm kiếm và kết hợp này cần phải hiệu quả, thường sử dụng các kỹ thuật như sắp xếp (sorting) kết hợp tìm kiếm nhị phân (binary search), hoặc sử dụng bảng băm (hash map/set).

Độ phức tạp của bước 2 là O(k^(N/2)) cho mỗi nửa (nếu có k lựa chọn cho mỗi phần tử). Độ phức tạp của bước 3 thường là O(k^(N/2) log(k^(N/2))) nếu sử dụng sắp xếp và tìm kiếm nhị phân, hoặc O(k^(N/2)) trung bình nếu sử dụng bảng băm. Tổng cộng, độ phức tạp được cải thiện đáng kể so với O(k^N) của vét cạn toàn bộ.

Ví dụ minh họa: Bài toán Tổng con (Subset Sum)

Đây là một trong những bài toán kinh điển nhất để minh họa kỹ thuật Meet in the middle.

Bài toán: Cho một mảng gồm N số nguyên và một số nguyên mục tiêu K. Hãy kiểm tra xem có tồn tại một tập con các số trong mảng có tổng bằng K hay không.

Giả sử N có thể lên tới 40.

Phân tích: Phương pháp vét cạn đơn giản là kiểm tra tất cả 2^N tập con. Với N=40, 2^40 là một con số khổng lồ, vượt quá khả năng tính toán trong thời gian giới hạn.

Áp dụng Meet in the middle:

Chia đôi: Chia mảng gốc N phần tử thành hai mảng con: arr1 chứa N/2 phần tử đầu tiên và arr2 chứa N - N/2 phần tử còn lại. (Chú ý: N/2 có thể làm tròn xuống hoặc lên).
Giải quyết độc lập:
- Sinh ra tất cả các tổng con có thể có từ các phần tử trong arr1. Lưu chúng vào một vector gọi là sums1. Số lượng tổng con sẽ là 2^(N/2).
- Sinh ra tất cả các tổng con có thể có từ các phần tử trong arr2. Lưu chúng vào một vector gọi là sums2. Số lượng tổng con sẽ là 2^(N-N/2).
- Để sinh ra các tổng con, chúng ta có thể sử dụng hàm đệ quy hoặc bitmask. Với N/2 nhỏ (khoảng 20), 2^(N/2) khoảng 1 triệu, hoàn toàn khả thi.
Kết hợp kết quả: Chúng ta cần kiểm tra xem có tồn tại s1 trong sums1 và s2 trong sums2 sao cho s1 + s2 = K hay không. Tương đương, với mỗi s1 trong sums1, chúng ta cần kiểm tra xem K - s1 có tồn tại trong sums2 hay không.
- Cách hiệu quả để làm điều này là sắp xếp sums2.
- Sau đó, duyệt qua từng s1 trong sums1. Đối với mỗi s1, sử dụng tìm kiếm nhị phân (binary search) trên sums2 để tìm xem có phần tử nào có giá trị bằng K - s1 không.

Cài đặt C++ cho bài toán Subset Sum (kiểm tra tồn tại tổng K):

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm> // For sort and binary_search

// Hàm đệ quy để sinh ra tất cả tổng con cho một nửa mảng
void generate_subset_sums(const std::vector<int>& arr, int index, long long current_sum, std::vector<long long>& sums) {
    // Trường hợp cơ bản: đã duyệt hết các phần tử của nửa mảng
    if (index == arr.size()) {
        sums.push_back(current_sum);
        return;
    }

    // Lựa chọn 1: Không bao gồm phần tử hiện tại
    generate_subset_sums(arr, index + 1, current_sum, sums);

    // Lựa chọn 2: Bao gồm phần tử hiện tại
    generate_subset_sums(arr, index + 1, current_sum + arr[index], sums);
}

int main() {
    int n;
    long long k;
    std::cin >> n >> k;

    std::vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }

    // Chia mảng thành hai nửa
    int mid = n / 2;
    std::vector<int> arr1(arr.begin(), arr.begin() + mid);
    std::vector<int> arr2(arr.begin() + mid, arr.end());

    std::vector<long long> sums1;
    std::vector<long long> sums2;

    // Sinh tổng con cho nửa đầu
    generate_subset_sums(arr1, 0, 0, sums1);

    // Sinh tổng con cho nửa sau
    generate_subset_sums(arr2, 0, 0, sums2);

    // Bước gặp gỡ ở giữa:
    // Sắp xếp sums2 để có thể tìm kiếm nhị phân hiệu quả
    std::sort(sums2.begin(), sums2.end());

    bool found = false;
    // Duyệt qua từng tổng s1 từ nửa đầu
    for (long long s1 : sums1) {
        // Chúng ta cần tìm một s2 trong sums2 sao cho s1 + s2 = K, tức là s2 = K - s1
        long long required_s2 = k - s1;

        // Sử dụng tìm kiếm nhị phân trong sums2 đã được sắp xếp
        if (std::binary_search(sums2.begin(), sums2.end(), required_s2)) {
            found = true;
            break;
        }
    }

    if (found) {
        std::cout << "YES" << std::endl;
    } else {
        std::cout << "NO" << std::endl;
    }

    return 0;
}

Giải thích code:

Hàm generate_subset_sums là một hàm đệ quy đơn giản để duyệt qua tất cả các tập con của một mảng con. Với mỗi phần tử, chúng ta có hai lựa chọn: bao gồm nó vào tổng hiện tại hoặc không. Hàm dừng khi đã xem xét tất cả các phần tử và thêm tổng cuối cùng vào vector sums.
Trong hàm main, chúng ta đọc đầu vào n và k, sau đó chia mảng arr thành hai vector arr1 và arr2.
Chúng ta gọi generate_subset_sums hai lần để tạo ra sums1 (tất cả tổng con từ arr1) và sums2 (tất cả tổng con từ arr2).
Để bước kết hợp hiệu quả, chúng ta sắp xếp sums2 bằng std::sort.
Sau đó, chúng ta lặp qua từng tổng s1 trong sums1. Đối với mỗi s1, chúng ta tính giá trị required_s2 cần tìm trong sums2 (k - s1).
Hàm std::binary_search được sử dụng để kiểm tra xem required_s2 có tồn tại trong sums2 đã sắp xếp hay không. Nếu tìm thấy dù chỉ một cặp s1, s2 thỏa mãn, chúng ta đặt found thành true và thoát vòng lặp.
Cuối cùng, in ra "YES" hoặc "NO" dựa trên giá trị của found.

Độ phức tạp thời gian của giải pháp này là O(2^(N/2) N) do việc sinh tổng con mất O(2^(N/2)), sắp xếp mất O(2^(N/2) log(2^(N/2))), và vòng lặp kết hợp mất O(2^(N/2) log(2^(N/2))) (mỗi lần tìm kiếm nhị phân mất O(log(2^(N/2))) = O(N/2)). Điều này hiệu quả hơn rất nhiều so với O(2^N) khi N lớn. Độ phức tạp không gian là O(2^(N/2)) để lưu trữ sums1 và sums2.

Ví dụ minh họa 2: Bài toán Tổng con nhỏ hơn hoặc bằng K (Maximum Subset Sum <= K)

Một biến thể phổ biến khác của bài toán Tổng con là tìm tổng con lớn nhất không vượt quá một giá trị K cho trước.

Bài toán: Cho một mảng gồm N số nguyên không âm và một số nguyên K. Tìm tổng con lớn nhất có thể tạo thành từ các phần tử trong mảng mà tổng đó nhỏ hơn hoặc bằng K.

Giả sử N có thể lên tới 40.

Áp dụng Meet in the middle: Các bước 1 và 2 tương tự như bài toán trước:

Chia đôi: Chia mảng arr thành arr1 (N/2 phần tử) và arr2 (N - N/2 phần tử).
Giải quyết độc lập: Sinh ra sums1 (tất cả tổng con từ arr1) và sums2 (tất cả tổng con từ arr2).
Kết hợp kết quả: Chúng ta cần tìm cặp s1 trong sums1 và s2 trong sums2 sao cho s1 + s2 <= K, và chúng ta muốn tối đa hóa giá trị s1 + s2. Tương đương, đối với mỗi s1 trong sums1, chúng ta cần tìm giá trị s2 lớn nhất trong sums2 sao cho s2 <= K - s1.
- Để tìm s2 lớn nhất thỏa mãn điều kiện s2 <= K - s1 một cách hiệu quả, chúng ta lại sắp xếp sums2.
- Duyệt qua từng s1 trong sums1. Đối với mỗi s1, chúng ta tìm kiếm trong sums2 giá trị lớn nhất không vượt quá K - s1.
- Trong một mảng đã sắp xếp, giá trị lớn nhất không vượt quá một ngưỡng (K - s1) có thể được tìm thấy bằng cách sử dụng std::upper_bound. upper_bound(begin, end, value) trả về một iterator tới phần tử đầu tiên lớn hơn value. Do đó, phần tử ngay trước iterator này (nếu nó không phải là begin) chính là phần tử lớn nhất nhỏ hơn hoặc bằng value.

Cài đặt C++ cho bài toán Maximum Subset Sum <= K:

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm> // For sort and upper_bound

// Hàm đệ quy để sinh ra tất cả tổng con cho một nửa mảng
void generate_subset_sums_recursive(const std::vector<int>& arr, int index, long long current_sum, std::vector<long long>& sums) {
    if (index == arr.size()) {
        sums.push_back(current_sum);
        return;
    }

    // Lựa chọn 1: Không bao gồm phần tử hiện tại
    generate_subset_sums_recursive(arr, index + 1, current_sum, sums);

    // Lựa chọn 2: Bao gồm phần tử hiện tại (chỉ thêm nếu tổng không tràn số, tùy vào giới hạn bài toán)
    // Ở đây giả sử tổng có thể lên tới K, dùng long long để an toàn
    generate_subset_sums_recursive(arr, index + 1, current_sum + arr[index], sums);
}

int main() {
    int n;
    long long k; // K có thể lớn, dùng long long
    std::cin >> n >> k;

    std::vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }

    // Chia mảng thành hai nửa
    int mid = n / 2;
    std::vector<int> arr1(arr.begin(), arr.begin() + mid);
    std::vector<int> arr2(arr.begin() + mid, arr.end());

    std::vector<long long> sums1;
    std::vector<long long> sums2;

    // Sinh tổng con cho nửa đầu
    generate_subset_sums_recursive(arr1, 0, 0, sums1);

    // Sinh tổng con cho nửa sau
    generate_subset_sums_recursive(arr2, 0, 0, sums2);

    // Bước gặp gỡ ở giữa:
    // Sắp xếp sums2
    std::sort(sums2.begin(), sums2.end());

    long long max_sum = 0; // Khởi tạo tổng lớn nhất tìm được là 0

    // Duyệt qua từng tổng s1 từ nửa đầu
    for (long long s1 : sums1) {
        // Chúng ta cần tìm s2 lớn nhất trong sums2 sao cho s1 + s2 <= K
        // Điều này tương đương s2 <= K - s1
        long long remaining_k = k - s1;

        // Nếu remaining_k âm, không thể kết hợp s1 với bất kỳ số không âm nào từ sums2
        if (remaining_k < 0) {
            continue;
        }

        // Tìm kiếm s2 lớn nhất trong sums2 <= remaining_k
        // std::upper_bound(begin, end, value) tìm phần tử ĐẦU TIÊN > value
        // Do đó, phần tử ngay trước nó (iterator - 1) chính là phần tử LỚN NHẤT <= value
        auto it = std::upper_bound(sums2.begin(), sums2.end(), remaining_k);

        // Nếu it không phải là sums2.begin(), nghĩa là có ít nhất một phần tử <= remaining_k
        if (it != sums2.begin()) {
            // Lấy phần tử ngay trước it
            long long s2 = *(--it);
            // Cập nhật max_sum nếu s1 + s2 lớn hơn
            max_sum = std::max(max_sum, s1 + s2);
        }
        // Nếu it == sums2.begin(), nghĩa là tất cả các phần tử trong sums2 đều lớn hơn remaining_k.
        // Trường hợp này chỉ có thể kết hợp s1 với tổng rỗng (0) của sums2.
        // Tổng 0 luôn có trong sums2 nếu hàm generate_subset_sums bắt đầu với 0 và vector arr2 không rỗng.
        // Tuy nhiên, max_sum đã được khởi tạo là 0 và s1 + 0 chỉ bằng s1, s1 đã được xem xét trong loop sums1.
        // Nên không cần xử lý đặc biệt ở đây, max_sum sẽ tự cập nhật nếu s1 > max_sum ban đầu.
    }

    std::cout << max_sum << std::endl;

    return 0;
}

Giải thích code:

Phần sinh tổng con (generate_subset_sums_recursive) giống như ví dụ trước.
Trong main, sau khi sinh và sắp xếp sums2, chúng ta khởi tạo max_sum bằng 0.
Duyệt qua từng tổng s1 trong sums1.
Tính remaining_k = k - s1. Đây là giới hạn tối đa mà s2 từ sums2 có thể có để s1 + s2 không vượt quá k.
Nếu remaining_k âm, không có cách nào cộng thêm số không âm từ sums2 để đạt tổng dương s1 + s2 <= k. Bỏ qua s1 này.
Sử dụng std::upper_bound(sums2.begin(), sums2.end(), remaining_k) để tìm iterator it tới phần tử đầu tiên trong sums2 lớn hơn remaining_k.
Nếu it không phải là sums2.begin() (tức là sums2 không rỗng và có ít nhất một phần tử nhỏ hơn hoặc bằng remaining_k), thì *(--it) chính là phần tử lớn nhất trong sums2 nhỏ hơn hoặc bằng remaining_k.
Cập nhật max_sum bằng giá trị lớn nhất giữa max_sum hiện tại và s1 + s2.
Cuối cùng, in ra max_sum.

Cách tiếp cận này cho phép chúng ta giải quyết bài toán Maximum Subset Sum <= K với N lên tới 40-45 một cách hiệu quả, trong khi vét cạn toàn bộ sẽ gặp khó khăn với N > 25.

Ưu điểm và Nhược điểm

Ưu điểm:

Giảm đáng kể độ phức tạp thời gian cho nhiều bài toán tổ hợp từ O(k^N) xuống O(k^(N/2)).
Khá linh hoạt, có thể áp dụng cho nhiều biến thể bài toán (kiểm tra tồn tại, tìm giá trị lớn nhất/nhỏ nhất, đếm số lượng).

Nhược điểm:

Yêu cầu bộ nhớ lớn để lưu trữ các kết quả trung gian (O(k^(N/2))). Đây có thể là giới hạn nếu k^(N/2) quá lớn.
Không phải bài toán nào cũng có thể chia thành hai nửa và kết hợp kết quả một cách đơn giản. Bài toán cần có tính chất "tổng hợp" từ hai tập con độc lập.

Bài tập ví dụ:

Sắp xếp theo chẵn lẻ bit

Trong một buổi phỏng vấn tại công ty, FullHouse Dev được giao một bài toán thú vị về xử lý bit. Họ cần phải viết một thuật toán sắp xếp đặc biệt dựa trên số lượng bit 1 trong biểu diễn nhị phân của các số.

Bài toán

FullHouse Dev được cung cấp một mảng $A$ gồm $n$ số nguyên. Nhiệm vụ của họ là sắp xếp lại mảng theo các điều kiện sau:

Các số có số lượng bit 1 chẵn sẽ xuất hiện trước theo thứ tự tăng dần
Tiếp theo là các số có số lượng bit 1 lẻ, cũng được sắp xếp theo thứ tự tăng dần

INPUT FORMAT:

Dòng đầu tiên chứa số nguyên $T$ - số lượng test case
Với mỗi test case:
- Dòng đầu tiên chứa số nguyên $n$
- Dòng thứ hai chứa $n$ số nguyên của mảng $A$

OUTPUT FORMAT:

Với mỗi test case, in ra mảng đã được sắp xếp theo yêu cầu trên một dòng mới

Ràng buộc:

$1 \leq T \leq 100$
$1 \leq n \leq 10^5$
$1 \leq A[i] \leq 10^9$

Ví dụ

INPUT

1
6
5 2 8 12 7 6

OUTPUT

5 6 12 2 7 8

Giải thích

Với mảng đầu vào [5, 2, 8, 12, 7, 6], kết quả [5, 6, 12, 2, 7, 8] được sắp xếp như sau:

Các số có số lượng bit 1 chẵn: 5(101), 6(110), 12(1100)
Các số có số lượng bit 1 lẻ: 2(10), 7(111), 8(100) Chào bạn, đây là hướng dẫn ngắn gọn để giải bài toán "Sắp xếp theo chẵn lẻ bit" bằng C++:

Hiểu yêu cầu: Bài toán yêu cầu sắp xếp mảng sao cho các số có số lượng bit 1 chẵn đứng trước, theo thứ tự tăng dần. Sau đó mới đến các số có số lượng bit 1 lẻ, cũng theo thứ tự tăng dần.
Ý tưởng chính:
- Cần xác định số lượng bit 1 (popcount) trong biểu diễn nhị phân của mỗi số.
- Cần phân loại các số dựa trên tính chẵn/lẻ của số lượng bit 1 này.
- Sử dụng một hàm so sánh tùy chỉnh (custom comparator) với thuật toán sắp xếp có sẵn (như std::sort trong C++).
Chi tiết hàm so sánh:
- Hàm so sánh nhận hai số nguyên a và b.
- Tính số lượng bit 1 cho a và b (gọi là countA và countB). Bạn có thể tự viết hàm đếm bit hoặc sử dụng hàm có sẵn trong C++ như __builtin_popcount (rất hiệu quả).
- Kiểm tra tính chẵn lẻ của countA và countB (parityA = countA % 2, parityB = countB % 2).
- Logic so sánh:
  - Nếu parityA khác parityB: Số có số lượng bit 1 chẵn (parity == 0) luôn đứng trước số có số lượng bit 1 lẻ (parity == 1).
  - Nếu parityA giống parityB (cả hai cùng chẵn hoặc cùng lẻ): Số nhỏ hơn đứng trước (sắp xếp tăng dần theo giá trị).
Cách triển khai:
- Đọc input vào một std::vector.
- Định nghĩa hàm so sánh tùy chỉnh dựa trên logic ở bước 3.
- Sử dụng std::sort với vector và hàm so sánh tùy chỉnh của bạn: std::sort(vec.begin(), vec.end(), custom_comparator);
- In kết quả từ vector đã sắp xếp.
Gợi ý về đếm bit 1:
- Cách đơn giản: Duyệt qua các bit của số bằng cách sử dụng phép toán & 1 và dịch phải >> 1.
- Cách hiệu quả (thường dùng trong competitive programming): Sử dụng __builtin_popcount(số) nếu dùng GCC/Clang.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.