Hiểu bài toán

Bài toán yêu cầu tìm số bước tối thiểu để chuyển N đĩa từ cột A sang cột B theo quy tắc của bài toán Tháp Hà Nội Ngược (Reverse Tower of Hanoi). Trong biến thể này, các cột được sắp xếp thành một hình tròn theo thứ tự A -> B -> C -> A. Quy tắc di chuyển chỉ cho phép chuyển một đĩa từ cột hiện tại sang cột bên cạnh theo chiều NGƯỢC chiều kim đồng hồ (A -> C, C -> B, B -> A).Đây là một biến thể tuyến tính hóa của bài toán tháp Hà Nội. Nếu coi các cột là các vị trí 0, 1, 2 tương ứng với A, B, C, thì quy tắc di chuyển cho phép di chuyển từ i sang (i + 2) % 3 (vì A(0) sang C(2) là +2 mod 3, C(2) sang B(1) là +2 mod 3, B(1) sang A(0) là +2 mod 3). Mục tiêu là chuyển toàn bộ đĩa từ A(0) sang B(1).

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

Cách Quy hoạch động (Dynamic Programming)

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

const long long MOD = 1e9 + 7;
const int MAXN = 10010;

long long dp[2][MAXN];

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

    int n;
    cin >> n;

    // dp[0][x]: số bước để chuyển x đĩa từ A sang C
    // dp[1][x]: số bước để chuyển x đĩa từ A sang B
    // Base case:
    dp[0][1] = 1; // Chuyển 1 đĩa từ A sang C (A -> C)
    dp[1][1] = 2; // Chuyển 1 đĩa từ A sang B (A -> C -> B)

    for (int i = 2; i <= n; i++) {
        // Công thức quy hoạch động:
        // dp[0][i] = 2 * dp[1][i-1] + 1
        // Giải thích: Để chuyển i đĩa từ A sang C:
        // 1. Chuyển i-1 đĩa từ A sang B (dp[1][i-1])
        // 2. Chuyển đĩa i từ A sang C (1 bước)
        // 3. Chuyển i-1 đĩa từ B sang C (dp[1][i-1])
        dp[0][i] = (2 * dp[1][i - 1] + 1) % MOD;

        // dp[1][i] = dp[0][i-1] + 2 * dp[1][i-1] + 2
        // Giải thích: Để chuyển i đĩa từ A sang B:
        // 1. Chuyển i-1 đĩa từ A sang C (dp[0][i-1])
        // 2. Chuyển đĩa i từ A sang C (1 bước)
        // 3. Chuyển i-1 đĩa từ C sang B (dp[1][i-1])
        // 4. Chuyển đĩa i từ C sang B (1 bước)
        // 5. Chuyển i-1 đĩa từ B sang A (dp[1][i-1])
        // 6. Chuyển đĩa i từ C sang B (phải đi qua A, 2 bước: C->A, A->B)
        // 7. Chuyển i-1 đĩa từ A sang B (dp[1][i-1])
        // Thực tế cách phân tích khác: 
        // dp[1][i] = dp[0][i-1] + 1 + dp[1][i-1] + 1 + dp[1][i-1]
        // Đơn giản hóa: dp[1][i] = dp[0][i-1] + 2*dp[1][i-1] + 2
        dp[1][i] = (dp[0][i - 1] + 2 * dp[1][i - 1] + 2) % MOD;
    }

    cout << dp[1][n] << endl;

    return 0;
}

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

Approach này sử dụng quy hoạch động để tính số bước di chuyển. Ta cần 2 trạng thái cho mỗi số lượng đĩa: chuyển từ A sang C và chuyển từ A sang B.

• dp[0][k]: số bước để chuyển k đĩa từ A sang C.
• dp[1][k]: số bước để chuyển k đĩa từ A sang B.

Công thức: dp[0][i] = 2 * dp[1][i-1] + 1 Để chuyển i đĩa từ A sang C:

1. Chuyển i-1 đĩa từ A sang B (cần dp[1][i-1] bước).
2. Chuyển đĩa i từ A sang C (1 bước).
3. Chuyển i-1 đĩa từ B sang C (cần dp[1][i-1] bước). Tổng: 2 * dp[1][i-1] + 1.

