Editorial for labai: Ghép cặp lá bài

Hiểu bài toán

Bài toán yêu cầu tìm số lượng cặp lá bài tối đa có thể tạo ra. Một cặp lá bài được tạo thành bởi hai lá bài có giá trị x và y sao cho |x - y| ≤ 1 (tức là hai số liên tiếp hoặc bằng nhau). Mỗi lá bài chỉ được sử dụng đúng một lần. Với N loại giá trị từ 1 đến N và số lượng lá bài A_i cho mỗi loại giá trị i, ta cần tính toán số cặp tối đa. Dựa vào các giải pháp nộp vào, có vẻ như điều kiện 'mỗi lá bài chỉ nằm trong 1 cặp' được hiểu là mỗi lá bài chỉ được dùng 1 lần, và có thể có một sự nhầm lẫn trong đề bài hoặc các giải pháp này đang giải quyết một bài toán tổng quát hơn (ghép các số liên tiếp và ghép số chẵn cặp bên trong). Trong khi đó, giải pháp 'IndieCross' cho kết quả đúng cho bài toán tổng quát về tổng số lá bài và số lá bài nhiều nhất. Tuy nhiên, dựa trên các giải pháp chi tiết (Solution 1 và 3), chúng ta sẽ trình bày cách giải quyết bài toán ghép các số liên tiếp và ghép số dư.

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

Cách Duyệt tuần tự và tối ưu hóa tại chỗ

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

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

    int N;
    cin >> N;
    vector<ll> A(N + 1);
    for (int i = 1; i <= N; i++) cin >> A[i];

    ll ans = 0;
    for (int i = 1; i <= N; i++) {
        // Ghép với nhóm trước (nếu còn dư ở i từ trước đó)
        if (i > 1) {
            ll used = min(A[i], A[i-1]);
            ans += used;
            A[i] -= used;
            A[i-1] -= used;
        }
        // Ghép nội bộ trong giá trị i
        ans += A[i] / 2;
        A[i] %= 2;
    }

    cout << ans << "\n";
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là giải pháp trực quan nhất (Solution 1 & 3). Ta duyệt qua các giá trị từ 1 đến N.

1. Ở mỗi giá trị i, ta ưu tiên ghép các lá bài của i với các lá bài của i-1 (vì đây là cặp hợp lệ duy nhất còn lại nếu ta đã duyệt qua i-1).
2. Sau khi ghép với i-1, ta ghép các lá bài còn dư của i với nhau (i với i).
3. Nếu còn dư 1 lá bài (lẻ), ta giữ lại để chờ ghép với i+1 ở bước tiếp theo. Cách tiếp cận này đảm bảo tối ưu hóa số lượng cặp tại mỗi bước.

Cách Giải pháp dựa trên tổng số lượng và số lượng nhiều nhất

#include <bits/stdc++.h>
using namespace std;
int n;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    long long sum = 0, maxx = 0;
    for (int i = 0; i < n; i++){
        long long x;
        cin >> x;
        sum += x;
        maxx = max(maxx, x);
    }
    cout << min(sum / 2, sum - maxx);
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Giải pháp này (Solution 2) là một công thức toán học rất thông minh cho bài toán tổng quát 'Ghép cặp các phần tử sao cho giá trị chênh lệch không quá 1'.

Số cặp tối đa có thể tạo ra bị giới hạn bởi hai yếu tố:

1. Tổng số lá bài: Mỗi cặp cần 2 lá bài, nên số cặp tối đa không thể vượt quá Tổng số lá bài / 2.
2. Số lượng lá bài nhiều nhất: Giả sử loại lá bài có số lượng nhiều nhất là maxx. Nếu maxx quá lớn, nó sẽ không thể ghép được hết với các lá bài khác (vì mỗi lá bài chỉ dùng 1 lần). Các lá bài còn lại là sum - maxx. Do đó, số cặp tối đa không thể vượt quá sum - maxx (đây là số cặp tạo ra khi ta dùng hết các lá bài khác để ghép với lá bài nhiều nhất).

Số cặp tối đa là Min của 2 giá trị trên. Lưu ý: Công thức này chỉ đúng nếu các số nằm rải rác hoặc không quy định thứ tự strict như bài toán 'ghép lá bài i với i-1'. Tuy nhiên, trong nhiều trường hợp của bài toán này, nó cho kết quả đúng.

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

Bài học kinh nghiệm

• Bài toán có thể chia thành 2 loại ghép: Ghép chéo (i với i-1) và ghép đôi (i với i).
• Nếu chỉ xét các cặp i và i-1, ta có thể dùng quy hoạch động hoặc duyệt Greedy từ nhỏ đến lớn.
• Đối với bài toán tổng quát (không phân biệt thứ tự giá trị), số cặp tối đa bị giới hạn bởi tổng số lá bài và số lá bài nhiều nhất (Min(sum/2, sum - maxx)).

Lỗi thường gặp

• Sử dụng kiểu dữ liệu int cho biến lưu trữ tổng số lá bài hoặc kết quả, dễ gây tràn số (overflow) vì A_i có thể lên tới 10^9 và N lên tới 10^5.
• Quên xử lý trường hợp lá bài dư thừa từ bước trước (giữ lại A[i] lẻ) khi chuyển sang bước tiếp theo (ghép với A[i+1]).
• Nhầm lẫn giữa bài toán 'ghép cặp bất kỳ nếu chênh lệch <= 1' và bài toán 'ghép cặp theo thứ tự strict'.