Editorial for dplines: Chia dòng văn bản

Hiểu bài toán

Bài toán yêu cầu chia một chuỗi gồm N từ vào các dòng sao cho mỗi dòng có tổng độ dài các từ không vượt quá L. Khi dàn các từ trên một dòng, nếu tổng độ dài thực tế là T (T ≤ L) thì độ xấu của dòng đó là L - T. Độ xấu của toàn văn bản được định nghĩa là độ xấu lớn nhất trong tất cả các dòng. Ta cần tìm cách chia sao cho độ xấu lớn nhất này là nhỏ nhất có thể.

Nói cách khác, ta cần tìm giá trị X nhỏ nhất sao cho có thể chia văn bản thành các dòng sao cho độ xấu của mỗi dòng không vượt quá X. Vì độ xấu của dòng thứ k là L - sum_len(dòng k), điều kiện này tương đương với việc tổng độ dài các từ trong mỗi dòng phải nằm trong khoảng [L - X, L].

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

Cách Quy hoạch động

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, L;
    cin >> N >> L;
    vector<int> a(N + 1);
    for (int i = 1; i <= N; i++) cin >> a[i];
    vector<int> pref(N + 1, 0);
    for (int i = 1; i <= N; i++) pref[i] = pref[i - 1] + a[i];

    // dp[i] là độ xấu lớn nhất của các dòng trước đó khi xử lý đến từ thứ i
    // Chúng ta cần tìm min của max(dp[j], ...) nên dp sẽ lưu độ xấu lớn nhất
    // Tuy nhiên, logic của giải pháp này cần phải được điều chỉnh để tìm min của max
    // Code dưới đây là một biến thể của giải pháp O(N^2) tìm X nhỏ nhất

    // Cach 2 (Tu Solution 2): Tim X nho nhat truc tiep
    // dp[i] là độ xấu lớn nhất của các dòng khi chia xong đến từ thứ i (với cách chia tối ưu nhất)
    vector<int> dp(N + 1, 1e9);
    dp[0] = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < i; j++) {
            if (pref[i] - pref[j] <= L) {
                // Độ xấu của dòng hiện tại (từ j+1 đến i) là L - (pref[i] - pref[j])
                // Độ xấu của cách chia trước đó là dp[j]
                // Độ xấu của cách chia mới là max(dp[j], L - (pref[i] - pref[j]))
                dp[i] = min(dp[i], max(dp[j], L - (pref[i] - pref[j])));
            }
        }
    }
    cout << dp[N];
    return 0;
}

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

Giải pháp này sử dụng quy hoạch động. Ta định nghĩa dp[i] là độ xấu lớn nhất của văn bản khi đã chia xong i từ đầu tiên (với cách chia tối ưu nhất).

• Trạng thái: dp[i] là độ xấu lớn nhất của các dòng đã được tạo ra từ các từ 1 đến i.
• Chuyển trạng thái: Để tính dp[i], ta xét tất cả các vị trí j trước i có thể là điểm kết thúc của dòng trước đó. Nếu các từ từ j+1 đến i có thể nằm trên một dòng (tức tổng độ dài pref[i] - pref[j] <= L), ta tạo một dòng mới.
• Công thức: dp[i] = min(dp[i], max(dp[j], L - (pref[i] - pref[j]))). Trong đó:
  • dp[j] là độ xấu lớn nhất của các dòng trước đó.
  • L - (pref[i] - pref[j]) là độ xấu của dòng hiện tại.
  • max(...) là độ xấu lớn nhất của cách chia mới.
  • min(...) chọn cách chia tốt nhất (có độ xấu lớn nhất nhỏ nhất).

Độ phức tạp là O(N^2) do có 2 vòng lặp lồng nhau, hoàn toàn chấp nhận được với N ≤ 6000.

Cách Tối ưu hóa Binary Search + DP/Two Pointers

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

int N, L;
vector<int> a, pref;

