Editorial for egroup: Đàn bò của nông dân John

Hiểu bài toán

Cho một dãy gồm N số nguyên, mỗi số chỉ nhận giá trị 1 hoặc 2. Nhiệm vụ là sửa đổi các giá trị trong dãy (bằng cách thay đổi chúng thành bất kỳ giá trị nào khác) sao cho dãy kết quả thỏa mãn tính chất: tất cả các số 1 phải đứng trước tất cả các số 2. Mục tiêu là tìm số lần sửa đổi tối thiểu. Có thể thay đổi một số thành 1, thành 2, hoặc thành một giá trị khác (ví dụ 3, 0...) để 'lãng quên' nó, nhưng quan trọng là dãy con chứa các số 1 phải nằm hoàn toàn trước dãy con chứa các số 2.

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

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

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

int solve(int n, const vector<int>& D) {
    vector<int> F1(n+1, 0), F2(n+1, 0), F3(n+1, 0);

    for (int i = 1; i <= n; ++i) {
        // F1: Chi phí để phần trước i chỉ toàn là 1
        F1[i] = F1[i-1] + (D[i] == 1 ? 0 : 1);
        // F2: Chi phí để phần trước i có dạng 1...12...2 (đang ở đoạn 2)
        F2[i] = min(F1[i], F2[i-1] + (D[i] == 2 ? 0 : 1));
        // F3: Chi phí để phần trước i có dạng 1...12...23...3 (đang ở đoạn 3)
        F3[i] = min(F2[i], F3[i-1] + (D[i] == 3 ? 0 : 1));
    }
    return F3[n];
}

int main() {
    int n;
    cin >> n;
    vector<int> D(n+1, 0);

    for (int i = 1; i <= n; ++i) {
        cin >> D[i];
    }

    // Giải quyết bài toán với giả định số 1 là 1, số 2 là 2
    int min1 = solve(n, D);

    // Đổi vai trò: số 2 trở thành 1 và số 1 trở thành 2
    for (int i = 1; i <= n; ++i) {
        D[i] = 4 - D[i];
    }

    // Giải quyết bài toán với vai trò đảo ngược
    int min2 = solve(n, D);

    cout << min(min1, min2) << endl;

    return 0;
}

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

Bài toán yêu cầu dãy chia làm 3 phần: phần đầu toàn số 1, phần giữa toàn số 2, phần cuối toàn số 3 (hoặc các số khác). Tuy nhiên, do chỉ có 1 và 2 đầu vào, ta cần kiểm tra 2 trường hợp: (1) Cuối dãy là số 2 (tức là có thể có đoạn 1 trước đoạn 2). (2) Cuối dãy là số 1 (tức là chỉ toàn 1, hoặc 1 sau 2, tức là dãy 2 rồi 1).

Ta dùng mảng F1, F2, F3:

• F1[i]: Chi phí nhỏ nhất để xử lý i phần tử đầu tiên, sao cho phần tử thứ i là '1' (đoạn 1).
• F2[i]: Chi phí nhỏ nhất để xử lý i phần tử, sao cho phần tử thứ i là '2' (đoạn 2). Nó có thể chuyển từ F1 (bắt đầu đoạn 2) hoặc ở lại F2.
• F3[i]: Chi phí nhỏ nhất để xử lý i phần tử, sao cho phần tử thứ i là '3' (đoạn 3). Nó có thể chuyển từ F2 hoặc ở lại F3.

Do input chỉ có 1 và 2, ta gán:

• Nếu D[i] == 1: Chi phí giữ nguyên ở F1 là 0, ở F2 là 1 (phải sửa thành 2), ở F3 là 1 (phải sửa).
• Nếu D[i] == 2: Chi phí giữ nguyên ở F1 là 1 (phải sửa thành 1), ở F2 là 0, ở F3 là 1.

Bài toán gốc chỉ có 1 và 2, nhưng code mẫu cho phép 3. Do đó, ta chạy 2 lần: Lần 1: Giữ nguyên 1, 2. F3 sẽ là đáp án vì nó bao gồm trường hợp 1->2->3 (tức 1->2 và đoạn 3 rỗng). Lần 2: Đổi 1 thành 2, 2 thành 1 (dùng 4 - D[i]). Đáp án là mín của 2 lần chạy.

