Hiểu bài toán

Xét n người tham gia sự kiện, mỗi người i có một chỉ số vui vẻ H[i]. Khi hai người i và j bắt tay nhau, họ tạo ra độ vui vẻ bằng tích H[i] * H[j]. Bài toán yêu cầu tính tổng độ vui vẻ khi tất cả mọi người đều đã bắt tay nhau (mỗi cặp đôi bắt tay đúng một lần). Nói cách khác, cần tính tổng các tích H[i] * H[j] với mọi cặp (i, j) sao cho 1 ≤ i < j ≤ n. Với n < 30000 và H[i] < 30000, ta cần một thuật toán hiệu quả.

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

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

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

int main() {
    int n;
    cin >> n;
    vector<long long> H(n);
    for(int i = 0; i < n; i++) {
        cin >> H[i];
    }
    long long total_joy = 0;
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            total_joy += H[i] * H[j];
        }
    }
    cout << total_joy << endl;
    return 0;
}

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

Cách tiếp cận 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) duy nhất. Với mỗi cặp, nó cộng dồn tích H[i] * H[j] vào biến kết quả. Phương pháp này dễ hiểu và cài đặt nhất nhưng không đủ nhanh do độ phức tạp O(n^2). Với n tối đa là 30,000, số lượng phép tính khoảng 450 triệu, vượt quá giới hạn thời gian của hầu hết các kỳ thi lập trình.

Cách Công thức toán học (Quy hoạch động / Tiền tố)

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

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

    long long n;
    cin >> n;
    vector<long long> a(n);

    // Đọc dữ liệu và tính tổng tiền tố
    long long prefix_sum = 0;
    long long res = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        // Với mỗi phần tử a[i], nó sẽ kết hợp với tất cả các phần tử đứng trước nó
        res += prefix_sum * a[i];
        prefix_sum += a[i];
    }

    cout << res;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n) (hoặc O(1) nếu không lưu mảng)

Phương pháp này dựa trên việc phân tích tổng quan hệ: Tổng = Σ{i=1}^{n} Σ{j=i+1}^{n} H[i] * H[j] Khi duyệtqua từng phần tử a[i] (từ trái sang phải), ta nhận thấy a[i] sẽ nhân với tổng của tất cả các phần tử đã xuất hiện trước đó (prefix sum). Cụ thể:

• Khi ở chỉ số i, tổng các tích tạo ra bởi a[i] và các phần tử trước nó là a[i] * (a[0] + a[1] + ... + a[i-1]).
• Ta duy trì biến prefix_sum để lưu tổng các phần tử đã duyệt.
• Biến res cộng dồn kết quả từng bước. Độ phức tạp thời gian là O(n) vì chỉ cần duyệt qua mảng một lần. Độ phức tạp không gian là O(n) nếu lưu mảng, hoặc O(1) nếu chỉ cần lưu tổng.

Cách Công thức đại số (Tổng bình phương)

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

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

    int n;
    cin >> n;
    vector<long long> H(n);
    long long sum = 0, sumSq = 0;
    for(int i = 0; i < n; i++){
        cin >> H[i];
        sum += H[i];
        sumSq += H[i] * H[i];
    }
    long long ans = (sum * sum - sumSq) / 2;
    cout << ans;
    return 0;
}

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

Phương pháp này sử dụng công thức tính tổng bình phương (Sum of Squares). Ta có tổng bình phương tổng quát: (Σ{i=1}^{n} H[i])^2 = Σ{i=1}^{n} H[i]^2 + 2 * Σ{1≤i<j≤n} H[i] * H[j] Suy ra: Σ</em>{1≤i<j≤n} H[i] * H[j] = ((Σ H[i])^2 - Σ H[i]^2) / 2</p>

Cách làm: