Hiểu bài toán

Bài toán yêu cầu tính tổng dãy调和级数 (Harmonic Series) $Sn = \sum{i=1}^{n} \frac{1}{i}$ cho $T$ test case khác nhau với $n$ lên tới $10^6$. Với mỗi test case, in ra kết quả làm tròn đến 5 chữ số thập phân. Do số lượng test case lớn ($T \le 10^5$) và giới hạn $n$ cố định ($n \le 10^6$), ta cần một phương pháp xử lý trước (preprocessing) để trả lời mỗi test case trong thời gian O(1).

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

Cách Brute Force

#include <stdio.h>

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        double sum = 0.0;
        for (int i = 1; i <= n; i++) {
            sum += 1.0 / i;
        }
        printf("%.5lf\n", sum);
    }
    return 0;
}

• Time Complexity: O(T * n) ~ $10^{11}$ operations
• Space Complexity: O(1)

Phương pháp này tính lại tổng từ đầu cho mỗi test case. Với $T=10^5$ và $n=10^6$, tổng số phép tính là $10^{11}$, vượt quá giới hạn thời gian (thường là $10^8$ operations/giây). Do đó, phương pháp này sẽ bị TLE (Time Limit Exceeded).

Cách Precomputation (Prefix Sum)

#include <stdio.h>

#define MAX 1000000
double prefix[MAX + 1];

int main() {
    int T, n;

    // Tien xu ly: tinh toan truoc tat ca cac tong
    prefix[0] = 0.0;
    for (int i = 1; i <= MAX; i++) {
        prefix[i] = prefix[i - 1] + 1.0 / i;
    }

    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        // Tra loi moi test case trong O(1)
        printf("%.5lf\n", prefix[n]);
    }

    return 0;
}

• Time Complexity: O(MAX + T) ~ $10^6 + 10^5$
• Space Complexity: O(MAX) ~ $10^6$

Đây là giải pháp tối ưu. Ta利用了 $n$ có giới hạn tối đa là $10^6$. Ta chạy một vòng lặp từ 1 đến $10^6$ để tính mảng cộng dồn (prefix sum) các phân số. $prefix[i]$ lưu giá trị của $S_i$. Mỗi test case chỉ mất O(1) để truy vấn giá trị đã được tính sẵn trong mảng. Thời gian chạy tổng thể nhanh enough để thỏa mãn giới hạn.

Cách Optimization (Dynamic Array)

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n;
    scanf("%d", &n);
    int a[n];
    int max = 0;

    // Doc cac test case va tim max
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        if (a[i] > max) max = a[i];
    }

    // Cap phat dong theo so nong nhat
    double *p = (double*)malloc((max + 1) * sizeof(double));
    p[0] = 0;
    for (int i = 1; i <= max; i++) {
        p[i] = p[i - 1] + 1.0 / i;
    }

    for (int i = 0; i < n; i++) {
        printf("%.5lf\n", p[a[i]]);
    }

    free(p);
    return 0;
}

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

Giải pháp này đọc hết các test case vào, tìm giá trị $n$ lớn nhất, sau đó mới cấp phát bộ nhớ và tính toán. Nó tiết kiệm bộ nhớ hơn một chút so với giải pháp cố định $MAX=10^6$ nếu các test case đều nhỏ. Tuy nhiên, trong bài này $n$ có thể lên tới $10^6$ nên độ phức tạp về thời gian và không gian tương đương với giải pháp Precomputation.

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

Bài học kinh nghiệm

• Bài toán có nhiều test case nhưng $n$ bị giới hạn ở $10^6$. Đây là dấu hiệu cho thấy nên dùng kỹ thuật tiền xử lý (Precomputation).
• Sử dụng mảng cộng dồn (Prefix Sum Array) để trả lời truy vấn trong thời gian O(1).
• Kiểu dữ liệu double ở C/C++ có độ chính xác đủ để tính tổng dãy调和级数 lên tới $10^6$ mà sai số không đáng kể cho yêu cầu làm tròn 5 chữ số thập phân.

Lỗi thường gặp

• Sử dụng thuật toán O(T*n)導致 TLE.
• Quên chuyển đổi sang số thực khi tính toán (ví dụ: viết 1/i thay vì 1.0/i), dẫn đến chia nguyên và kết quả sai.
• Làm tròn sai cách hoặc sai thứ tự in nếu không dùng định dạng %.5lf.
• Tràn số nếu dùng kiểu int để lưu tổng (nhưng bài này dùng double nên không lo).