Hiểu bài toán

Cho hai người chơi thay phiên nhau rút ngẫu nhiên các lá thăm từ hộp đen chứa N lá số từ 1 đến N. Mỗi lá tương ứng với một bài tập có điểm ai. Người chơi nào rút được lá đó sẽ được cộng điểm ai. Tí là người đi trước. Mục tiêu là tìm chênh lệch điểm tối đa giữa Tí và Sửu (điểm Tí - điểm Sửu). Tí muốn tối đa hóa chênh lệch này, trong khi Sửu muốn giảm nó. Vì cả hai đều có thể chọn lá thăm bất kỳ trong số các lá còn lại, chúng ta cần tìm cách phân chia các bài tập sao cho Tí được lấy số lượng bài nhiều hơn hoặc bằng Sửu (nếu N là số lẻ), và điểm số của Tí là lớn nhất có thể.

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

Cách Sắp xếp và Tính toán trực tiếp

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

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

    int N;
    cin >> N;
    vector<int> a(N);
    for (int &x : a) cin >> x;

    sort(a.begin(), a.end(), greater<int>());

    int k = (N + 1) / 2;  // số bài Tí lấy (điễn trước)
    int sumTi = 0, sumAll = 0;
    for (int i = 0; i < N; ++i) sumAll += a[i];
    for (int i = 0; i < k; ++i) sumTi += a[i];

    int diff = 2 * sumTi - sumAll;
    cout << diff;
}

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

Đây là cách tiếp cận trực tiếp và hiệu quả nhất.

1. Xét các trường hợp:
   • Nếu N chẵn: Tí và Sửu mỗi người rút N/2 lá. Tí muốn tổng điểm của N/2 lá lớn nhất, Sửu sẽ lấy số còn lại. Để chênh lệch lớn nhất, Tí phải lấy N/2 lá có điểm cao nhất. Khi đó, điểm Tí là tổng N số lớn nhất, điểm Sửu là tổng N số nhỏ nhất.
   • Nếu N lẻ: Tí đi trước và sẽ lấy nhiều hơn 1 lá so với Sửu. Cụ thể, Tí lấy (N+1)/2 lá, Sửu lấy N/2 lá. Tí vẫn nên ưu tiên lấy các lá có điểm cao nhất để tối đa hóa tổng điểm.
2. Thuật toán:
   • Sắp xếp mảng a theo thứ tự giảm dần.
   • Tính tổng điểm của k = (N+1)/2 lá đầu tiên (điểm cao nhất) gán cho Tí (sumTi).
   • Tính tổng tất cả các lá (sumAll).
   • Công thức chênh lệch: diff = sumTi - (sumAll - sumTi) = 2 * sumTi - sumAll.
3. Độ phức tạp: Sắp xếp mất O(N log N), các thao tác tính tổng mất O(N). Với N <= 50, cách này chạy rất nhanh.

Cách Đối xứng và Tính tổng

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x: a)
        cin >> x;
    sort(a.begin(), a.end());
    int sum = 0;
    for (int i = 0; i < n/2; i++){
        sum -= a[i];
    }
    for (int i = n/2; i < n; i++){
        sum += a[i];
    }
    cout << abs(sum);
}

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

Cách tiếp cận này dựa trên việc chia đôi mảng sau khi đã sắp xếp.

1. Sắp xếp mảng a theo thứ tự tăng dần.
2. Chia mảng thành 2 nửa:
   • Nửa đầu (các số nhỏ nhất).
   • Nửa sau (các số lớn nhất).
3. Logic: Nếu N chẵn, Tí lấy N/2 số lớn nhất (nửa sau), Sửu lấy N/2 số nhỏ nhất (nửa đầu). Chênh lệch là tổng nửa sau trừ đi tổng nửa đầu. Nếu N lẻ, Tí lấy (N+1)/2 số lớn nhất, Sửu lấy N/2 số nhỏ nhất. Do cách chia mảng n/2 (chia lấy sàn), nửa sau sẽ nhiều hơn nửa đầu 1 phần tử nếu N lẻ. Tí sẽ lấy hết nửa sau, Sửu lấy hết nửa đầu.
4. Công thức: sum = (Tổng nửa sau) - (Tổng nửa đầu). Kết quả in ra là abs(sum) để đảm bảo dương (dù logic đảm bảo sum >= 0). Lưu ý: Code mẫu tính sum bằng cách cộng các số lớn và trừ các số nhỏ.

