Hướng dẫn cho Orange Contest #02 - Lối Thoát Không Gian

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Tóm tắt đề bài

Cho một hệ thống gồm \(n\) trạm dịch chuyển. Chi phí di chuyển giữa hai trạm \(u\) và \(v\) bất kỳ được tính bằng công thức:

\[w(u, v) = \frac{\max(u, v)}{\gcd(u, v)}\]

Yêu cầu là tìm đường đi ngắn nhất (tổng chi phí nhỏ nhất) từ trạm xuất phát \(a\) đến trạm đích \(b\).

Phân tích

  • Điều kiện: \(2 \le n \le 10^9\), \(1 \le a, b \le n, a \neq b\).
  • Nhận xét quan trọng:
    • Nhìn vào công thức chi phí \(w(u, v) = \frac{\max(u, v)}{\gcd(u, v)}\), ta thấy nếu gọi \(g = \gcd(a, b)\), ta có thể chia cả \(a\) và \(b\) cho \(g\) mà không làm thay đổi bản chất cấu trúc tỷ lệ của các bước nhảy. Cụ thể, bài toán thực chất chỉ phụ thuộc vào các ước số của \(a\) và \(b\).
    • Do \(n\) rất lớn (\(10^9\)), ta không thể dùng các thuật toán đồ thị thông thường trên toàn bộ tập đỉnh từ \(1\) đến \(n\). Tuy nhiên, ta nhận thấy các trạm trung gian tối ưu thường có mối liên hệ về ước số với \(a\) và \(b\).

Hướng giải quyết (Tối ưu)

Ý tưởng chính

  1. Rút gọn: Đặt \(g = \gcd(a, b)\), ta chia \(a\) và \(b\) cho \(g\). Khi đó \(\gcd(a, b) = 1\). Việc dịch chuyển từ trạng thái \((x, y)\) về \((a, b)\) có thể được quy hoạch động trên tập các ước số.
  2. Liệt kê ước số:
    • Tìm tất cả các ước số của \(a\) (lưu vào danh sách d1) và các ước số của \(b\) (lưu vào danh sách d2), sau đó sắp xếp tăng dần.
  3. Quy hoạch động (DP):
    • Gọi \(dp[x][y]\) là chi phí nhỏ nhất để đi từ trạng thái tương ứng với ước thứ \(x\) của \(a\) và ước thứ \(y\) của \(b\).
    • Ta sử dụng kỹ thuật nhớ kết quả (Memoization) kết hợp với hàm đệ quy để chuyển trạng thái hiệu quả.
    • Tại mỗi bước, ta thử nhảy qua các ước số tương thích để tối ưu hóa tổng chi phí.

Độ phức tạp

  • Thời gian: Phụ thuộc vào số lượng ước số của \(a\) và \(b\). Vì \(a, b \le 10^9\), số lượng ước số là rất nhỏ (tối đa vài trăm ước), giúp thuật toán chạy cực kỳ nhanh và vượt qua giới hạn thời gian.
  • Bộ nhớ: \(O(d_1 \times d_2)\) với \(d_1, d_2\) lần lượt là số lượng ước của \(a\) và \(b\).

Code tham khảo

C++
C++
#include <bits/stdc++.h>

using namespace std;

#define int long long
const int INF = 1000000000000007LL;

void solve() {
    int n, a, b;
    cin >> n >> a >> b;

    int g = gcd(a, b);
    a /= g;
    b /= g;

    vector<int> d1, d2;
    for (int i = 1; i * i <= a; i++) {
        if (a % i == 0) {
            d1.push_back(i);
            if (i * i != a) {
                d1.push_back(a / i);
            }
        }
    }

    for (int i = 1; i * i <= b; i++) {
        if (b % i == 0) {
            d2.push_back(i);
            if (i * i != b) {
                d2.push_back(b / i);
            }
        }
    }

    sort(d1.begin(), d1.end());
    sort(d2.begin(), d2.end());

    int sz1 = d1.size();
    int sz2 = d2.size();

    vector<vector<int>> to_d1(sz1, vector<int>(sz1, -1));
    for (int i = 0; i < sz1; i++) {
        int u = 0;
        for (int j = i; j >= 0; j--) {
            while (u < i && d1[i] > d1[u] * d1[j]) {
                u++;
            }
            if (d1[i] % d1[j] == 0 && d1[i] / d1[j] == d1[u]) {
                to_d1[i][j] = u;
            }
        }
    }

    vector<vector<int>> to_d2(sz2, vector<int>(sz2, -1));
    for (int i = 0; i < sz2; i++) {
        int u = 0;
        for (int j = i; j >= 0; j--) {
            while (u < i && d2[i] > d2[u] * d2[j]) {
                u++;
            }
            if (d2[i] % d2[j] == 0 && d2[i] / d2[j] == d2[u]) {
                to_d2[i][j] = u;
            }
        }
    }

    vector<vector<int>> dels_d1(sz1);
    for (int i = 0; i < sz1; i++) {
        for (int j = 0; j <= i; j++) {
            if (d1[i] % d1[j] == 0) {
                dels_d1[i].emplace_back(j);
            }
        }
    }

    vector<vector<int>> dels_d2(sz2);
    for (int i = 0; i < sz2; i++) {
        for (int j = 0; j <= i; j++) {
            if (d2[i] % d2[j] == 0) {
                dels_d2[i].emplace_back(j);
            }
        }
    }

    vector<vector<int>> dp(sz1, vector<int>(sz2, -1));

    auto go = [&](auto&& self, int x, int y) -> int {
        if (dp[x][y] != -1) {
            return dp[x][y];
        }
        if (x == 0 && y == 0) {
            return 0;
        }
        dp[x][y] = INF;

        for (int dx : dels_d1[x]) {
            for (int dy : dels_d2[y]) {
                if (dx == 0 && dy == 0) {
                    continue;
                }
                dp[x][y] = min(dp[x][y], max(d1[dx], d2[dy]) + self(self, to_d1[x][dx], to_d2[y][dy]));
            }
        }
        return dp[x][y];
    };

    cout << go(go, sz1 - 1, sz2 - 1) << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tests = 1;
    while (tests--) {
        solve();
    }
    return 0;
}
Python
Python
import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    n = int(data[0])
    a = int(data[1])
    b = int(data[2])

    import math
    g = math.gcd(a, b)
    a //= g
    b //= g

    d1 = []
    i = 1
    while i * i <= a:
        if a % i == 0:
            d1.append(i)
            if i * i != a:
                d1.append(a // i)
        i += 1

    d2 = []
    i = 1
    while i * i <= b:
        if b % i == 0:
            d2.append(i)
            if i * i != b:
                d2.append(b // i)
        i += 1

    d1.sort()
    d2.sort()

    sz1 = len(d1)
    sz2 = len(d2)

    INF = 10**18

    # Python implementation of the dynamic programming approach can follow a similar structure using memoization.
    # Due to recursive depth and performance considerations in Python, C++ is typically preferred for this complexity.

solve()

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.