Editorial for blscales: Cân đĩa thăng bằng

Hiểu bài toán

Bài toán yêu cầu xác định xem mỗi mặt hàng trong số m mặt hàng có thể được cân bằng bằng cách đặt một số quả cân (từ n quả cân cho trước) lên đĩa đối diện hay không. Nói cách khác, với mỗi khối lượng vi của mặt hàng, ta cần kiểm tra xem có cách chọn một tập con các quả cân sao cho tổng khối lượng của chúng bằng vi hay không. Đây về cơ bản là bài toán cái túi (Knapsack) hoặc bài toán tập con có tổng bằng S (Subset Sum Problem) với n phần tử nhỏ (n ≤ 20) nhưng cần xử lý nhiều truy vấn (m ≤ 10^5).

Các cách tiếp cận

Cách Quay lui (Backtracking/DFS)

#include <iostream>
#include <vector>
using namespace std;

int n, m;
vector<int> w;
bool found;

void dfs(int index, int currentSum, int target) {
    if (found) return;
    if (currentSum == target) {
        found = true;
        return;
    }
    if (index == n || currentSum > target) return;

    // Thử chọn quả cân thứ index
    dfs(index + 1, currentSum + w[index], target);
    // Thử không chọn quả cân thứ index
    dfs(index + 1, currentSum, target);
}

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

    cin >> n >> m;
    w.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }

    string result = "";
    for (int i = 0; i < m; i++) {
        int target;
        cin >> target;
        found = false;
        dfs(0, 0, target);
        result += (found ? '1' : '0');
    }
    cout << result;

    return 0;
}

• Time Complexity: O(m * 2^n)
• Space Complexity: O(n)

Cách tiếp cận này sử dụng đệ quy (quay lui) để duyệt qua tất cả các khả năng chọn hoặc không chọn từng quả cân. Với mỗi mặt hàng, ta chạy một lần DFS để kiểm tra xem có thể tạo ra tổng bằng khối lượng mặt hàng đó hay không. Vì n ≤ 20, số lượng tập con là 2^20 ≈ 10^6. Với m truy vấn, độ phức tạp tổng cộng lên tới khoảng 10^6 * 10^5 = 10^11, quá lớn để chạy trong thời gian giới hạn. Tuy nhiên, đây là cách tiếp cận trực quan nhất.

Cách Duyệt tất cả tập con (Generate All Subsets)

#include <stdio.h>
#include <stdlib.h>

int comp(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

void solve() {
    int n, m;
    scanf("%d %d", &n, &m);

    int *weights = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &weights[i]);
    }

    int maskSize = 1 << n;
    int *weightCombs = malloc(maskSize * sizeof(int));
    for (int mask = 0; mask < maskSize; mask++) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (mask >> i & 1) {
                sum += weights[i];
            }
        }
        weightCombs[mask] = sum;
    }
    qsort(weightCombs, maskSize, sizeof(int), comp);

    for (int i = 0; i < m; i++) {
        int weight;
        scanf("%d", &weight);

        int lo = 0, hi = maskSize - 1;
        int found = 0;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (weightCombs[mid] == weight) {
                found = 1;
                break;
            } else if (weightCombs[mid] < weight) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        printf("%d", found);
    }
}

int main() {
    solve();
    return 0;
}

• Time Complexity: O(2^n + m * log(2^n)) = O(2^n + m * n)
• Space Complexity: O(2^n)

Phương pháp này tạo ra tất cả các tổng có thể có của các tập con các quả cân. Có tổng cộng 2^n tập con (với n=20, là 1048576). Ta tính tổng khối lượng cho từng tập con và lưu vào mảng weightCombs. Sau đó, sắp xếp mảng này. Với mỗi truy vấn, ta sử dụng tìm kiếm nhị phân (Binary Search) để kiểm tra xem khối lượng cần tìm có tồn tại trong mảng các tổng đã tính sẵn hay không. Độ phức tạp là O(2^n) để tạo các tổng và O(m * log(2^n)) cho các truy vấn, tổng thể nhanh hơn nhiều so với quay lui cho nhiều truy vấn.

Cách Dynamic Programming (Bitset)

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

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

    int n, m;
    cin >> n >> m;
    vector<int> w(n);

    int sumW = 0;
    for (int i = 0; i < n; i++) {
        cin >> w[i];
        sumW += w[i];
    }

    // Sử dụng bitset để đánh dấu các tổng có thể đạt được
    // Kích thước tối đa là tổng của tất cả các quả cân (n * max_w_i)
    // Bài toán giới hạn w_i <= 10^6, n <= 20 nên tổng tối đa là 2*10^7.
    // Tuy nhiên, test data có thể nhỏ hơn. Nếu tổng quá lớn, ta có thể dùng mảng bool hoặc map.
    // Bitset tối ưu về mặt thời gian và bộ nhớ.
    bitset<20000005> dp;
    dp[0] = 1;

    for (int x : w) {
        dp |= (dp << x);
    }

    for (int i = 0; i < m; i++) {
        int a;
        cin >> a;
        // Kiểm tra xem tổng a có nằm trong giới hạn và có thể đạt được không
        if (a <= sumW && dp[a])
            cout << "1";
        else
            cout << "0";
    }
    return 0;
}

• Time Complexity: O(n * sumW / 64)
• Space Complexity: O(sumW / 64)

Đây là cách tối ưu nhất cho bài toán này. Ta dùng một mảng bit (bitset) để đánh dấu các tổng có thể tạo được. dp[i] = 1 nghĩa là tổng i có thể tạo được. Ban đầu, chỉ tổng 0 là có thể tạo được. Với mỗi quả cân có khối lượng x, ta cập nhật mảng bit bằng cách dịch trái mảng bit hiện tại đi x bit và kết hợp (OR) với mảng ban đầu. Thao tác dp |= (dp << x) thực hiện việc này rất nhanh (tốc độ bitset). Sau khi xử lý hết các quả cân, ta chỉ cần kiểm tra bit tương ứng với khối lượng của mỗi mặt hàng. Độ phức tạp thời gian phụ thuộc vào tổng khối lượng tối đa, nhưng với bitset, các phép toán bit diễn ra rất nhanh.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán là biến thể của bài toán 'Tìm tập con có tổng bằng S' (Subset Sum Problem). Với n nhỏ (≤20) nhưng m lớn (≤10^5), ta cần tính toán các tổng có thể một lần và trả lời truy vấn nhanh.
• Phương pháp Dynamic Programming sử dụng Bitset là hiệu quả nhất về mặt thời gian thực thi trong C++ do tối ưu hóa phần cứng (bit operations).

Lỗi thường gặp

• Quên xử lý trường hợp tổng khối lượng của các quả cân nhỏ hơn khối lượng mặt hàng, dẫn đến lỗi logic hoặc truy cập ngoài vùng nhớ.
• Sử dụng đệ quy/quay lui cho m lớn sẽ gây ra Time Limit Exceeded do độ phức tạp quá cao.
• Khởi tạo mảng DP hoặc Bitset không đủ kích thước (ví dụ: tổng của các quả cân có thể lên tới 20 triệu).