Hiểu bài toán

Cho một dãy nhị phân gồm các số 0 và 1. Bạn được thực hiện một phép biến đổi: chọn một đoạn con liên tiếp và hoán vị các phần tử trong đoạn đó (tức là bạn có thể sắp xếp lại các số 0 và 1 trong một đoạn con bất kỳ). Mục tiêu là sau một lần biến đổi như vậy, dãy kết quả có số lượng số 1 liên tiếp nhiều nhất có thể (đoạn dài nhất toàn 1). Hãy tìm độ dài tối đa của đoạn con toàn 1 này.

Phân tích chi tiết:

• Chúng ta có thể hoán vị một đoạn con bất kỳ.
• Việc hoán vị cho phép chúng ta tập hợp tất cả các số 1 trong đoạn đó về một phía và các số 0 về một phía.
• Vấn đề trở thành: chọn một đoạn con sao cho khi dồn các số 1 lại, đoạn con đó 'kết nối' được với các số 1 bên ngoài để tạo thành một đoạn toàn 1 dài nhất.
• Gọi base là số lượng 1 có sẵn trong dãy.
• Nếu ta chọn một đoạn con có c0 số 0 và c1 số 1, sau khi hoán vị, ta có thể có một đoạn toàn 1 độ dài c1.
• Đoạn này có thể nối với các đoạn 1 bên ngoài nếu đoạn con được chọn nằm giữa các đoạn 1 đó hoặc bao trùm một phần gap.
• Thực tế, phép biến đổi này cho phép ta 'mua' các số 0 từ một đoạn con để đổi lấy sự tập trung các số 1. Câu hỏi là đoạn nào cho phép ta có độ dài đoạn 1 lớn nhất.

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

Cách Kadane's Algorithm (Biến đổi)

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

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

    freopen("bitseq.inp", "r", stdin);
    freopen("bitseq.out", "w", stdout);

    int n;
    cin >> n;

    vector<int> a(n);
    int ones = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] == 1) ones++;
    }

    // Biến đổi: 0 -> 1 (tốt), 1 -> -1 (xấu vì làm mất 1 từ 'base')
    // Nếu ta chọn một đoạn, ta mất các số 1 có sẵn trong đó (để sắp xếp lại)
    // Nhưng ta được 'tái sử dụng' chúng. 
    // Logic: base là số 1 toàn cục. Nếu ta chọn một đoạn con, ta muốn tối ưu hóa số lượng 1 trong đoạn đó + số 1 ngoài đoạn đó.
    // Số 1 ngoài đoạn đó là base - (số 1 trong đoạn).
    // Nếu ta sắp xếp lại đoạn con, ta có thể tạo ra một đoạn toàn 1 độ dài (số 1 trong đoạn).
    // Nhưng để đoạn này nối dài được, nó phải nằm cạnh các đoạn 1 khác.
    // Công thức chung cho bài này (thường thấy):
    // Kết quả = base + max_subarray_sum(b)
    // Trong đó b[i] = 1 nếu a[i] == 0, b[i] = -1 nếu a[i] == 1.
    // Ý nghĩa: Việc chọn một đoạn con để tối ưu hóa là một sự đánh đổi. 
    // Nếu thêm 0 vào đoạn con, ta được +1 độ dài (vì 0 có thể biến thành 1).
    // Nếu thêm 1 vào đoạn con, ta mất -1 (vì 1 đó đã được tính trong base, khi ta sắp xếp lại đoạn con, 1 đó không còn nằm ở vị trí tự nhiên để nối dài thêm bên ngoài, nó bị 'nhào lộn' vào trong).
    // Tuy nhiên, cách giải thích khác chuẩn hơn:
    // Bài này là tìm max (số 1 trong đoạn con được chọn + số 1 bên ngoài).
    // Số 1 bên ngoài = base - (số 1 trong đoạn).
    // Nếu ta chọn một đoạn con và hoán vị nó, ta có thể dồn tất cả 1 về một bên. 
    // Giả sử ta muốn đoạn 1 nằm ở cuối đoạn con được chọn. 
    // Đoạn 1 này có thể nối với đoạn 1 nằm ngay sau đoạn con (nếu có).
    // Hoặc nó có thể nối với đoạn 1 nằm ngay trước.
    // Nhưng phép biến đổi cho phép ta chọn đoạn con, hoán vị, và sau đó xem độ dài dãy 1 dài nhất.
    // Gọi đoạn con được chọn là [l, r].
    // Số 1 trong đoạn là c1. Số 0 trong đoạn là c0.
    // Sau hoán vị, ta có thể có đoạn 1 độ dài c1 ở cuối [l, r].
    // Nếu sau [l, r] có sẵn đoạn 1, ta nối được.
    // Nếu trước [l, r] có sẵn đoạn 1, ta có thể hoán vị sao cho 1 nằm ở đầu [l, r] để nối.
    // Tuy nhiên, chỉ được hoán vị 1 lần duy nhất, chọn 1 đoạn con duy nhất.
    // Câu trả lời đúng nhất cho bài này (theo các solution):
    // Dùng Kadane với mảng b, b[i] = 1 nếu a[i]=0, b[i]=-1 nếu a[i]=1.
    // Kết quả = base + max(0, max_subarray_sum(b)).
    // 
    // Code Kadane:
    int best = -1e9, cur = 0;
    for (int x : a) {
        int val = (x == 0 ? 1 : -1);
        cur = max(val, cur + val);
        best = max(best, cur);
    }
    // Trường hợp không chọn đoạn nào (hoặc đoạn không tốt) thì giá trị là 0.
    // Nếu all 1s, best = -n, base = n. Result = n + (-1) ? Không, all 1scase handled separately?
    // Solution 2: cout << ones + best. 
    // Nếu all 1s: ones = n. b[i] = -1. best = -1. Result = n - 1. (Đúng, vì ta phải chọn 1 đoạn để hoán vị, làm nó không còn toàn 1 nếu n > 0).
    // Nếu có 0: best >= 0.
    cout << ones + best;
}

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