dp[1][i] = dp[0][i-1] + 2 * dp[1][i-1] + 2 Để chuyển i đĩa từ A sang B:

1. Chuyển i-1 đĩa từ A sang C (dp[0][i-1] bước).
2. Chuyển đĩa i từ A sang C (1 bước).
3. Chuyển i-1 đĩa từ C sang B (dp[1][i-1] bước).
4. Chuyển đĩa i từ C sang B (1 bước).
5. Chuyển i-1 đĩa từ B sang A (dp[1][i-1] bước).
6. Chuyển đĩa i từ B sang A (không thể trực tiếp, phải qua C: B->A->C->B, nhưng ta đang ở B và muốn đưa nó xuống A? Không, ta đang ở bước 4 là đã ở B. Ta cần dọn đường cho các đĩa nhỏ hơn từ A lên B. Trong bước 5, ta chuyển các đĩa nhỏ từ B về A. Sau đó ta cần đưa đĩa i (đang ở B) xuống dưới các đĩa nhỏ hơn? Không, đĩa i là to nhất.

Phân tích lại: Để chuyển i đĩa từ A sang B:

1. Chuyển i-1 đĩa từ A sang C (dp[0][i-1] bước).
2. Chuyển đĩa i từ A sang C (1 bước).
3. Chuyển i-1 đĩa từ C sang B (dp[1][i-1] bước).
4. Chuyển đĩa i từ C sang B (1 bước). Lúc này i-1 đĩa đang ở B, đĩa i cũng ở B nhưng ở dưới. Ta cần đưa i-1 đĩa lên trên i.
5. Chuyển i-1 đĩa từ B sang A (dp[1][i-1] bước).
6. Chuyển đĩa i từ B sang C (2 bước: B->A->C).
7. Chuyển i-1 đĩa từ A sang B (dp[1][i-1] bước).
8. Chuyển đĩa i từ C sang B (1 bước).

Công thức trong code là dp[1][i] = dp[0][i-1] + 2 * dp[1][i-1] + 2. Có vẻ thiếu một đoạn dp[1][i-1] nữa?

Thực tế, lời giải trong code là: dp[1][i] = (dp[0][i-1] + 2 * dp[1][i-1] + 2) % MOD; Điều này có nghĩa là:

• dp[0][i-1]: A -> C
• +1: A -> C (đĩa i)
• dp[1][i-1]: C -> B
• +1: C -> B (đĩa i)
• dp[1][i-1]: B -> A (chuyển các đĩa nhỏ ra đường đi)
• +1: B -> A (đĩa i)? Không.

Công thức đúng cho dp[1][i] là: dp[1][i] = dp[0][i-1] + 1 + dp[1][i-1] + 1 + dp[1][i-1] = dp[0][i-1] + 2*dp[1][i-1] + 2. Đúng là như vậy. Các bước:

1. Chuyển i-1 đĩa từ A sang C: dp[0][i-1].
2. Chuyển đĩa i từ A sang C: 1 bước.
3. Chuyển i-1 đĩa từ C sang B: dp[1][i-1].
4. Chuyển đĩa i từ C sang B: 1 bước.
5. Chuyển i-1 đĩa từ B sang A: dp[1][i-1]. Tại sao lại chuyển B sang A? Vì ta cần đưa đĩa i (đang ở B) xuống dưới cùng. Đĩa i đang ở B, các đĩa nhỏ hơn cũng ở B. Ta cần đưa các đĩa nhỏ đi chỗ khác để đĩa i có thể nằm ở dưới.

Wait, sau bước 3 và 4, ta có: i-1 đĩa ở B (đĩa i ở dưới). Ta muốn đĩa i ở dưới cùng của cột B.

• Chuyển i-1 đĩa từ B sang A: dp[1][i-1].
• Đĩa i đang ở B, muốn xuống dưới cùng? Nó đã ở dưới cùng rồi. Nhưng ta muốn nó ở A? Không.

Ta có 3 cột: A, B, C. Mục tiêu: Chuyển N đĩa từ A sang B. Quy tắc: A->C, C->B, B->A.

Giả sử ta muốn chuyển i đĩa từ X sang Y. Có 3 loại đích:

1. X -> (X+2)%3: Dễ nhất.
2. X -> (X+1)%3: Khó nhất.

Giả sử X=0 (A), Y=1 (B). dp[0][i]: 0 -> 2 (A -> C). dp[1][i]: 0 -> 1 (A -> B).

Công thức dp[0][i] = 2 * dp[1][i-1] + 1:

• Chuyển i-1 đĩa 0 -> 1 (A->B): dp[1][i-1].
• Chuyển đĩa i 0 -> 2 (A->C): 1.
• Chuyển i-1 đĩa 1 -> 2 (B->C): dp[1][i-1]. (Vì 1->2 tương tự 0->1). Đúng.

Công thức dp[1][i] = dp[0][i-1] + 2 * dp[1][i-1] + 2: Muốn chuyển i đĩa 0 -> 1.

1. Chuyển i-1 đĩa 0 -> 2 (A->C): dp[0][i-1].
2. Chuyển đĩa i 0 -> 2 (A->C): 1.
3. Chuyển i-1 đĩa 2 -> 1 (C->B): dp[1][i-1]. (Vì 2->1 tương tự 0->1).
4. Chuyển đĩa i 2 -> 1 (C->B): 1. Bây giờ i-1 đĩa và i đĩa đều ở 1. Ta cần i-1 đĩa lên trên i.
5. Chuyển i-1 đĩa 1 -> 0 (B->A): dp[1][i-1]. (1->0 tương tự 0->1).
6. Chuyển đĩa i 1 -> 0 (1->0)? Không, ta cần đưa i ra chỗ khác? Không.

Lại xem xét: Sau bước 4: i-1 đĩa ở 1, i ở 1 (dưới). Muốn i ở dưới cùng của 1. Ta có thể:

• Chuyển i-1 đĩa 1 -> 0 (dp[1][i-1]).
• Chuyển đĩa i 1 -> 0 (1). (Bây giờ i ở 0).
• Chuyển i-1 đĩa 0 -> 1 (dp[1][i-1]). (Bây giờ i-1 ở 1).
• Chuyển đĩa i 0 -> 1 (1). (Bây giờ i ở 1, ở dưới). Tổng: dp[0][i-1] + 1 + dp[1][i-1] + 1 + dp[1][i-1] + 1 + dp[1][i-1] + 1? Sai.

Ta chỉ cần i ở dưới cùng của 1. Khi i-1 đang ở 0, i ở 1. Ta cần đưa i-1 từ 0 lên 1 (trên i). dp[1][i-1] để đưa i-1 từ 0 lên 1. Tổng: dp[0][i-1] + 1 + dp[1][i-1] + 1 + dp[1][i-1]. = dp[0][i-1] + 2*dp[1][i-1] + 2. Đúng là như vậy.

Tại sao lại là dp[1][i-1] cuối cùng? Vì sau khi i ở 1 (bước 4), i-1 cũng ở 1. Ta cần di chuyển i-1 đi chỗ khác.

• i-1 đi 1 -> 0 (dp[1][i-1]).
• i ở lại 1.
• i-1 từ 0 quay lại 1 (dp[1][i-1]). Tổng cộng 2 * dp[1][i-1].

Vậy công thức là đúng.

Cách Đại số tuyến tính (Linear Algebra)

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

const long long MOD = 1e9 + 7;

// Ma trận 2x2
struct Matrix {
    long long mat[2][2];
    Matrix() {
        memset(mat, 0, sizeof(mat));
    }
};

Matrix multiply(Matrix A, Matrix B) {
    Matrix C;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                C.mat[i][j] = (C.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % MOD;
            }
        }
    }
    return C;
}

