Hướng dẫn cho COLORBOX (OLP MT&TN 2023 Sơ Loại Không Chuyên)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: Flower_On_Stone

Tóm tắt đề bài

Cho một dãy \(n\) cây màu \(a_1, a_2, \dots, a_n\). Bạn cần chọn một đoạn con liên tiếp từ vị trí \(l\) đến \(r\) (\(1 \leq l \leq r \leq n\)) để loại bỏ, sao cho các cây màu còn lại (phần phía trước \(l\) và phần phía sau \(r\)) đôi một khác nhau. Tìm độ dài đoạn \([l, r]\) nhỏ nhất.

Phân tích

Điều kiện: Sau khi bỏ đoạn \([l, r]\), tập hợp các phần tử \(\{a_1, \dots, a_{l-1}, a_{r+1}, \dots, a_n\}\) không có phần tử nào lặp lại.
Ràng buộc: \(n \leq 10^6\), các giá trị \(a_i \leq n\). Với \(n\) lớn như vậy, thuật toán cần đạt độ phức tạp \(O(n)\).
Nhận xét quan trọng:
- Nếu ta bỏ đoạn \([l, r]\) mà thỏa mãn điều kiện, thì khi mở rộng đoạn đó thành \([l, r+1]\) hoặc \([l-1, r]\), điều kiện vẫn sẽ được thỏa mãn (vì tập hợp các phần tử còn lại chỉ ít đi, không thể phát sinh thêm sự trùng lặp).
- Đây là tính chất của kỹ thuật Two Pointers (Hai con trỏ).

Cách làm đơn giản (Brute Force)

Ý tưởng

Duyệt qua tất cả các cặp \((l, r)\) có thể có. Với mỗi cặp, kiểm tra xem các phần tử còn lại có đôi một khác nhau hay không bằng cách dùng một mảng đánh dấu hoặc tập hợp (set).

Độ phức tạp

Thời gian: \(O(n^3)\) hoặc \(O(n^2)\) nếu tối ưu việc kiểm tra.
Đánh giá: Chỉ phù hợp với \(n \leq 1000\) (Subtask 1 và 2).

Code Brute Force

C++

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

bool check(int l, int r, int n, const vector<int>& a) {
    vector<int> cnt(n + 1, 0);
    for (int i = 0; i < n; i++) {
        if (i >= l && i <= r) continue; // Bỏ qua đoạn [l, r]
        cnt[a[i]]++;
        if (cnt[a[i]] > 1) return false;
    }
    return true;
}

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

    int ans = n;
    for (int l = 0; l < n; l++) {
        for (int r = l; r < n; r++) {
            if (check(l, r, n, a)) {
                ans = min(ans, r - l + 1);
            }
        }
    }
    cout << ans;
    return 0;
}

Python

n = int(input())
a = list(map(int, input().split()))

def check(l, r):
    cnt = {}
    for i in range(n):
        if l <= i <= r:
            continue
        if a[i] in cnt:
            return False
        cnt[a[i]] = 1
    return True

ans = n
for l in range(n):
    for r in range(l, n):
        if check(l, r):
            ans = min(ans, r - l + 1)
print(ans)

Hướng giải quyết (Tối ưu)

Thuật toán Hai con trỏ (Two Pointers)

Mục tiêu là tìm đoạn \([l, r]\) ngắn nhất sao cho các phần tử ngoài đoạn này không trùng nhau.

Khởi tạo:
- Sử dụng mảng cnt để đếm số lần xuất hiện của mỗi màu trong tập hợp các phần tử "đang giữ lại".
- Biến duplicate đếm số lượng màu đang bị lặp lại (có cnt[x] > 1).
- Ban đầu, ta coi như chưa bỏ đoạn nào, cho tất cả các phần tử vào cnt.
Tiến hành:
- Sử dụng con trỏ left chạy từ \(0\) đến \(n-1\). Với mỗi left, ta cố gắng tìm con trỏ right nhỏ nhất sao cho khi bỏ đoạn [left, right], số lượng duplicate bằng \(0\).
- Khi left tăng lên, ta "thêm lại" phần tử \(a_{left-1}\) vào tập hợp giữ lại.
- Khi right tăng lên, ta "loại bỏ" phần tử \(a_{right}\) khỏi tập hợp giữ lại.
Chi tiết hàm add và del_value:
- add(x): Tăng cnt[x]. Nếu cnt[x] == 2, tức là màu \(x\) bắt đầu bị lặp, tăng duplicate.
- del_value(x): Giảm cnt[x]. Nếu cnt[x] == 1, tức là màu \(x\) không còn bị lặp, giảm duplicate.

Các bước thực hiện

Bước 1: Thêm toàn bộ mảng vào hệ thống đếm.
Bước 2: Bắt đầu duyệt left từ \(0\). Tại mỗi left, ta di chuyển right xa dần cho đến khi không còn màu nào bị lặp (duplicate == 0).
Bước 3: Cập nhật kết quả ans = min(ans, right - left + 1).

Độ phức tạp

Thời gian: \(O(n)\) vì mỗi con trỏ left và right chỉ duyệt qua mảng một lần.
Bộ nhớ: \(O(n)\) để lưu mảng cnt.

Code tham khảo

C++

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

const int MAXN = 1000005;
int cnt[MAXN];
int duplicate = 0;

void add(int value) {
    cnt[value]++;
    if (cnt[value] == 2) {
        duplicate++;
    }
}

void del_value(int value) {
    cnt[value]--;
    if (cnt[value] == 1) {
        duplicate--;
    }
}

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

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

    // Nếu ban đầu không có màu nào lặp
    if (duplicate == 0) {
        cout << 0;
        return 0;
    }

    int right = -1;
    int answer = n;

    for (int left = 0; left < n; left++) {
        // Thử mở rộng right cho đến khi hết duplicate
        while (right < n - 1 && duplicate > 0) {
            right++;
            del_value(a[right]);
        }

        if (duplicate == 0) {
            answer = min(answer, right - left + 1);
        }

        // Trước khi sang left tiếp theo, phải trả lại a[left] vào tập giữ lại
        add(a[left]);
    }

    cout << answer;
    return 0;
}

Python

import sys

def solve():
    # Đọc dữ liệu nhanh
    input = sys.stdin.read().split()
    if not input:
        return
    n = int(input[0])
    a = list(map(int, input[1:]))

    MAX_N = 1000005
    cnt = [0] * MAX_N
    duplicate = 0

    def add(value):
        nonlocal duplicate
        cnt[value] += 1
        if cnt[value] == 2:
            duplicate += 1

    def del_value(value):
        nonlocal duplicate
        cnt[value] -= 1
        if cnt[value] == 1:
            duplicate -= 1

    # Ban đầu thêm tất cả các phần tử vào
    for x in a:
        add(x)

    if duplicate == 0:
        print(0)
        return

    right = -1
    answer = n

    # Kỹ thuật hai con trỏ
    for left in range(n):
        # Di chuyển right để loại bỏ các phần tử lặp
        while right < n - 1 and duplicate > 0:
            right += 1
            del_value(a[right])

        if duplicate == 0:
            answer = min(answer, right - left + 1)

        # Thêm lại phần tử ở vị trí left vào tập hợp giữ lại
        add(a[left])

    print(answer)

solve()

Bình luận

Tải bình luận...

Không có bình luận nào.