Editorial for tabwalk: Chỉ đường Robot

Hiểu bài toán

Robot bắt đầu tại ô (1, 1) trên một bảng vô hạn, tại ô (i, j) giá trị là i * j. Robot chỉ di chuyển sang các ô kề cạnh (trên, dưới, trái, phải). Yêu cầu tìm số bước di chuyển ít nhất để đến một ô có giá trị bằng N cho trước (1 ≤ N ≤ 10^12). Số bước từ (1, 1) đến (i, j) là (i - 1) + (j - 1).

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

Cách Duyệt qua các ước số

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

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

    ll N;
    cin >> N;

    ll ans = LLONG_MAX;

    for (ll i = 1; i * i <= N; i++){
        if (N % i == 0){
            ll j = N / i;
            ll steps = (i - 1) + (j - 1);
            ans = min(ans, steps);
        }
    }
    cout << ans;
    return 0;
}

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

Giả sử robot đi đến ô (i, j) có giá trị i * j = N. Khi đó i và j là hai ước số của N. Số bước cần thiết là (i - 1) + (j - 1). Để tìm số bước nhỏ nhất, ta cần tìm cặp ước (i, j) sao cho tổng (i + j) nhỏ nhất.

Thuật toán:

1. Khởi tạo kết quả ans với giá trị vô cùng lớn.
2. Duyệt qua tất cả các số i từ 1 đến sqrt(N).
3. Nếu i là ước của N (tức N % i == 0), thì j = N / i cũng là một ước.
4. Tính số bước (i - 1) + (j - 1) và cập nhật ans nếu nhỏ hơn.
5. In ra ans.

Vì i và j là ước của N, nên i * j = N. Việc duyệt đến sqrt(N) là đủ để xét hết các cặp ước (mỗi cặp ước (i, j) tương ứng với một cặp (j, i)).

Cách Tối ưu hóa duyệt

#include <bits/stdc++.h>
using namespace std;
long long N;
int main(){
    cin >> N;
    long long res = LLONG_MAX;
    for(long long d = 1; d * d <= N; d++){
        if(N % d == 0){
            long long i = d;
            long long j = N / d;
            res = min(res, i + j - 2);
        }
    }
    cout << res << endl;
    return 0;
}

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

Đây là cách tiếp cận tương tự như cách 1, nhưng được trình bày ngắn gọn hơn và là lời giải chính xác cho bài toán này.

Ý tưởng cốt lõi:

• Bài toán quy về tìm hai số nguyên dương i, j sao cho i * j = N và i + j là nhỏ nhất.
• Vì i + j nhỏ nhất khi i và j gần nhau nhất, nên ta chỉ cần duyệt qua các ước i nhỏ hơn hoặc bằng sqrt(N).

Cách hoạt động:

• Duyệt d từ 1 đến sqrt(N).
• Nếu d chia hết N, thì d và N/d là một cặp ước.
• Số bước là d + N/d - 2.
• Cập nhật kết quả.

Ví dụ với N=12: Các ước: (1,12) -> 11 bước; (2,6) -> 6 bước; (3,4) -> 5 bước. (4,3) và (6,2) đã xét ở trên. Kết quả là 5.

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

Bài học kinh nghiệm

• Bài toán có thể biến đổi thành bài toán tìm cặp ước (i, j) của N sao cho tổng i + j là nhỏ nhất.
• Số bước từ (1, 1) đến (i, j) là quãng đường Manhattan: |i-1| + |j-1| = i + j - 2 (vì i, j >= 1).
• Với ràng buộc N <= 10^12, thuật toán O(sqrt(N)) là hoàn toàn khả thi (sqrt(10^12) = 10^6).

Lỗi thường gặp

• Sử dụng biến kiểu int cho N và các biến vòng lặp, dẫn đến tràn số (overflow) vì N có thể lên tới 10^12. Cần dùng long long.
• Bỏ qua trường hợp i = j (khi N là số chính phương), tuy nhiên thuật toán duyệt đến sqrt(N) vẫn xử lý đúng.
• Quên cập nhật kết quả cho trường hợp i=1, j=N (số bước rất lớn, nhưng vẫn cần xét để đảm bảo logic nếu không có ước nào khác).