Cách Quy hoạch động (Tối ưu hóa tổng)

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    int total = 0;
    for(int i=0; i<n; i++) {
        cin >> a[i];
        total += a[i];
    }

    // Đặt giới hạn trọng lượng là tổng điểm của 1/2 số bài (hoặc hơn)
    // Với N <= 50 và a_i <= 50, tổng điểm tối đa là 2500.
    int limit = total / 2 + 50;
    vector<bool> dp(limit + 1, false);
    dp[0] = true;

    for(int x : a) {
        for(int j = limit; j >= x; j--) {
            if(dp[j - x]) dp[j] = true;
        }
    }

    int maxTi = 0;
    // Tí lấy k = (N+1)/2 bài
    int k = (n + 1) / 2;

    // Tìm tổng điểm lớn nhất có thể tạo thành từ k số
    // Đây là bài toán 'Partition Problem' biến thể, nhưng N nhỏ nên có thể dùng Bitset hoặc DP.
    // Tuy nhiên, giải pháp DP ở trên là Subset Sum (tìm tổng có thể tạo được), chưa phân biệt được số lượng phần tử.
    // Để phân biệt số lượng, cần DP 2 chiều: dp[i][j] = có thể tạo tổng j bằng i phần tử không.

    // Code dưới đây minh họa cho DP 2 chiều:
    int max_sum = total;
    vector<vector<bool>> dp2(k + 1, vector<bool>(max_sum + 1, false));
    dp2[0][0] = true;
    for (int x : a) {
        for (int i = k; i >= 1; i--) {
            for (int j = max_sum; j >= x; j--) {
                if (dp2[i-1][j-x]) dp2[i][j] = true;
            }
        }
    }

    int best = 0;
    for (int j = max_sum; j >= 0; j--) {
        if (dp2[k][j]) {
            best = j;
            break;
        }
    }
    cout << 2 * best - total;
}

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

Đây là cách giải tổng quát hơn cho bài toán chia đôi tập hợp.

1. Bài toán có thể coi là: Chọn k = (N+1)/2 phần tử sao cho tổng của chúng lớn nhất.
2. Sử dụng quy hoạch động 2 chiều: dp[i][j] = true nếu có thể chọn i phần tử để tạo tổng j.
3. Quy luật: Duyệt qua từng số x trong mảng a. Cập nhật dp[i][j] từ dp[i-1][j-x]. Duyệt ngược i và j để tránh dùng lại phần tử.
4. Sau khi tính xong bảng DP, duyệt từ tổng lớn nhất giảm dần đến 0, tìm tổng j đầu tiên mà dp[k][j] bằng true.
5. Chênh lệch là 2*j - total. Cách này có độ phức tạp cao hơn so với sắp xếp nhưng là cách giải chuẩn cho các bài toán tương tự khi dữ liệu lớn hơn (tuy nhiên với N=50 thì sắp xếp nhanh hơn và đơn giản hơn).

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

Bài học kinh nghiệm

• Người đi trước (Tí) có lợi thế về số lượng bài được chọn (nếu N lẻ) và quyền ưu tiên chọn bài có điểm cao nhất. Do đó, chiến lược tối ưu cho Tí là luôn chọn các bài có điểm cao nhất.
• Bài toán này về bản chất là tìm cách chia tập hợp các số thành 2 tập con sao cho chênh lệch tổng của chúng lớn nhất, với ràng buộc về số lượng phần tử mỗi tập.
• Nếu sắp xếp giảm dần, Tí lấy k phần tử đầu tiên, Sửu lấy phần còn lại. Chênh lệch tối đa = 2 * (tổng k phần tử đầu) - (tổng tất cả).

Lỗi thường gặp

• Lầm tưởng rằng Tí và Sửu bốc hoàn toàn ngẫu nhiên: Đề bài yêu cầu tìm chênh lệch tối đa, ngụ ý rằng cả hai đều chơi optimal (Tí muốn thắng đậm, Sửu muốn tránh thua đậm). Do đó ta phải giả định Tí luôn chọn lá tốt nhất.
• Sai lệch trong việc tính số lượng lá Tí được lấy: Nếu N chẵn, Tí lấy N/2; nếu N lẻ, Tí lấy (N+1)/2. Lầm tưởng cả hai luôn lấy N/2 sẽ sai đáp án khi N lẻ.
• Trong cách giải quy hoạch động, nếu chỉ dùng 1 chiều (Subset Sum) mà không kiểm soát số lượng phần tử, ta chỉ biết tổng có thể đạt được chứ không biết tổng đó tạo thành từ bao nhiêu số. Phải dùng DP 2 chiều (số lượng - tổng) để giải quyết đúng bài toán này.