Editorial for gift: Hộp quà đặc biệt

Hiểu bài toán

Bài toán yêu cầu tính số bước cần thiết để biến đổi một số nguyên dương $n$ về 1 bằng cách áp dụng công thức lặp Collatz: nếu $n$ chẵn thì $n \to n/2$, nếu $n$ lẻ thì $n \to 3n+1$. Với $T$ test case và mỗi $n \le 10^6$, ta cần in ra số bước biến đổi cho từng test case.

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

Cách Brute Force (Simulation)

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        int count = 0;
        while (n != 1) {
            if (n % 2 == 0) {
                n /= 2;
            } else {
                n = 3 * n + 1;
            }
            count++;
        }
        cout << count << endl;
    }
    return 0;
}

• Time Complexity: O(T * K) với K là số bước trung bình (khoảng 200-300 cho n <= 10^6)
• Space Complexity: O(1)

Phương pháp này mô phỏng trực tiếp quy trình biến đổi. Với mỗi test case, ta chạy vòng lặp while thực hiện các phép tính cho đến khi n bằng 1. Do $n \le 10^6$ số bước cần thiết để về 1 khá nhỏ (dưới 500), nên phương pháp này chạy rất nhanh và không cần tối ưu hóa thêm.

Cách Dynamic Programming (Memoization)

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

const int MAX = 1000005;
int dp[MAX];

int solve(long long n) {
    if (n == 1) return 0;
    if (n < MAX && dp[n] != 0) return dp[n];

    int res;
    if (n % 2 == 0) {
        res = 1 + solve(n / 2);
    } else {
        res = 1 + solve(3 * n + 1);
    }

    if (n < MAX) dp[n] = res;
    return res;
}

int main() {
    int t;
    cin >> t;
    dp[1] = 0;
    while (t--) {
        int n;
        cin >> n;
        cout << solve(n) << endl;
    }
    return 0;
}

• Time Complexity: O(N + T) với N là giới hạn mảng (10^6)
• Space Complexity: O(N)

Approach này sử dụng kỹ thuật DP để lưu lại kết quả của các số đã tính toán. Tuy nhiên, trong bài toán này với $n \le 10^6$, phương pháp Simulation đơn giản là đủ tốt và dễ implement hơn. DP thường được dùng khi có nhiều truy vấn lặp lại hoặc số lượng test case rất lớn.

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

Bài học kinh nghiệm

• Với $n \le 10^6$, số bước để về 1 là rất nhỏ (dưới 500), nên việc mô phỏng trực tiếp là hoàn toàn khả thi.
• Biến số cần dùng kiểu long long trong quá trình tính toán vì $3n+1$ có thể vượt quá giới hạn của int trước khi chia đôi.

Lỗi thường gặp

• Quên xử lý trường hợp n = 1 (kết quả là 0) nếu dùng vòng lặp while không kiểm tra trước.
• Sử dụng kiểu int cho biến n có thể gây tràn số (overflow) khi tính $3n+1$ với n lớn (ví dụ $n = 10^6$ thì $3n+1 = 3000001$ vẫn nằm trong giới hạn int nhưng các số lớn hơn trong chuỗi Collatz có thể vượt quá).