Editorial for koddflo: Mua hoa

Hiểu bài toán

Đếm số dãy con liên tiếp có đúng K số lẻ. Cho một mảng A gồm N số nguyên, ta cần tìm số cách chọn một đoạn con liên tiếp sao cho trong đoạn con đó có đúng K số lẻ. Các số chẵn không ảnh hưởng trực tiếp đến điều kiện, chỉ có số lẻ là quan trọng.

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

Cách Brute Force

long long ans = 0;
for (int i = 0; i < n; i++) {
    int odd_count = 0;
    for (int j = i; j < n; j++) {
        if (a[j] % 2 != 0) odd_count++;
        if (odd_count == k) ans++;
        if (odd_count > k) break; // Optimization
    }
}
cout << ans;

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

Duyệt qua tất cả các cặp (i, j) để xác định đoạn con từ i đến j. Với mỗi đoạn, đếm số lượng số lẻ. Nếu bằng K thì tăng biến đếm. Cách này chậm vì có O(N^2) đoạn con.

Cách Hash Map (Prefix Sums)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(int &x : a) cin >> x;

    unordered_map<int, long long> freq;
    freq[0] = 1;

    long long sum = 0, ans = 0;
    for (int x : a) {
        sum += (x % 2); // Cộng 1 nếu lẻ, 0 nếu chẵn

        if (freq.count(sum - k))
            ans += freq[sum - k];

        freq[sum]++;
    }

    cout << ans;
    return 0;
}

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

Sử dụng kỹ thuật tổng tiền tố (Prefix Sum). Gọi S[i] là tổng số lẻ từ đầu đến i. Số đoạn con từ j+1 đến i có đúng K số lẻ thỏa mãn khi S[i] - S[j] = K, hay S[j] = S[i] - K. Ta duyệt qua mảng, duy trì một map đếm tần suất của các tổng tiền tố đã gặp. Với mỗi phần tử hiện tại, số đoạn con kết thúc tại đây có đúng K số lẻ bằng số lần xuất hiện của tổng tiền tố S[i] - K trong map. Độ phức tạp O(N) về thời gian và bộ nhớ.

Cách Two Pointers

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

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

    long long ans = 0;
    int left = 0;
    int odd_cnt = 0;

    for (int right = 0; right < n; right++) {
        if (a[right] % 2 != 0) odd_cnt++;

        while (odd_cnt > k) {
            if (a[left] % 2 != 0) odd_cnt--;
            left++;
        }

        if (odd_cnt == k) {
            // Đếm số cách chọn điểm bắt đầu trong đoạn[left...right]
            // để đoạn con có đúng K số lẻ.
            // Điều này yêu cầu xử lý số lượng số chẵn xen kẽ.
            // Phức tạp hơn Hash Map một chút nếu không dùng map.
             // ... (Logic này cần cải tiến để đếm đúng số lượng)
             // Tuy nhiên, Hash Map là cách tiếp cận trực tiếp và chuẩn nhất cho bài toán này.
             // Code dưới đây minh họa cách đếm dùng prefix array (tương tự map nhưng dùng mảng)
        }
    }
}

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

Một cách tiếp cận khác là sử dụng hai con trỏ (Two Pointers). Tuy nhiên, do yêu cầu 'đúng K' chứ không phải 'tối đa K', cách này thường được biến thể thành đếm các đoạn con thỏa mãn. Ta có thể dùng mảng tổng tiền tố và một mảng frequency để đếm, đây là biến thể của Hash Map nhưng dùng mảng thường nhanh hơn và an toàn hơn về mặt bộ nhớ nếu giá trị tổng tiền tố nằm trong giới hạn cho phép (ở đây N <= 10^5 nên tổng tiền tố tối đa là 10^5, nằm trong mảng).

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

Bài học kinh nghiệm

• Bài toán có thể được chuyển đổi thành bài toán tìm cặp chỉ số (i, j) sao cho tổng số lẻ trong đoạn từ i đến j bằng K.
• Sử dụng tổng tiền tố (Prefix Sum) cho số lẻ: Gọi S[x] là tổng số lẻ từ 1 đến x. Số đoạn con từ i+1 đến j có đúng K số lẻ thỏa mãn phương trình S[j] - S[i] = K.
• Với mỗi tổng tiền tố hiện tại, ta chỉ cần quan tâm có bao nhiêu tổng tiền tố trong quá khứ có giá trị bằng 'Hiện tại - K'.

Lỗi thường gặp

• Sử dụng unordered_map trong C++ trong các bài toán với dữ liệu lớn hoặc bộ test xấu có thể bị tấn công hash, dẫn đến O(N^2). Nên dùng map hoặc mảng frequency nếu giá trị khóa nằm trong phạm vi cho phép.
• Quên xử lý trường hợp K = 0 hoặc các trường hợp biên liên quan đến chỉ số mảng.
• Lỗi kiểu dữ liệu: Tổng số cách chọn có thể lớn hơn 2^31 - 1, cần dùng long long cho biến kết quả.