// Kiểm tra xem có thể chia văn bản sao cho độ xấu mỗi dòng <= X không
bool check(int X) {
    // Điều kiện: mỗi dòng phải có tổng độ dài >= L - X
    int min_len = max(0, L - X);
    // dp[i]: true nếu có thể chia xong i từ đầu tiên
    vector<bool> dp(N + 1, false);
    dp[0] = true;

    // Sử dụng sliding window để tối ưu
    // dp[i] = true nếu tồn tại j < i sao cho dp[j] == true và min_len <= pref[i]-pref[j] <= L
    // Tức là pref[j] nằm trong [pref[i] - L, pref[i] - min_len]

    int left = 0, right = 0; // Window cho dp[j] == true
    // Cần quản lý các chỉ số j sao cho pref[j] được sắp xếp
    // Hoặc đơn giản là dùng mảng thường do N nhỏ

    for (int i = 1; i <= N; i++) {
        // Duyệt j để tìm dp[i]
        for (int j = 0; j < i; j++) {
            if (dp[j]) {
                int len = pref[i] - pref[j];
                if (len >= min_len && len <= L) {
                    dp[i] = true;
                    break;
                }
            }
        }
    }
    return dp[N];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> L;
    a.resize(N + 1);
    pref.resize(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
    }

    int low = 0, high = L; // Đáp án nằm trong khoảng [0, L]
    while (low < high) {
        int mid = (low + high) / 2;
        if (check(mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    cout << low;
    return 0;
}

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

Ta có thể cải tiến bằng cách kết hợp Binary Search và Quy hoạch động.

1. Binary Search: Ta tìm giá trị X (độ xấu tối thiểu) bằng cách tìm kiếm nhị phân trong khoảng từ 0 đến L.
2. Hàm kiểm tra (Check): Với mỗi giá trị X, ta cần kiểm tra xem có thể chia văn bản sao cho mọi dòng có độ xấu không vượt quá X hay không.
   • Điều kiện này tương đương với việc mỗi dòng phải có tổng độ dài từ L - X đến L.
   • Ta dùng quy hoạch động dp[i] (kiểu boolean) để kiểm tra xem có thể chia xong i từ đầu tiên hay không.
   • dp[i] = true nếu tồn tại j < i sao cho dp[j] = true và đoạn từ j+1 đến i hợp lệ.

Vì N khá nhỏ (6000), việc dùng DP O(N^2) bên trong hàm check O(log L) là hoàn toàn ổn. Tuy nhiên, có thể tối ưu hơn nữa bằng cách dùng Two Pointers (Sliding Window) cho phần tìm j hợp lệ, giảm độ phức tạp của check xuống O(N).

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

Bài học kinh nghiệm

• Bài toán có thể được xem là bài toán tìm giá trị nhỏ nhất (Minimize the Maximum) của độ xấu, rất phù hợp với phương pháp Binary Search kết hợp với kiểm tra tính khả thi (Feasibility Check).
• Nếu không dùng Binary Search, ta có thể giải trực tiếp bằng Quy hoạch động O(N^2) bằng cách định nghĩa dp[i] là giá trị độ xấu lớn nhất của cách chia tốt nhất cho i từ đầu tiên.
• Việc sử dụng mảng tổng tiền tố (prefix sum) giúp tính tổng độ dài của một đoạn từ trong O(1), từ đó kiểm tra điều kiện dòng một cách nhanh chóng.

Lỗi thường gặp

• Lầm tưởng độ xấu là tổng độ dài của dòng. Độ xấu được định nghĩa là L - T (phần còn lại), nên khi kiểm tra điều kiện dòng, ta cần chú ý đến cả giới hạn dưới (nếu có) tương ứng với L - X.
• Xử lý sai các chỉ số mảng khi tính prefix sum hoặc truy vấn dp. Cần chú ý dp[0] thường là khởi tạo (true hoặc 0) và xử lý từ i=1.
• Quên kiểm tra điều kiện dòng có thể trống hoặc chỉ chứa 1 từ, dẫn đến sai lệch trong các biên của vòng lặp.