Editorial for house: Sơn nhà

Hiểu bài toán

Bài toán yêu cầu tìm số lượng ít nhất các tòa nhà cần sơn lại để đảm bảo không có hai tòa nhà liên tiếp nào có cùng màu sơn. Ta được cho một xâu độ dài n với các ký tự đại diện cho màu sắc hiện tại của từng tòa nhà. Việc sơn lại có thể thay đổi màu của một tòa nhà thành bất kỳ màu nào trong 4 màu (Đỏ, Vàng, Xanh, Tím).

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

Cách Duyệt và đếm (Greedy)

#include <stdio.h>
#include <string.h>

int main() {
    int n;
    scanf("%d", &n);
    char s[2505];
    scanf("%s", s);

    int ans = 0;
    // Duyệt qua xâu, mỗi khi gặp đoạn liên tiếp các ký tự giống nhau,
    // ta cần thay đổi nửa sau của đoạn đó.
    // Ví dụ: AAAAA -> ABABA (cần 2 lần sơn)
    // Tức là với độ dài k của đoạn giống nhau, ta cần k/2 lần sơn.

    int len = 1;
    for (int i = 1; i < n; i++) {
        if (s[i] == s[i-1]) {
            len++;
        } else {
            ans += len / 2;
            len = 1;
        }
    }
    ans += len / 2; // Xử lý đoạn cuối

    printf("%d\n", ans);
    return 0;
}

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

Cách tiếp cận này dựa trên quan sát: Nếu có một đoạn gồm k tòa nhà liên tiếp cùng màu (ví dụ: DDDD), ta cần thay đổi một nửa số tòa nhà trong đoạn đó để màu sắc xen kẽ (ví dụ: DxDxD...). Số lần sơn tối thiểu cho một đoạn dài k là k/2. Thuật toán duyệt qua xâu, đếm độ dài các đoạn liên tiếp giống nhau, và cộng dồn k/2 vào kết quả.

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

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

const int INF = 1e9;
const string colors = "DVXT";

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    // dp[i][c] là chi phí nhỏ nhất để sơn nhà thứ i thành màu c
    // với điều kiện các nhà trước đó đều hợp lệ.
    vector<vector<int>> dp(n, vector<int>(4, INF));

    // Khởi tạo nhà đầu tiên
    for (int c = 0; c < 4; ++c) {
        if (s[0] == colors[c]) {
            dp[0][c] = 0;
        } else {
            dp[0][c] = 1;
        }
    }

    for (int i = 1; i < n; ++i) {
        for (int curr = 0; curr < 4; ++curr) {
            int cost = (s[i] == colors[curr]) ? 0 : 1;
            for (int prev = 0; prev < 4; ++prev) {
                if (curr == prev) continue;
                dp[i][curr] = min(dp[i][curr], dp[i-1][prev] + cost);
            }
        }
    }

    int ans = INF;
    for (int c = 0; c < 4; ++c) {
        ans = min(ans, dp[n-1][c]);
    }

    cout << ans << endl;
    return 0;
}

• Time Complexity: O(n * C^2) ~ O(n * 16)
• Space Complexity: O(n * C) ~ O(n)

Sử dụng quy hoạch động. Gọi dp[i][c] là số lần sơn ít nhất để căn nhà thứ i có màu c (với c là 1 trong 4 mã màu), sao cho các căn nhà từ 0 đến i đều hợp lệ. Công thức chuyển trạng thái: dp[i][c] = min(dp[i-1][c_prev]) + cost, trong đó cost là 0 nếu màu c trùng màu ban đầu của nhà i, ngược lại là 1. Đáp án là giá trị nhỏ nhất của dp[n-1][c] cho tất cả các màu c.

Cách Giải thuật tham lam (Lưu ý)

#include <stdio.h>
#include <string.h>

int main() {
    int n;
    scanf("%d", &n);
    char s[2505];
    scanf("%s", s);

    int res = 0;
    for (int i = 0; i < n - 1; i++) {
        if (s[i] == s[i + 1]) {
            res++;
            i++; // Bỏ qua nhà tiếp theo
        }
    }
    printf("%d", res);
    return 0;
}

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

Đây là một biến thể của giải thuật tham lam thấy trong Solution 2. Nó duyệt qua dãy nhà, mỗi khi gặp hai nhà liên tiếp cùng màu (s[i] == s[i+1]), nó đếm thêm 1 lần sơn và nhảy qua nhà tiếp theo (i += 2). Ví dụ: DDDD -> D?DD. Trỏ trỏ vào i=0, thấy D=D, đếm 1, nhảy tới i=2. s[2]=D, s[3]=D, đếm 1, nhảy tới i=4. Kết quả là 2. Cách này đúng với các bài toán mà chi phí sơn lại chỉ áp dụng khi có xung đột trực tiếp và việc thay đổi nhà thứ 2 không tạo ra xung đột mới với nhà thứ 3 (vì ta nhảy qua nhà thứ 3). Tuy nhiên, cách tiếp cận chia đoạn k/2 (Approach 1) hay DP (Approach 2) là chính xác hơn và dễ hiểu hơn.

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

Bài học kinh nghiệm

• Bài toán có thể giảm xuống thành bài toán chia dãy thành các đoạn liên tiếp cùng màu, mỗi đoạn dài k cần tối thiểu k/2 lần sơn.
• Quy hoạch động là cách tiếp cận tổng quát nhất, đảm bảo tìm được tối ưu toàn cục.
• Giải thuật tham lam chia đoạn là cách hiệu quả nhất về mặt tính toán cho bài toán này với độ phức tạp O(n).

Lỗi thường gặp

• Lầm tưởng rằng chỉ cần sửa các cặp đôi liền kề (A A -> A B) là đủ, mà không nhận ra nếu có 3 nhà cùng màu AAA, việc sửa nhà giữa (A A A -> A B A) vẫn để lại nhà cuối chưa được xử lý nếu xét theo cặp (nhà 1-2 đã sửa, nhà 2-3 đã sửa, nhưng dãy AAA vẫn tốn 1 lần sửa, AAAA tốn 2 lần...). Công thức chung là k/2.
• Xử lý sai độ dài xâu đầu vào, đặc biệt là khi dùng scanf và getchar trong C.
• Quên cập nhật biến đếm độ dài đoạn liên tiếp ở cuối xâu.