Đây là cách tiếp cận tối ưu sử dụng thuật toán Kadane.

1. Biến đổi bài toán: Gọi base là số lượng số 1 có sẵn trong dãy. Khi ta chọn một đoạn con bất kỳ để hoán vị, ta đang thực hiện một sự đánh đổi:

   • Nếu trong đoạn con đó có số 0, ta có thể đưa nó vào vị trí cần thiết để tăng độ dài dãy 1 (đánh dấu +1).
   • Nếu trong đoạn con đó có số 1, số 1 đó bị di chuyển ra khỏi vị trí tự nhiên của nó, có thể làm gián đoạn dãy 1 hiện có hoặc không giúp ích trực tiếp cho việc nối dài thêm các đoạn 1 bên ngoài (đánh dấu -1).

2. Tạo mảng giá trị: Tạo một mảng mới b mà ở đó:

   • b[i] = 1 nếu a[i] = 0 (vì 0 là tài nguyên để tạo ra 1).
   • b[i] = -1 nếu a[i] = 1 (vì 1 là tài nguyên đã được tính trong base, việc chọn nó vào đoạn hoán vị có thể coi là chi phí).

3. Tìm đoạn con tối ưu: Sử dụng Kadane để tìm đoạn con liên tiếp có tổng lớn nhất trong b. Gọi giá trị này là max_gain.

   • Nếu max_gain dương, nghĩa là việc hoán vị đoạn con này mang lại lợi ích ròng (tăng độ dài dãy 1).
   • Nếu max_gain âm hoặc âm, ta có thể không chọn đoạn con nào (hoặc chọn đoạn không ảnh hưởng).

4. Kết quả: Độ dài dãy 1 tối đa = base + max_gain.

   • Solution 2 đã triển khai chính xác logic này.
   • Solution 1 có vẻ làm tương tự nhưng biến đổi slightly khác: nó đếm res (số 1) và dùng Kadane tìm đoạn toàn 0 dài nhất (hoặc đoạn mà cnt0 > cnt1). Thực chất cnt trong Solution 1 là cnt0 - cnt1 của đoạn hiện tại. Nó tìm max cnt. Và công thức cuối res + ans tương đương base + max_gain.

