Editorial for c3: Duyệt mảng

Hiểu bài toán

Cho một mảng gồm N số nguyên dương a1, a2, ..., aN và một số nguyên dương X. Nhiệm vụ của bạn là đếm số lượng cặp chỉ số (i, j) sao cho 1 ≤ i ≤ j ≤ N và ai + aj² = X. Giới hạn: N ≤ 10⁵, ai ≤ 500.

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

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

#include <stdio.h>

int main() {
    int n, x, dem = 0;
    scanf("%d%d", &n, &x);
    int a[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (int j = 1; j < n; j++) {
        if (a[j] * a[j] < x) {
            for (int i = 0; i <= j; i++) {
                if (a[i] + a[j] * a[j] == x) ++dem;
            }
        }
    }
    printf("%d", dem);
    return 0;
}

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

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 cặp (i, j) thỏa mãn điều kiện 0 ≤ i ≤ j < N. Với mỗi cặp, nó kiểm tra trực tiếp xem a[i] + a[j]² có bằng X hay không. Do N có thể lên tới 10⁵, độ phức tạp O(N²) sẽ dẫn đến Time Limit Exceeded (TLE).

Cách Hash Map (Đếm tần suất)

#include <stdio.h>

#define MAX_A 501

int main() {
    int n, X;
    scanf("%d %d", &n, &X);

    int a[n], cnt[MAX_A] = {0};
    long long ans = 0;

    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        int needed = X - (a[i] * a[i]);
        if (needed >= 1 && needed <= 500) {
            ans += cnt[needed];
        }
        cnt[a[i]]++;
    }

    printf("%lld\n", ans);
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1) (trừ mảng đếm)

Phương pháp này tối ưu bằng cách sử dụng một mảng đếm (frequency array) để lưu số lần xuất hiện của các số trong mảng. Trong một lần duyệt mảng duy nhất:

1. Với mỗi phần tử a[i], ta xem nó là a_j (số bị bình phương). Ta cần tìm một số a_i trước đó sao cho a_i + a[i]² = X => a_i = X - a[i]².
2. Thay vì tìm a_i trong mảng đã duyệt, ta dùng mảng đếm để lấy ngay số lần xuất hiện của a_i (cần nếu a_i nằm trong giới hạn 1-500).
3. Sau khi cộng dồn vào kết quả, ta cập nhật mảng đếm cho a[i] (đánh dấu a[i] có thể là a_i cho các phần tử sau). Cách này đảm bảo ta chỉ đếm các cặp (i, j) với i < j. Tuy nhiên, đề bài cho phép i = j. Ta cần xử lý riêng các cặp i = j nếu a[i] + a[i]² = X.

Cách Optimized Hash Map (Xử lý i = j)

#include <stdio.h>

#define MAX_A 501

int main() {
    int n, X;
    scanf("%d %d", &n, &X);

    int cnt[MAX_A] = {0};
    long long ans = 0;

    for (int i = 0; i < n; i++) {
        int val;
        scanf("%d", &val);

        // 1. Xử lý cặp (i, i)
        if ((long long)val + (long long)val * val == X) {
            ans++;
        }

        // 2. Xử lý các cặp (j, i) với j < i (val là a_i)
        // Cần tìm a_j sao cho a_j + val^2 = X
        int needed = X - (val * val);
        if (needed >= 1 && needed <= 500) {
            ans += cnt[needed];
        }

        // Cập nhật tần suất cho val (lưu vào mảng đếm)
        cnt[val]++;
    }

    printf("%lld\n", ans);
    return 0;
}

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

Đây là phiên bản sửa đổi của phương pháp Hash Map để đảm bảo đúng 100% với điều kiện i ≤ j.

• Logic vẫn là duyệt qua mảng một lần.
• Với mỗi phần tử val hiện tại (tương ứng chỉ số i):
  • Kiểm tra ngay lập tức nếu val đóng vai trò cả a_i và a_j (tức là val + val² == X). Nếu có, tăng biến đếm.
  • Kiểm tra xem có bao nhiêu phần tử a_j (với j < i) đã xuất hiện trước đó mà thỏa mãn a_j + val² == X. Đây chính là số lượng cặp (j, i) hợp lệ. Ta lấy giá trị này từ mảng đếm cnt.
  • Cuối cùng, cập nhật cnt[val]++ để val có thể đóng vai trò a_j cho các phần tử tiếp theo.

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

Bài học kinh nghiệm

• Bài toán có thể được biến đổi thành: Với mỗi phần tử a[j], cần tìm số lượng a[i] (i ≤ j) sao cho a[i] = X - a[j]².
• Do giá trị a[i] nhỏ (≤ 500), ta có thể sử dụng mảng đếm (frequency array) thay cho hash map để tối ưu tốc độ và bộ nhớ.
• Điều kiện i ≤ j yêu cầu ta phải xử lý cẩn thận thứ tự duyệt và cập nhật mảng đếm để tránh đếm trùng hoặc thiếu.

Lỗi thường gặp

• Quên xử lý trường hợp i = j (cặp chỉ số trùng nhau).
• Biến tràn số khi tính a[j]² (nên ép kiểu sang long long).
• Truy cập chỉ số mảng âm nếu X - a[j]² nhỏ hơn 1.