Hiểu bài toán

Bài toán yêu cầu tìm số bước di chuyển tối thiểu để chuyển từ trạng thái ban đầu gồm N bi xanh ở N ô đầu tiên, 1 ô trống ở giữa, và N bi đỏ ở N ô cuối cùng, sang trạng thái目标 là N bi đỏ ở N ô đầu tiên, 1 ô trống ở giữa, và N bi xanh ở N ô cuối cùng. Các quy tắc di chuyển: bi xanh chỉ được di chuyển sang trái vào ô trống, bi đỏ chỉ được di chuyển sang phải vào ô trống. Mỗi lần di chuyển, viên bi có thể nhảy qua 1 ô trống kề bên hoặc cách 1 ô (tức là khoảng cách 1 hoặc 2 đơn vị). Với N=1, ví dụ minh họa OBR -> RBO -> ROB cần 3 bước. Dữ liệu đầu vào N lên tới 10^9, yêu cầu output là kết quả chia lấy dư cho 10^9 + 7.

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

Cách Quy luật quan sát (Công thức)

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long ans = (n * (n + 2)) % 1000000007;
    cout << ans;
    return 0;
}

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

Quan sát bài toán với các giá trị N nhỏ: N=1 -> 13=3, N=2 -> 24=8, N=3 -> 3*5=15. Ta thấy quy luật kết quả là N * (N + 2). Đây là công thức dạng số học đơn giản. Do N có thể lên tới 10^9, ta chỉ cần tính công thức này và lấy dư modulo 10^9+7. Tuy nhiên, cần cẩn thận với tràn số khi nhân 2 số lớn, nên dùng phép nhân có lấy dư hoặc biến đổi kiểu dữ liệu (ví dụ dùng long long hoặc unsigned long long).

Cách Mô phỏng (Chỉ dùng cho N nhỏ)

// Pseudocode for simulation approach
// Chỉ khả thi với N <= 10 hoặc 20
deque<char> q;
// Khởi tạo: B...B O R...R
// BFS hoặc tìm đường đi ngắn nhất
// Độ phức tạp O(N!) hoặc O(2^N), không khả thi với N lớn

• Time Complexity: O(N!) - Rất chậm
• Space Complexity: O(N)

Với N lớn, việc mô phỏng toàn bộ trạng thái là bất khả thi do số lượng trạng thái quá lớn (C(2N, N)). Tuy nhiên, với N rất nhỏ (ví dụ N=1, 2), ta có thể dùng thuật toán tìm đường đi ngắn nhất (BFS) trên đồ thị các trạng thái để xác minh công thức. Các bước BFS sẽ xem mỗi trạng thái là một node và thực hiện các bước di chuyển hợp lệ. Đây là cách tiếp cận brute-force để tìm quy luật, không phải cách giải cho N lớn.

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

Bài học kinh nghiệm

• Bài toán có quy luật toán học đơn giản: Kết quả = N * (N + 2).
• Với N lớn, các phương pháp mô phỏng hay quy hoạch động đều không khả thi, buộc phải dùng công thức trực tiếp.
• Bài toán về bản chất là biến đổi chuỗi kí tự theo quy tắc c cụ thể, nhưng tổng số bước tuân theo quy luật hình học.

Lỗi thường gặp

• Tràn số (Integer Overflow): N có thể lên tới 10^9, khi nhân N*(N+2) sẽ vượt quá giới hạn của kiểu int hoặc long long (32-bit). Cần sử dụng 64-bit integer (long long) và thực hiện phép nhân có lấy dư (modular multiplication) hoặc chia đôi trước khi nhân nếu chia hết.
• Sai quy luật: Có thể nhầm lẫn với các công thức khác như N^2, N*(N-1)... Cần kiểm tra kỹ với các giá trị mẫu (N=1, N=2).
• Bỏ qua quy tắc di chuyển: Nếu tính toán theo cách khác (ví dụ đếm số bước tối thiểu cho từng con vịt), có thể ra sai đáp án nếu không để ý quy tắc bi xanh chỉ đi trái, bi đỏ chỉ đi phải và khoảng cách di chuyển.