Hiểu bài toán

Bài toán yêu cầu tìm số điểm tối đa mà Goku có thể đạt được khi so bài với Goten. Có tổng cộng 2N lá bài được đánh số từ 1 đến 2N. Goten sở hữu N lá bài cụ thể (được cho trước), Goku sở hữu N lá bài còn lại. Trong mỗi lượt chơi, cả hai người cùng đưa ra một lá bài, lá nào có giá trị lớn hơn sẽ giành được 1 điểm. Goten chơi theo đúng trình tự các lá bài đã cho (theo thứ tự nhập vào).

Mục tiêu: Xếp lá bài của Goku sao cho số lượt Goku thắng (lá bài của Goku > lá bài của Goten) là nhiều nhất có thể.

Giả sử Goten chơi các lá bài theo thứ tự: $A1, A2, ..., AN$. Goku cần chọn thứ tự các lá bài $B1, B2, ..., BN$ (trong bộ bài còn lại) để tối đa hóa số lượng chỉ số $i$ sao cho $Bi > Ai$.

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

Cách Quy hoạch động (Dynamic Programming)

// Ví dụ code cho Quy hoạch động (Chỉ dùng cho N nhỏ)
// Với N=50000, code này không chạy đúng thời gian.
// Tuy nhiên, logic Greedy là tối ưu.

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

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

    vector<int> b;
    vector<bool> used(2*n+1, false);
    for(int x : a) used[x] = true;
    for(int i=1; i<=2*n; i++) if(!used[i]) b.push_back(i);

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    int ans = 0;
    int i = 0, j = 0;
    while(i < n && j < n) {
        if(b[j] > a[i]) {
            ans++;
            i++;
            j++;
        } else {
            j++;
        }
    }
    cout << ans;
    return 0;
}

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

Giả sử ta muốn dùng DP. Trạng thái có thể là: đang xét lá bài thứ i của Goten, và ta đã dùng k lá bài của Goku. Tuy nhiên, để biết nước đi tiếp theo có thắng hay không, ta cần biết giá trị lá bài của Goku. Do đó DP khó áp dụng trực tiếp.

Một cách tiếp cận DP khác (thường dùng cho bài toán tương tự nhưng quy mô nhỏ): Sắp xếp bài của Goten và Goku. Dùng DP[i][j] là số điểm tối đa khi xét i lá Goten và j lá Goku.

Tuy nhiên, với N lên tới 50,000, giải pháp O(N^2) chắc chắn bị TLE. Code mẫu trong giải pháp 3 có vẻ là một dạng tối ưu hóa của DP hoặc Greedy.

Giải pháp 3 thực chất là biến thể của thuật toán chuẩn xác: Sắp xếp cả hai mảng và dùng 2 con trỏ (hoặc 1 con trỏ cho Goten, 1 cho Goku).

Phân tích chi tiết Approach 3 (thanhbtm1):

• Đánh dấu bài của Goten.
• Tạo mảng b chứa bài của Goku.
• Sắp xếp a (bài Goten) và b (bài Goku).
• Dùng 2 chỉ số ia (điểm từ cuối mảng a) và ib (điểm từ cuối mảng b).
• Logic: Nếu bài lớn nhất của Goku (b[ib]) nhỏ hơn bài lớn nhất của Goten (a[ia]), thì không thể thắng lá a[ia] bằng lá bài lớn nhất hiện có, nên ta ‘hy sinh’ lá b[ib] này cho các lá bài nhỏ hơn của Goten (dù không thắng, hoặc để dành). Ta chuyển sang lá b[ib-1].
• Nếu b[ib] >= a[ia], ta có thể dùng lá b[ib] để thắng a[ia] (hoặc các lá lớn hơn của Goten). Logic này hơi khác với cách tiếp cận Greedy chuẩn.

Greedy Chuẩn (Giải thích trong Approach 2):

• Sắp xếp bài của Goten theo thứ tự xuất hiện (hoặc bất kỳ thứ tự nào nếu ta chỉ cần tối đa hóa số trận thắng).
• Sắp xếp bài của Goku tăng dần.
• Dùng 2 con trỏ: Duyệt qua từng lá bài của Goten (từ lá nhỏ nhất đến lớn nhất), cố tìm lá bài của Goku nhỏ nhất nhưng vẫn lớn hơn lá bài của Goten. Nếu tìm thấy, ta dùng nó và cộng điểm.

Rationale: Việc dùng lá bài của Goku nhỏ nhất có thể để thắng giúp giữ lại các lá bài lớn cho các lá bài lớn hơn của Goten sau này.

Cách Greedy với Multiset (Tối ưu)

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

Đây là cách tiếp cận trực quan nhất và cũng là lời giải chuẩn xác cho bài toán này.

1. Chuẩn bị dữ liệu:

   • Đọc N và các lá bài của Goten.
   • Tạo một tập hợp (set hoặc multiset) chứa các lá bài của Goku. Ta có thể tạo một mảng boolean hoặc mảng đánh dấu để xác định lá bài nào thuộc về Goten, sau đó thêm các lá còn lại vào goku_set.

