Editorial for tribo: Dãy số Tribonacci

Hiểu bài toán

Bài toán yêu cầu tìm số tribonacci đầu tiên lớn hơn hoặc bằng n. Dãy số tribonacci được định nghĩa: a0 = 0, a1 = 0, a2 = 1, và với k >= 3 thì an = a(n-1) + a(n-2) + a(n-3). Với mỗi test case (tối đa 100 test), input là một số nguyên n (0 <= n <= 10^9), output là số tribonacci đầu tiên >= n.

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

Cách Precompute (Mảng trước)

#include <stdio.h>

int main() {
    long long a[70];
    a[0] = a[1] = 0;
    a[2] = 1;
    for(int i = 3; i < 70; i++){
        a[i] = a[i-1] + a[i-2] + a[i-3];
    }
    int n;
    while(scanf("%d", &n) != -1){
        for(int i = 0; i < 70; i++){
            if(a[i] >= n){
                printf("%lld\n", a[i]);
                break;
            }
        }
    }
    return 0;
}

• Time Complexity: O(1) per query (sau O(70) precompute)
• Space Complexity: O(1) (khoảng 70 phần tử)

Các giải pháp được cung cấp (Solution 1, 2, 3) đều đi theo hướng này. Vì n <= 10^9, ta chỉ cần precompute dãy tribonacci trước. Dãy này tăng rất nhanh, chỉ cần khoảng 50-60 phần tử là vượt quá 10^9. Ta tạo mảng chứa các số tribonacci, sau đó với mỗi query n, chỉ cần duyệt mảng từ đầu để tìm số tribonacci đầu tiên >= n.

Cách Binary Search (Tìm kiếm nhị phân)

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

int main() {
    vector<long long> tribo;
    tribo.push_back(0);
    tribo.push_back(0);
    tribo.push_back(1);
    while (tribo.back() < 1e9) {
        int sz = tribo.size();
        long long next_val = tribo[sz-1] + tribo[sz-2] + tribo[sz-3];
        tribo.push_back(next_val);
    }

    int n;
    while (cin >> n) {
        auto it = lower_bound(tribo.begin(), tribo.end(), n);
        cout << *it << endl;
    }
    return 0;
}

• Time Complexity: O(log K) per query (K là kích thước mảng ~40)
• Space Complexity: O(K)

Sau khi precompute dãy tribonacci, ta có thể sử dụng thuật toán tìm kiếm nhị phân (lower_bound) để tìm số tribonacci >= n nhanh hơn. Tuy nhiên, do kích thước mảng rất nhỏ (~40), sự cải thiện về tốc độ so với duyệt tuần tự là không đáng kể, nhưng đây là một cách tiếp cận tổng quát hơn cho các bài toán tương tự.

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

Bài học kinh nghiệm

• Dãy tribonacci tăng rất nhanh (tốc độ exponential), số lượng phần tử cần tính để vượt quá giới hạn input 10^9 là rất nhỏ (chỉ khoảng 40-50 phần tử).
• Với số lượng test nhỏ (<= 100), việc duyệt mảng trực tiếp (O(K)) hoàn toàn chấp nhận được và dễ implement.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu quá nhỏ (ví dụ: int) có thể gây tràn số (overflow) khi tính toán các số tribonacci lớn hơn 10^9. Nên dùng long long (trong C/C++).
• Quên xử lý trường hợp n = 0 hoặc n = 1 (dù logic duyệt mảng chuẩn xác vẫn trả về đúng, nhưng cần hiểu rõ dãy bắt đầu từ 0, 0, 1).