Editorial for wosub: Đoạn con thách đố

Hiểu bài toán

Bài toán yêu cầu tìm đoạn con liên tiếp dài nhất trong một mảng một chiều các số nguyên dương sao cho tổng các phần tử trong đoạn con đó bằng với một giá trị cho trước S. Nếu không tồn tại đoạn con nào có tổng bằng S, kết quả là -1.

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

Cách Brute Force (Vét cạn)

#include<stdio.h>
#include<math.h>
int main(){
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    int s,res=-1,max=-1e9;
    scanf("%d",&s);
    for(int i=0;i<n;i++){
        int d=0;
        for(int j=i;j<n;j++){
            d+=a[j];
            if(d>s){
                break;
            }
            else if(d==s){
                if(j-i+1>res){
                    res=j-i+1;
                }
                break; 
            }
        }
    }
    printf("%d",res);
    return 0;
}

• Time Complexity: O(N^2) trong trường hợp xấu nhất (tuy nhiên do break sớm khi tổng vượt quá S và các phần tử dương, thời gian thực tế nhanh hơn)
• Space Complexity: O(1) (không tính mảng đầu vào)

Phương pháp này sử dụng hai vòng lặp lồng nhau để duyệt qua tất cả các đoạn con có thể. Vòng lặp ngoài chọn điểm bắt đầu (i), vòng lặp trong chọn điểm kết thúc (j). Tại mỗi đoạn con [i, j], ta tính tổng và so sánh với S. Do các phần tử đều dương, nếu tại một thời điểm nào đó tổng vượt quá S, ta có thể kết thúc vòng lặp trong sớm (break) vì các phần tử tiếp theo sẽ chỉ làm tổng tăng lên. Nếu tìm thấy đoạn con có tổng bằng S, ta cập nhật độ dài lớn nhất.

Cách Two Pointers (Hai con trỏ)

#include <stdio.h>

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    int a[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    int S;
    scanf("%d", &S);

    int left = 0;
    long long current_sum = 0;
    int max_len = -1;
    int found = 0;

    for (int right = 0; right < n; right++) {
        current_sum += a[right];

        while (current_sum > S && left <= right) {
            current_sum -= a[left];
            left++;
        }

        if (current_sum == S) {
            int len = right - left + 1;
            if (len > max_len) {
                max_len = len;
                found = 1;
            }
        }
    }

    if (!found) printf("-1");
    else printf("%d", max_len);

    return 0;
}

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

Đây là cách tiếp cận tối ưu. Ta sử dụng hai con trỏ (hoặc chỉ số) left và right để biểu diễn một đoạn con. right duyệt qua các phần tử từ đầu到最后. Ta duy trì tổng của đoạn con hiện tại current_sum. Nếu current_sum nhỏ hơn S, ta tiếp tục tăng right để thêm phần tử vào đoạn con. Nếu current_sum vượt quá S, ta cần loại bỏ các phần tử ở đầu đoạn con bằng cách tăng left cho đến khi current_sum <= S. Do các phần tử đều dương, current_sum sẽ giảm khi left tăng. Khi current_sum bằng S, ta cập nhật độ dài lớn nhất. Độ phức tạp là O(N) vì mỗi phần tử chỉ được thêm vào và loại ra khỏi đoạn con tối đa một lần.

Cách Prefix Sum + Hash Map

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

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

    unordered_map<long long, int> first_occurrence;
    long long prefix_sum = 0;
    int max_len = -1;

    // Base case: prefix sum 0 occurs at index -1 (before array starts)
    first_occurrence[0] = -1;

    for (int i = 0; i < n; i++) {
        prefix_sum += a[i];

        // We want to find if there exists a previous index j such that
        // prefix_sum - prefix_sum[j] = S
        // => prefix_sum[j] = prefix_sum - S
        long long target = prefix_sum - S;

        if (first_occurrence.count(target)) {
            int len = i - first_occurrence[target];
            if (len > max_len) {
                max_len = len;
            }
        }

        // Only store the first occurrence of this prefix sum to get the longest segment
        if (first_occurrence.find(prefix_sum) == first_occurrence.end()) {
            first_occurrence[prefix_sum] = i;
        }
    }

    cout << max_len << endl;
    return 0;
}

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

Phương pháp này sử dụng ý tưởng tổng tiền tố (Prefix Sum). Gọi P[i] là tổng các phần tử từ a[0] đến a[i]. Tổng của đoạn con từ chỉ số j+1 đến i là P[i] - P[j]. Ta cần tìm P[i] - P[j] = S, hay P[j] = P[i] - S. Trong khi duyệt qua mảng, ta tính P[i] và kiểm tra xem giá trị P[i] - S đã xuất hiện trước đó chưa bằng một Hash Map (đồ á băm). Nếu có, ta tìm được đoạn con có tổng bằng S. Để tìm đoạn dài nhất, ta chỉ cần lưu chỉ số xuất hiện đầu tiên của mỗi tổng tiền tố. Độ phức tạp thời gian là O(N) cho quá trình duyệt và truy vấn Hash Map.

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

Bài học kinh nghiệm

• Tất cả các phần tử đều dương: Điều này cho phép các thuật toán 'Two Pointers' và 'vét cạn có break' hoạt động hiệu quả vì tổng của đoạn con tăng dần khi ta mở rộng đoạn con về bên phải.
• Bài toán quy về bài toán tìm hai chỉ số i, j sao cho tổng tiền tố tại j trừ đi tổng tiền tố tại i bằng S.
• Để tìm đoạn con dài nhất, trong phương pháp Hash Map, ta chỉ cần ghi nhận chỉ số xuất hiện đầu tiên của mỗi tổng tiền tố.

Lỗi thường gặp

• Lưu ý về kiểu dữ liệu: Tổng các phần tử có thể vượt quá giới hạn của kiểu int (với N=10^5 và a[i]=1000, tổng tối đa là 10^8, nằm trong int nhưng nếu S lớn hoặc tổng âm thì cần long long). Tuy nhiên, ở bài này a[i] dương nên int có thể đủ, nhưng dùng long long an toàn hơn.
• Xử lý trường hợp đoạn con bắt đầu từ phần tử đầu tiên (chỉ số 0): Cần khởi tạo tổng tiền tố trước mảng (giả sử là 0 tại chỉ số -1) vào Hash Map.
• Với thuật toán Two Pointers, điều kiện dừng của vòng lặp while khi thu hẹp đoạn con phải chính xác: while (current_sum > S && left <= right).