Cách Sliding Window (Two Pointers)

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    freopen("bitseq.inp", "r", stdin);
    freopen("bitseq.out", "w", stdout);

    int N;
    cin >> N;
    vector<int> a(N);
    int base = 0;
    for(int i = 0; i < N; i++) {
        cin >> a[i];
        base += a[i];
    }

    int ans = base; // Trường hợp không hoán vị hoặc hoán vị không cải thiện
    int cnt[2] = {0, 0}; // cnt[0] là số 0, cnt[1] là số 1 trong window
    int j = 0;

    for(int i = 0; i < N; i++){
        cnt[a[i]]++;

        // Window [j, i]
        // Điều kiện window hợp lệ: cnt[1] <= cnt[0]
        // Tại sao? Nếu ta muốn tối ưu hóa, ta cần số 0 >= số 1 trong đoạn hoán vị.
        // Nếu cnt[1] > cnt[0], đoạn này 'lỗ' (bị âm gain).
        // Tuy nhiên, logic chính xác của Solution 3 là:
        // Duy trì window sao cho số 0 >= số 1.
        // Nếu cnt[1] > cnt[0], ta co hẹp window từ bên trái.

        while(cnt[1] > cnt[0]){
            cnt[a[j]]--;
            j++;
        }

        // Gain = cnt[0] - cnt[1]
        // Kết quả = base + Gain
        ans = max(ans, base + cnt[0] - cnt[1]);
    }
    cout << ans;
}

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

Cách tiếp cận này sử dụng kỹ thuật Sliding Window (hai con trỏ) để tối ưu hóa.

1. Logic Window: Ta cần tìm một đoạn con sao cho hiệu lệch giữa số 0 và số 1 là lớn nhất, nhưng có giới hạn.

   • Nếu một đoạn con có nhiều 0 hơn 1, nó có thể được dùng để tăng độ dài dãy 1.
   • Nếu một đoạn con có nhiều 1 hơn 0, nó không có lợi ích.

2. Thu hẹp Window: Duyệt qua mảng bằng con trỏ i. Duy trì một cửa sổ [j, i].

   • Nếu trong cửa sổ hiện tại, cnt[1] > cnt[0] (số 1 nhiều hơn số 0), ta thu hẹp cửa sổ từ bên trái (tăng j) cho đến khi điều kiện cnt[1] <= cnt[0] thỏa mãn.

3. Cập nhật kết quả: Với mỗi cửa sổ hợp lệ, tính giá trị gain = cnt[0] - cnt[1]. Cập nhật ans = max(ans, base + gain).

4. So sánh với Kadane: Sliding window này tìm đoạn con có (số 0) - (số 1) lớn nhất một cách có điều kiện (luôn đảm bảo dương hoặc 0). Trong khi Kadane tìm max subarray sum tự do (có thể âm, nhưng ta max với 0). Về bản chất, cả hai đều giải quyết được bài toán.

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

Bài học kinh nghiệm

• Phép biến đổi cho phép hoán vị một đoạn con, về cơ bản cho phép ta chọn một đoạn con và 'tái phân phối' các số 1 trong đoạn đó. Điều này có nghĩa là ta có thể tập hợp các số 1 lại với nhau trong đoạn đó.
• Bài toán có thể giảm xuống thành bài toán tìm đoạn con liên tiếp tối ưu trong một mảng phụ, nơi số 0 được coi là +1 (nguồn lực để tăng độ dài) và số 1 được coi là -1 (chi phí để di chuyển). Tổng giá trị này cộng với số lượng 1 ban đầu cho kết quả cuối cùng.
• Một cách tương đương, bài toán là tìm đoạn con sao cho số 0 trong đoạn trừ đi số 1 trong đoạn là lớn nhất không âm, và cộng thêm số 1 ban đầu của toàn dãy.

Lỗi thường gặp

• Xử lý sai trường hợp toàn bộ dãy là 1. Nếu dãy toàn 1, ta vẫn phải chọn một đoạn con để hoán vị (dù đoạn đó không thay đổi gì), nhưng kết quả phải là n - 1 (vì ta không thể có dãy dài hơn n và việc hoán vị làm gián đoạn tính liên tục nếu n > 0). Các solution thường xử lý đúng do logic -1 của thuật toán Kadane.
• Quên cộng với số lượng 1 ban đầu (base hoặc ones). Kết quả không chỉ là độ dài đoạn con tối ưu tìm được, mà là tổng số 1 có thể tập hợp lại được.
• Lầm tưởng rằng chỉ cần tìm đoạn toàn 0 dài nhất. Việc chỉ tìm đoạn toàn 0 dài nhất không đủ, vì đoạn đó có thể bị ngăn cách bởi các đoạn 1 ở xa. Phải xem xét sự đánh đổi giữa 0 và 1 trong đoạn con được chọn.