Editorial for scbn2: Số cặp bằng nhau 2

Hiểu bài toán

Bài toán yêu cầu đếm số lượng các cặp chỉ số (i, j) sao cho i < j và a[i] = a[j] trong một dãy số gồm n phần tử. Nói cách khác, chúng ta cần đếm tổng số cặp phần tử bằng nhau trong dãy. Với giới hạn n ≤ 10^5 và giá trị phần tử a_i ≤ 5*10^4, giải thuật cần chạy đủ nhanh.

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

Cách Brute Force (Đối sánh mọi cặp)

#include <stdio.h>

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

    long long count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] == a[j]) {
                count++;
            }
        }
    }
    printf("%lld", count);
    return 0;
}

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

Giải thuật 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) với i < j. Nếu a[i] == a[j], ta tăng biến đếm. Cách này rất dễ hiểu nhưng hiệu năng cực kỳ kém với n lớn (ví dụ n=10^5, số phép so sánh ~5*10^9), dẫn đến thời gian chạy quá giới hạn (TLE).

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

#include <stdio.h>
#include <string.h>

#define MAX_VAL 50000

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

    // Mảng đếm tần suất, khởi tạo bằng 0
    // Giá trị a_i max là 50000 nên cần mảng kích thước 50001
    int freq[MAX_VAL + 1] = {0};

    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        freq[x]++;
    }

    long long count = 0;
    for (int i = 0; i <= MAX_VAL; i++) {
        if (freq[i] >= 2) {
            // Công thức tính số cặp: C(k, 2) = k*(k-1)/2
            count += (long long)freq[i] * (freq[i] - 1) / 2;
        }
    }
    printf("%lld", count);
    return 0;
}

• Time Complexity: O(n + V)
• Space Complexity: O(V)

Thay vì so sánh các cặp, ta đếm số lần xuất hiện của mỗi giá trị (tần suất) bằng một mảng. Với mỗi giá trị x có tần suất k, số cặp bằng nhau tạo thành bởi các phần tử x là tổ hợp chập 2 của k, tức là k*(k-1)/2. Ta cộng dồn kết quả cho tất cả các giá trị. V là giá trị lớn nhất của phần tử (50000). Độ phức tạp O(n + V) rất tốt cho n ≤ 10^5.

Cách Optimized Counting (Tối ưu bộ nhớ)

#include <stdio.h>

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

    // Khai báo mảng đếm tần suất ngay trong hàm main
    // Kích thước 50001 là đủ, các phần tử mặc định là 0
    int dp[50001] = {0};

    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        dp[x]++; // Đọc và đếm luôn, không cần mảng trung gian
    }

    long long count = 0;
    for (int i = 0; i <= 50000; i++) {
        if (dp[i] >= 2) {
            // Tính toán số cặp
            count += 1LL * dp[i] * (dp[i] - 1) / 2;
        }
    }
    printf("%lld", count);
    return 0;
}

• Time Complexity: O(n + 50000)
• Space Complexity: O(50001)

Đây là phiên bản tối ưu của phương pháp đếm tần suất. Thay vì dùng mảng toàn cục hoặc mảng động lớn, ta dùng mảng c cục bộ với kích thước cố định 50001. Quan trọng hơn, ta không cần lưu trữ mảng đầu vào a[] (tốn O(n) bộ nhớ) mà có thể đọc từng số và cập nhật mảng đếm ngay lập tức. Đây là cách tiếp cận hiệu quả và phổ biến nhất cho bài toán này.

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

Bài học kinh nghiệm

• Bài toán đếm cặp bằng nhau có thể quy về bài toán đếm tần suất. Nếu một phần tử xuất hiện k lần, nó đóng góp k*(k-1)/2 cặp.
• Với dữ liệu nhập có giá trị nhỏ (≤ 50000), việc dùng mảng trực tiếp (Direct Addressing) nhanh và hiệu quả hơn nhiều so với các cấu trúc dữ liệu phức tạp như map hay hash table.

Lỗi thường gặp

• Sai kích thước mảng đếm tần suất: Nếu giá trị a_i lên tới 50000, mảng cần kích thước tối thiểu là 50001 (chỉ số từ 0 đến 50000).
• Tràn số nguyên: Biến đếm kết quả phải là long long vì số cặp có thể lên tới ~(10^5 * 10^4)/2 ≈ 5*10^9~, lớn hơn giới hạn của int (2*10^9).
• Phép chia trong công thức tổ hợp: Nên thực hiện phép nhân trước rồi chia, và ép kiểu sang long long (ví dụ: (long long)k * (k-1) / 2) để tránh lỗi số học khi k lớn.