Hiểu bài toán

Cho một dãy gồm N tấm ván sơn các màu khác nhau. Ta được phép thực hiện thao tác: chọn một màu C và xóa tất cả các tấm ván có màu C đó khỏi dãy. Sau khi xóa, các tấm ván còn lại sẽ sát lại với nhau nhưng vẫn giữ nguyên thứ tự ban đầu. Nhiệm vụ là tìm độ dài của đoạn liên tiếp dài nhất (với các tấm ván cùng màu nằm cạnh nhau) có thể đạt được sau khi thực hiện đúng một thao tác xóa một màu bất kỳ (hoặc không xóa gì cả). Ví dụ: với dãy [1, 2, 2, 3, 2, 2], nếu xóa màu 1 ta được [2, 2, 3, 2, 2] (đoạn dài nhất là 2), nếu xóa màu 3 ta được [1, 2, 2, 2, 2] (đoạn dài nhất là 4).

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

Cách Brute Force (Duyệt tất cả màu)

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

int main() {
    ifstream in("paint.in");
    ofstream out("paint.out");
    int n;
    in >> n;
    vector<int> a(n);
    set<int> colors;
    for (int i = 0; i < n; i++) {
        in >> a[i];
        colors.insert(a[i]);
    }

    int res = 1;
    // Thử xóa từng loại màu
    for (int color : colors) {
        vector<int> filtered;
        for (int x : a) {
            if (x != color) {
                filtered.push_back(x);
            }
        }

        // Tính độ dài đoạn liên tiếp dài nhất trong mảng mới
        if (filtered.empty()) continue;
        int current_len = 1;
        for (int i = 1; i < filtered.size(); i++) {
            if (filtered[i] == filtered[i-1]) {
                current_len++;
            } else {
                res = max(res, current_len);
                current_len = 1;
            }
        }
        res = max(res, current_len);
    }
    out << res;
    in.close();
    out.close();
    return 0;
}

• Time Complexity: O(N * K) (K là số màu phân biệt, tối đa N -> O(N^2))
• Space Complexity: O(N)

Cách tiếp cận này giả lập trực tiếp quá trình xóa màu. Duyệt qua từng màu duy nhất có trong dãy. Với mỗi màu đó, tạo một mảng mới chứa các phần tử không phải màu đó. Sau đó, duyệt mảng mới này để tìm đoạn liên tiếp dài nhất. Đây là cách làm đơn giản nhất nhưng không hiệu quả về mặt thời gian执行.

Cách Hash Map Optimization (Tối ưu hóa)

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen("paint.in", "r", stdin);
    freopen("paint.out", "w", stdout);

    int n;
    cin >> n;
    vector<int> a(n);
    set<int> s;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s.insert(a[i]);
    }

    int res = 0;
    for (int color : s) {
        int count = 1;
        int before = -1; // Lưu màu của phần tử trước đó (sau khi lọc)

        for (int i = 0; i < n; i++) {
            if (a[i] == color) continue; // Bỏ qua màu đang xóa

            if (a[i] == before) {
                count++;
            } else {
                res = max(res, count);
                count = 1;
                before = a[i];
            }
        }
        res = max(res, count); // Kiểm tra đoạn cuối cùng
    }

    cout << res;
    return 0;
}

• Time Complexity: O(N * K) (với K là số màu phân biệt)
• Space Complexity: O(N)

Thay vì tạo mảng mới tốn bộ nhớ và thời gian copy, ta chỉ cần duyệt mảng gốc và giả vờ rằng phần tử có màu đang xóa không tồn tại. Biến before dùng để lưu màu của phần tử hợp lệ gần nhất. Nếu phần tử hiện tại (khác màu đang xóa) giống before thì tăng độ dài đoạn liên tiếp. Cách này loại bỏ overhead của việc tạo vector mới nhưng về độ phức tạp thuật toán vẫn là O(N^2) trong trường hợp xấu nhất (nếu có N màu phân biệt).

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

Bài học kinh nghiệm

• Bài toán có thể được chia nhỏ thành các bài toán con: 'Nếu xóa màu X thì độ dài đoạn liên tiếp dài nhất là bao nhiêu?' và ta cần tìm giá trị lớn nhất trong các bài toán con đó.
• Màu sắc là các số nguyên, có thể sử dụng cấu trúc dữ liệu Set hoặc Unordered Set để lấy danh sách các màu phân biệt một cách nhanh chóng.
• Việc xóa một màu làm thay đổi tính liên tiếp của các đoạn, nhưng ta chỉ quan tâm đến các đoạn mới được nối lại với nhau.

Lỗi thường gặp

• Quên xử lý trường hợp dãy rỗng sau khi xóa (ví dụ xóa hết tất cả các phần tử).
• Biến res phải được khởi tạo đúng (ví dụ bằng 1 hoặc 0) và cập nhật giá trị cuối cùng của đoạn liên tiếp sau vòng lặp.
• Sử dụng vector để lưu mảng mới trong cách 1 có thể gây tràn bộ nhớ hoặc chậm nếu N lớn (ví dụ N=10^5).