2. Thuật toán:

   • Duyệt qua các lá bài của Goten theo thứ tự nhập vào (hoặc có thể sắp xếp tăng dần).
   • Với mỗi lá bài của Goten có giá trị x, ta cần tìm trong tập bài của Goku một lá bài có giá trị lớn nhất nhưng vẫn nhỏ hơn x (nếu muốn tối đa hóa số điểm và cách tiếp cận khác) hoặc nhỏ nhất nhưng lớn hơn x.
   • Phân tích: Để tối đa hóa tổng số điểm, ta nên dùng lá bài của Goku 'vừa đủ' để thắng lá bài của Goten.
   • Cụ thể: Khi Goten ra lá x, ta nên dùng lá bài của Goku có giá trị nhỏ nhất nhưng vẫn lớn hơn x. Nếu dùng lá lớn hơn cần thiết, ta sẽ làm lãng phí lá bài mạnh đó cho các lượt sau (khi Goten ra lá lớn hơn).

3. Thực thi:

   • Sử dụng std::set (hoặc std::multiset) cho bài của Goku để có thể tìm kiếm và xóa phần tử hiệu quả.
   • Duyệt từng lá x của Goten:
     • Tìm iterator tới phần tử đầu tiên trong goku_set lớn hơn x bằng hàm upper_bound(x).
     • Nếu tìm thấy (it != goku_set.end()), tăng điểm và xóa phần tử đó khỏi tập.
     • Nếu không tìm thấy, ta không thể thắng lượt này.

Độ phức tạp: O(N log N) do thao tác với set.

Cách Hai con trỏ (Two Pointers)

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

Phương pháp này dựa trên việc sắp xếp lại cả hai tập hợp bài.

1. Sắp xếp:

   • Sắp xếp bài của Goten theo thứ tự tăng dần.
   • Sắp xếp bài của Goku theo thứ tự tăng dần.

2. Logic Hai Con Trỏ:

   • Ta dùng hai chỉ số i và j để duyệt qua mảng goten và goku.
   • Nếu goku[j] > goten[i]: Ta có thể dùng lá bài goku[j] để thắng lá goten[i]. Ta cộng điểm và tăng cả i và j lên 1.
   • Nếu goku[j] <= goten[i]: Lá bài goku[j] quá nhỏ để thắng goten[i]. Trong trường hợp này, lá bài goku[j] này không thể thắng bất kỳ lá bài nào từ goten[i] trở đi (vì mảng goten được sắp xếp tăng dần). Do đó, ta loại bỏ lá goku[j] này và tăng j lên 1.

3. Tại sao hiệu quả?

   • Bằng cách sắp xếp, ta đảm bảo rằng khi ta tìm thấy một cặp thắng cuộc, ta đang sử dụng lá bài của Goku nhỏ nhất có thể để đánh bại lá bài nhỏ nhất còn lại của Goten. Điều này tối đa hóa cơ hội thắng cho các lượt sau.

Độ phức tạp: O(N log N) cho việc sắp xếp + O(N) cho việc duyệt.

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

Bài học kinh nghiệm

• Bài toán có thể được coi là biến thể của bài toán 'Matching' trong lý thuyết trò chơi: Ghép từng lá bài của Goten với một lá bài của Goku sao cho số cặp thỏa mãn điều kiện (Goku > Goten) là lớn nhất.
• Giải thuật Greedy là tối ưu: Luôn cố gắng thắng lá bài của Goten bằng lá bài của Goku nhỏ nhất có thể (vừa đủ lớn).
• Việc sắp xếp lại các lá bài của Goten không làm thay đổi kết quả cuối cùng (số điểm tối đa), vì ta có thể tự do lựa chọn lá bài của Goku cho mỗi lượt chơi, không phụ thuộc vào việc Goten chơi lá đó ở lượt thứ nhất hay thứ N.
• Sử dụng cấu trúc dữ liệu std::set với hàm upper_bound là cách hiện thực hóa Greedy đơn giản nhất.

Lỗi thường gặp

• Độ phức tạp O(N^2): Nếu không sử dụng cấu trúc dữ liệu hiệu quả (Set) hoặc thuật toán hai con trỏ sau khi sắp xếp, mà thay vào đó duyệt tìm kiếm tuyến tính, bạn sẽ gặp Time Limit Exceeded với N=50000.
• Quên sắp xếp hoặc xử lý sai thứ tự: Nếu bạn không sắp xếp lại bài của Goten và Goku (trong phương pháp hai con trỏ), thuật toán hai con trỏ sẽ không hoạt động đúng.
• Lỗi truy cập mảng: Khi tạo mảng đánh dấu bài của Goten, cần mảng size 2*N + 1 để tránh tràn mảng (vì bài có giá trị tới 2N).
• Sử dụng lower_bound thay vì upper_bound: Nếu dùng lower_bound(x), bạn có thể chọn chính xác lá bài bằng x (nếu có, nhưng trong bài này bài không bị trùng). Tuy nhiên, logic upper_bound(x) tìm lá bài đầu tiên lớn hơn x là chính xác nhất cho điều kiện 'lớn hơn'.