Cách Tối ưu hóa Quy hoạch động (O(1) space)

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

    auto calc = [&](int a, int b) {
        int c1 = 0, c2 = 0;
        for (int x : D) {
            // c1: chi phí để đoạn trước là a
            // c2: chi phí để đoạn trước là b
            int new_c1 = c1 + (x == a ? 0 : 1);
            int new_c2 = min(c1, c2) + (x == b ? 0 : 1);
            c1 = new_c1;
            c2 = new_c2;
        }
        return c2;
    };

    // Trường hợp 1: a=1, b=2 (1...2)
    // Trường hợp 2: a=2, b=1 (2...1)
    // Lưu ý: Bài này chỉ có 1 và 2, nhưng để chắc chắn ta xét cả 2.
    // Tuy nhiên, do chỉ có 1 và 2, đáp án nằm ở:
    // 1. Để tất cả là 1 (chi phí = số lượng 2)
    // 2. Để tất cả là 2 (chi phí = số lượng 1)
    // 3. Để 1...12...2 (chi phí = tối thiểu)
    // 4. Để 2...21...1 (chi phí = tối thiểu)

    // Code mẫu ở trên là tối ưu cho 3 giai đoạn. Giai đoạn 3 là 'bất kỳ'.
    // Thực tế bài này chỉ cần xét 2 giai đoạn: 1 rồi 2.
    // Hoặc dùng DP với 2 biến.

    int min_changes = n;
    // Duyệt qua mọi điểm chia i (0 đến n)
    // Sửa phần trước i thành 1, phần từ i trở đi thành 2.
    // Tính nhanh bằng prefix/suffix sum.

    vector<int> prefix(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix[i+1] = prefix[i] + (D[i] == 2 ? 1 : 0);
    }
    vector<int> suffix(n + 1, 0);
    for (int i = n - 1; i >= 0; --i) {
        suffix[i] = suffix[i+1] + (D[i] == 1 ? 1 : 0);
    }

    for (int i = 0; i <= n; ++i) {
        min_changes = min(min_changes, prefix[i] + suffix[i]);
    }
    // Hoặc đổi vai trò 1-2
    // Nhưng do input chỉ có 1 và 2, phép chia "1 trước 2 sau" covers "toàn 1" và "toàn 2".
    // Tuy nhiên, "2 trước 1 sau" cũng hợp lệ nếu ta sửa đổi.
    // Đáp án đúng là min(prefix[i] + suffix[i], prefix2[i] + suffix2[i])
    // Nhưng do input chỉ có 1 và 2, phép chia "1 trước 2 sau" covers "toàn 1" và "toàn 2".
    // Tuy nhiên, "2 trước 1 sau" cũng hợp lệ nếu ta sửa đổi.

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

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

Thay vì dùng DP 3 trạng thái, ta có thể dùng 2 biến để lưu trạng thái:

• cost1: Chi phí để các phần tử xét đến hiện tại đều thuộc nhóm 1.
• cost2: Chi phí để các phần tử xét đến hiện tại đều thuộc nhóm 2 (và có thể có 1 ở trước).

Cập nhật: Nếu gặp số 1:

• Giữ nó ở nhóm 1: cost1 không đổi.
• Chuyển nó vào nhóm 2 (phải sửa thành 2): cost2 mới = min(cost1, cost2) + 1. Nếu gặp số 2:
• Sửa nó thành 1 để vào nhóm 1: cost1 mới = cost1 + 1.
• Giữ nó ở nhóm 2: cost2 mới = min(cost1, cost2).

Hoặc đơn giản hơn (vì chỉ có 1 và 2): Duyệt qua từng vị trí i để làm điểm chia. Phần từ 0 đến i-1 nên là 1. Phần từ i đến n-1 nên là 2. Chi phí = (Số lượng 2 ở bên trái) + (Số lượng 1 ở bên phải). Tính tổng tiền tố (số 2) và hậu tố (số 1) để tính nhanh. Đáp án là giá trị nhỏ nhất khi duyệt qua mọi i. Đừng quên xét trường hợp đổi vai trò (1 thành 2, 2 thành 1) vì "1 trước 2 sau" không cover trường hợp "2 trước 1 sau" (nếu ta muốn giữ 2 trước).

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

Bài học kinh nghiệm

• Bài toán có thể coi là tìm cách chia dãy thành 2 phần (hoặc 3 phần với phần cuối rỗng): phần đầu toàn 1, phần đuôi toàn 2.
• Vì chỉ có 2 loại giá trị đầu vào (1 và 2), ta có thể dùng kỹ thuật 'Prefix Sum' (tổng tiền tố) để đếm số lượng 2 bên trái và số lượng 1 bên phải.
• Một cách tiếp cận khác là Quy hoạch động với 2 trạng thái: đang ở đoạn 1 hoặc đang ở đoạn 2.

Lỗi thường gặp

• Quên xét trường hợp dãy chỉ toàn 1 hoặc toàn 2 (trong cách chia tay, cách này được bao gồm tự động khi điểm chia là 0 hoặc N).
• Quên xét việc đổi vai trò 1 và 2 (tức là cho phép 2 đứng trước 1).