Hiểu bài toán

Cho một dãy số gồm n số nguyên dương ai (1 ≤ ai ≤ n). Với mỗi chỉ số k từ 1 đến n, yêu cầu đếm số lượng cặp chỉ số (i, j) sao cho i < j, i ≠ k, j ≠ k và ai = aj. Nói cách khác, ta cần tính tổng số cặp giá trị bằng nhau trong dãy, sau đó loại trừ những cặp có chứa chỉ số k.

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

Cách Hash Map cơ bản

#include <iostream>
#include <unordered_map>

using namespace std;

long long C(int n) {
    return 1LL * n * (n - 1) / 2;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n; cin >> n;
    int a[n];
    unordered_map<int, int> freq;

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

    // Tính tổng số cặp toàn cục
    long long total_pairs = 0;
    for (auto x : freq) {
        total_pairs += C(x.second);
    }

    for (int k = 0; k < n; k++) {
        // Nếu loại bỏ a[k], số cặp của giá trị a[k] giảm từ C(freq[a[k]]) xuống C(freq[a[k]] - 1)
        long long ans = total_pairs - C(freq[a[k]]) + C(freq[a[k]] - 1);
        cout << ans << "\n";
    }

    return 0;
}

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

Cách tiếp cận này sử dụng một hash map (hoặc mảng tần suất) để đếm số lần xuất hiện của mỗi giá trị. Bước đầu tiên, tính tổng số cặp giá trị bằng nhau trong toàn bộ dãy. Với mỗi chỉ số k, ta chỉ cần điều chỉnh tổng số cặp bằng cách loại bỏ các cặp được tạo ra bởi giá trị tại a[k] (tức là bớt đi C(freq[a[k]]) và cộng thêm C(freq[a[k]] - 1)). Phép tính này là hằng số thời gian cho mỗi truy vấn, dẫn đến độ phức tạp tổng thể là O(n).

Cách Tối ưu với mảng tần suất

#include <iostream>
#include <vector>

using namespace std;

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

    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> count(n + 1, 0);

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

    long long total_pairs = 0;
    for (int i = 1; i <= n; ++i) {
        total_pairs += 1LL * count[i] * (count[i] - 1) / 2;
    }

    for (int k = 0; k < n; ++k) {
        int val = a[k];
        // Công thức: Tổng - Gốc + Mới
        long long ans = total_pairs - (1LL * count[val] * (count[val] - 1) / 2) + 
                        (1LL * (count[val] - 1) * (count[val] - 2) / 2);
        cout << ans << '\n';
    }

    return 0;
}

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

Đây là phiên bản tối ưu hóa của cách tiếp cận đầu tiên. Vì giá trị a_i nằm trong khoảng từ 1 đến n, ta không cần dùng hash map (có thể tốn kém chi phí thường niên) mà có thể dùng một mảng count kích thước n+1 để lưu tần suất. Logic tính toán tương tự như cách 1: tính tổng toàn cục trước, sau đó với mỗi phần tử, ta chỉ cần thực hiện công thức toán học để hiệu chỉnh kết quả. Cách này đảm bảo tốc độ chạy nhanh nhất và ổn định nhất.

Cách Thư viện chuẩn (BachNguyen)

#include<bits/stdc++.h>

using namespace std;

long long C(int n){
    return 1LL * n * (n - 1) / 2;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n; cin >> n;
    int a[n];
    map<int, int> mp;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        mp[a[i]]++;
    }

    long long sum = 0;
    for(auto x : mp){
        sum += C(x.second);
    }

    for(int i = 0; i < n; i++){
        // Tính toán tương tự: Tổng - Cũ + Mới
        long long ans = sum - C(mp[a[i]]) + C(mp[a[i]] - 1);
        cout << ans << "\n";
    }
    return 0;
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Cách tiếp cận này sử dụng std::map (cây đỏ-đen) để lưu tần suất. Về mặt logic, nó hoàn toàn giống với phương pháp hash map. Tuy nhiên, do std::map có độ phức tạp O(log n) cho mỗi thao tác chèn/cập nhật, độ phức tạp tổng thể của thuật toán sẽ là O(n log n). Trong các kỳ thi lập trình cạnh tranh, nếu giới hạn độ phức tạp cho phép O(n), nên ưu tiên sử dụng mảng hoặc unordered_map (hash map) thay vì map.

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

Bài học kinh nghiệm

• Bài toán có thể chuyển đổi từ việc tính toán lại toàn bộ cho mỗi k sang công thức hiệu chỉnh: Số cặp ban đầu - Số cặp bị mất + Số cặp mới được tạo ra (nếu có).
• Tổng số cặp của một giá trị có tần suất f là C(f) = f*(f-1)/2. Khi loại bỏ 1 phần tử, tần suất giảm xuống f-1, số cặp trở thành C(f-1).
• Vì a_i <= n, ta có thể tối ưu không gian bằng cách dùng mảng tần suất thay vì hash map.

Lỗi thường gặp

• Tràn số (Integer Overflow): Tổng số cặp có thể lên tới ~O(n^2). Khi n = 200,000, tổng số cặp có thể lên tới ~2*10^10, vượt quá giới hạn của kiểu int 32-bit. Cần dùng kiểu long long (64-bit).
• Sai công thức tính toán: Cần đảm bảo công thức là total_pairs - C(f) + C(f-1), không phải các phép tính khác.
• Lỗi nhập xuất: Do dữ liệu lớn, cần tắt đồng bộ stream (iosbase::syncwith_stdio(false); cin.tie(NULL);) để tránh TLE.