Matrix power(Matrix A, long long p) {
    Matrix res;
    res.mat[0][0] = 1; res.mat[1][1] = 1; // Ma trận đơn vị
    while (p > 0) {
        if (p & 1) res = multiply(res, A);
        A = multiply(A, A);
        p >>= 1;
    }
    return res;
}

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

    int n;
    cin >> n;

    if (n == 1) {
        cout << 2 << endl;
        return 0;
    }

    // Ta có:
    // f(n) = 2*f(n-1) + g(n-1) + 2
    // g(n) = 2*f(n-1) + g(n-1) + 1
    // Nơi f(n) là dp[1][n] (A->B), g(n) là dp[0][n] (A->C).
    // Thực tế:
    // g(n) = 2*f(n-1) + 1
    // f(n) = g(n-1) + 2*f(n-1) + 2
    // Thay g(n-1) vào:
    // f(n) = (2*f(n-2) + 1) + 2*f(n-1) + 2 = 2*f(n-1) + 2*f(n-2) + 3
    // Ta cần dãy f(n). 
    // f(1) = 2
    // f(2) = 7
    // f(3) = 2*7 + 2*2 + 3 = 14 + 4 + 3 = 21. (Matches sample).

    // Xây dựng ma trận chuyển trạng thái:
    // [ f(n) ]   = [ 2 2 3 ] [ f(n-1) ]
    // [ f(n-1)]     [ 1 0 0 ] [ f(n-2) ]
    // [ 1     ]     [ 0 0 1 ] [ 1      ]
    // Hoặc đơn giản hơn:
    // [ f(n)   ]   = [ 2 2 3 ] [ f(n-1) ]
    // [ f(n-1) ]     [ 1 0 0 ] [ f(n-2) ]
    // [ 1      ]     [ 0 0 1 ] [ 1      ]

    // Ta có:
    // f(n) = 2*f(n-1) + 2*f(n-2) + 3
    // f(n-1) = f(n-1)
    // 1 = 1

    // Ma trận:
    // [ 2 2 3 ]
    // [ 1 0 0 ]
    // [ 0 0 1 ]

    Matrix T;
    T.mat[0][0] = 2; T.mat[0][1] = 2; T.mat[0][2] = 3;
    T.mat[1][0] = 1; T.mat[1][1] = 0; T.mat[1][2] = 0;
    T.mat[2][0] = 0; T.mat[2][1] = 0; T.mat[2][2] = 1;

    // Vector ban đầu:
    // f(2) = 7
    // f(1) = 2
    // 1 = 1

    if (n == 1) { cout << 2 << endl; return 0; }
    if (n == 2) { cout << 7 << endl; return 0; }

    Matrix P = power(T, n - 2);

    // Result = P * [7, 2, 1]^T
    long long res = (P.mat[0][0] * 7 + P.mat[0][1] * 2 + P.mat[0][2] * 1) % MOD;

    cout << res << endl;

    return 0;
}

