Hiểu bài toán

Bài toán yêu cầu tìm giá trị lớn nhất trong dãy số A được định nghĩa đệ quy như sau:

• A[0] = 0
• A[1] = 1
• A[2i] = A[i]
• A[2i + 1] = A[i] + A[i + 1] Cho trước số nguyên dương N, ta cần tìm max(A[1], A[2], ..., A[N]). Với T test cases (T <= 10^5) và N <= 10^5, ta cần một giải pháp hiệu quả để trả lời nhiều truy vấn.

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

Cách Tính toán trực tiếp theo công thức đệ quy

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

long long getA(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (n % 2 == 0) return getA(n / 2);
    return getA(n / 2) + getA(n / 2 + 1);
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        long long max_val = 0;
        for (int i = 1; i <= n; i++) {
            max_val = max(max_val, getA(i));
        }
        cout << max_val << "\n";
    }
    return 0;
}

• Time Complexity: O(N * log N) mỗi test case (Quá chậm)
• Space Complexity: O(log N) (Stack)

Giải pháp này tính giá trị A[i] cho mỗi i từ 1 đến N bằng cách gọi hàm đệ quy. Độ phức tạp tính toán A[i] là O(log i) do mỗi bước chia đôi chỉ số. Với N test case, độ phức tạp tổng thể là quá lớn, dẫn đến TLE (Time Limit Exceeded).

Cách Precompute (Tiền tính) toàn bộ

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

const int MAXN = 100005;
long long A[MAXN];
long long maxA[MAXN];

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

    // Khoi tao
    A[0] = 0;
    A[1] = 1;
    maxA[0] = 0;
    maxA[1] = 1;

    // Tinh toan day A va ket qua cho den MAXN
    for (int i = 2; i < MAXN; i++) {
        if (i % 2 == 0) {
            A[i] = A[i / 2];
        } else {
            A[i] = A[i / 2] + A[i / 2 + 1];
        }
        // Luon luon cap nhat max len den i
        maxA[i] = max(maxA[i - 1], A[i]);
    }

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << maxA[n] << "\n";
    }
    return 0;
}

• Time Complexity: O(MAXN) tiền tính + O(1) mỗi truy vấn
• Space Complexity: O(MAXN)

Đây là cách tiếp cận được sử dụng trong các bài nộp accepted. Ta tính toán mảng A[] và mảng maxA[] (mảng tiền tố tối đa) cho tất cả các giá trị N có thể tối đa (100,000) trước khi xử lý các test case. Khi có truy vấn, chỉ cần trả lời maxA[N] ngay lập tức. Độ phức tạp không gian là O(MAXN) nhưng nằm trong giới hạn cho phép.

Cách Optimized Precompute (Giảm bộ nhớ)

#include <bits/stdc++.h>
using namespace std;

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

    const int MAXN = 100000;
    static int A[MAXN + 1]; // Dùng mảng tĩnh hoặc vector
    static int maxA[MAXN + 1];

    A[0] = 0;
    A[1] = 1;
    maxA[0] = 0;
    maxA[1] = 1;

    for (int i = 2; i <= MAXN; i++) {
        if (i % 2 == 0) A[i] = A[i / 2];
        else A[i] = A[i / 2] + A[i / 2 + 1];
        maxA[i] = max(maxA[i - 1], A[i]);
    }

    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        cout << maxA[N] << '\n';
    }
    return 0;
}

• Time Complexity: O(MAXN) tiền tính + O(1) mỗi truy vấn
• Space Complexity: O(MAXN)

Giải pháp này giống với Approach 2 nhưng nhấn mạnh vào việc tối ưu hóa bộ nhớ và tốc độ bằng cách khai báo mảng static và sử dụng fast I/O. Việc tiền tính toàn bộ kết quả cho N_max (100,000) cho phép xử lý hàng trăm nghìn truy vấn trong thời gian rất ngắn.

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

Bài học kinh nghiệm

• Cấu trúc đệ quy của dãy số A giống với cấu trúc của cây đệ quy (binary tree), cho phép tính toán nhanh chóng bằng cách chia đôi.
• Vì số lượng truy vấn T lớn và N bị giới hạn (10^5), phương pháp tiền tính (precomputation) là tối ưu nhất để trả lời truy vấn O(1).
• Giá trị của A[i] tăng chậm (độ lớn xấp xỉ log(i) hoặc i/2), nhưng để tìm max thì ta cần duyệt qua tất cả các phần tử trước đó.

Lỗi thường gặp

• Sử dụng đệ quy không nhớ (memoization) hoặc tính lại mỗi lần cho mỗi test case sẽ gây quá thời gian.
• Quên cập nhật giá trị maxA[i] dựa trên maxA[i-1], dẫn đến kết quả sai nếu giá trị lớn nhất nằm ở một chỉ số nhỏ hơn N.
• Lỗi tràn số (Integer Overflow): Dãy A có thể vượt quá 2^31-1. Nên dùng kiểu dữ liệu lớn hơn (long long) cho mảng A.