Hiểu bài toán

Nhiệm vụ là tìm số lượng thẻ tối thiểu cần thay đổi để dãy số 1 và 2 thỏa mãn điều kiện: tất cả các con bò cầm thẻ 1 phải đứng trước tất cả các con bò cầm thẻ 2. Về cơ bản, dãy kết quả phải có dạng: một đoạn đầu toàn số 1, đoạn sau toàn số 2 (hoặc chỉ có 1 loại duy nhất). Chúng ta chỉ được phép thay đổi giá trị thẻ, không được đổi chỗ các con bò.

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

Cách Brute Force (Duyệt toàn bộ)

#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];

    int min_changes = N;
    // Duyệt mọi vị trí chia cắt i (từ 0 đến N)
    // Vị trí i là chỉ số đầu tiên của phần tử 2 (nếu có)
    for (int i = 0; i <= N; i++) {
        int changes = 0;
        // Đếm số lượng thẻ 2 ở bên trái (cần đổi thành 1)
        for (int j = 0; j < i; j++) {
            if (a[j] == 2) changes++;
        }
        // Đếm số lượng thẻ 1 ở bên phải (cần đổi thành 2)
        for (int j = i; j < N; j++) {
            if (a[j] == 1) changes++;
        }
        min_changes = min(min_changes, changes);
    }

    cout << min_changes << endl;
    return 0;
}

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

Cách tiếp cận này thử tất cả các cách chia dãy thành 2 phần: phần đầu (từ 0 đến i-1) sẽ là nơi ở của các con số 1, và phần sau (từ i đến N-1) sẽ là nơi ở của các con số 2. Với mỗi cách chia, ta đếm số lượng thẻ sai vị trí (số 2 ở bên trái và số 1 ở bên phải). Độ phức tạp là O(N^2) do có N vị trí chia và mỗi vị trí tốn O(N) để đếm, phù hợp với N nhỏ nhưng không tối ưu cho N lên tới 30,000.

Cách Prefix and Suffix Arrays (Tiền tố và Hậu tố)

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

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

    // prefix_2[i]: số lượng thẻ 2 từ vị trí 1 đến i
    vector<int> prefix_2(N + 1, 0);
    // suffix_1[i]: số lượng thẻ 1 từ vị trí i đến N
    vector<int> suffix_1(N + 2, 0);

    for (int i = 1; i <= N; i++)
        prefix_2[i] = prefix_2[i - 1] + (a[i] == 2);

    for (int i = N; i >= 1; i--)
        suffix_1[i] = suffix_1[i + 1] + (a[i] == 1);

    int res = N;
    // Duyệt vị trí chia từ 0 đến N
    // Nếu chia tại i, bên trái (1..i) chỉ được có 1, bên phải (i+1..N) chỉ được có 2
    // Số thẻ 2 cần đổi ở bên trái: prefix_2[i]
    // Số thẻ 1 cần đổi ở bên phải: suffix_1[i+1]
    for (int i = 0; i <= N; i++) {
        int current_changes = prefix_2[i] + suffix_1[i + 1];
        res = min(res, current_changes);
    }

    cout << res << endl;
    return 0;
}

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

Để tối ưu, ta sử dụng hai mảng phụ. Mảng prefix2[i] lưu số lượng thẻ 2 từ đầu đến i, và mảng suffix1[i] lưu số lượng thẻ 1 từ i đến cuối. Khi đó, với mỗi vị trí chia i, số lần sửa đổi cần thiết là tổng của prefix2[i] (số 2 ở khu vực 1) và suffix1[i+1] (số 1 ở khu vực 2). Việc tính toán này chỉ tốn O(1) sau khi đã xây dựng mảng phụ, giúp giảm độ phức tạp xuống O(N).

Cách Optimized Prefix Sums (Tối ưu)

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

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

    // Tính tổng số lượng 1 có trong toàn bộ dãy
    int total_ones = 0;
    for (int x : d) if (x == 1) total_ones++;

    int min_changes = N; // Khởi tạo giá trị lớn
    int current_twos_in_left = 0;
    int current_ones_in_left = 0;

    // Duyệt qua các vị trí chia
    for (int i = 0; i <= N; ++i) {
        // Thay đổi cần thiết:
        // 1. Đổi các số 2 ở bên trái thành 1: số lượng là current_twos_in_left
        // 2. Đổi các số 1 ở bên phải thành 2: số lượng là (Tổng 1) - (Số 1 ở bên trái)
        int changes = current_twos_in_left + (total_ones - current_ones_in_left);
        min_changes = min(min_changes, changes);

        // Cập nhật biến đếm cho vị trí chia tiếp theo
        if (i < N) {
            if (d[i] == 2) current_twos_in_left++;
            else if (d[i] == 1) current_ones_in_left++;
        }
    }

    cout << min_changes << endl;
    return 0;
}

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

Phương pháp này là phiên bản tối ưu nhất của kỹ thuật tiền tố. Thay vì lưu trữ toàn bộ mảng, ta chỉ cần duyệt qua dãy một lần duy nhất. Ta duy trì số lượng thẻ 2 và thẻ 1 đã đi qua. Với mỗi vị trí chia, số lượng sửa đổi được tính toán tức thì bằng cách lấy số 2 ở bên trái cộng với số 1 ở bên phải (tính bằng tổng số 1 trừ đi số 1 ở bên trái). Cách này giúp tiết kiệm bộ nhớ tối đa (O(1)) và vẫn đảm bảo tốc độ O(N).

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

Bài học kinh nghiệm

• Bài toán có thể quy về bài toán tìm điểm chia (split point) sao cho tổng chi phí là nhỏ nhất. Chi phí tại điểm chia i bao gồm: số lượng '2' ở bên trái (0..i-1) và số lượng '1' ở bên phải (i..N-1).
• Sử dụng kỹ thuật 'Prefix Sums' (tổng tiền tố) để tính toán nhanh số lượng các phần tử trong một đoạn mà không cần duyệt lại.
• Vì giới hạn N khá lớn (30,000), thuật toán O(N^2) sẽ bị TLE (Time Limit Exceeded), do đó cần sử dụng thuật toán O(N) hoặc O(N log N).

Lỗi thường gặp

• LỗiIndexing: Trong C++, mảng thường bắt đầu từ 0, nhưng khi tính tổng tiền tố từ 1 đến N, cần chú ý chuyển đổi chỉ số cho đúng để tránh truy cập ngoài vùng nhớ.
• Xử lý biên: Cần kiểm tra các trường hợp đặc biệt như N=0, hoặc toàn bộ dãy chỉ có một loại số (chỉ có 1 hoặc chỉ có 2). Vòng lặp duyệt điểm chia phải đi từ 0 đến N (bao gồm cả trường hợp chia ở ngay đầu hoặc ngay cuối).
• Sử dụng biến phụ: Trong giải pháp tối ưu, cần phân biệt rõ biến đếm 'tổng số 1' và 'số 1 đã đi qua' để tính toán đúng số lượng thẻ 1 ở bên phải.