• Time Complexity: O(log N)
• Space Complexity: O(1)

Approach này sử dụng ma trận lũy thừa để tối ưu hóa tính toán. Từ kết quả của Approach 1, ta có: dp[1][n] = 2 * dp[1][n-1] + 2 * dp[1][n-2] + 3 (với dp[1][1] = 2, dp[1][2] = 7).

Đây là một phương trình truy hồi tuyến tính. Ta có thể biểu diễn nó dưới dạng ma trận:

$$ \begin{pmatrix} f(n) \\ f(n-1) \\ 1 \end{pmatrix} = \begin{pmatrix} 2 & 2 & 3 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} f(n-1) \\ f(n-2) \\ 1 \end{pmatrix} $$

Nơi f(n) là dp[1][n].

Để tính f(n), ta nhân ma trận lũy thừa T^(n-2) với vector giá trị ban đầu [f(2), f(1), 1]^T = [7, 2, 1]^T.

Phương pháp này giảm độ phức tạp thời gian từ O(N) xuống O(log N) do sử dụng lũy thừa ma trận nhanh. Đây là phương pháp tối ưu nhất về mặt lý thuyết cho các bài toán quy hoạch động tuyến tính.

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

Bài học kinh nghiệm

• Bài toán có thể được chia thành các bài toán con: chuyển k đĩa từ A sang C (trạng thái 'dễ') và từ A sang B (trạng thái 'khó').
• Các bước di chuyển có tính chất đệ quy và có thể được tổng quát hóa bằng phương trình truy hồi.
• Quy tắc di chuyển theo chu trình 3 cột (A->C->B->A) tạo ra các mô hình lặp lại.

Lỗi thường gặp

• Xác định sai công thức truy hồi, đặc biệt là số bước để chuyển đĩa to nhất trong các trường hợp phức tạp (ví dụ: phải di chuyển đĩa to ra đường vòng).
• Quên chia lấy dư khi số lượng bước quá lớn, dẫn đến tràn số (overflow).
• Lầm tưởng rằng bài toán này giống bài tháp Hà Nội kinh điển với số bước là 2^N - 1.