Editorial for oddcoin: Tiền xu

Hiểu bài toán

Bài toán yêu cầu tìm số lượng xu tối thiểu để trả đúng t đồng. Có một tập hợp các mệnh giá xu có sẵn (1, 3, 5, 10, 30, 50, 100, 300, 500, 1000, 3000, 5000, 10000, 30000, 50000) và một loại xu mới mệnh giá x. Với mỗi test case gồm x và t, ta cần tính số xu ít nhất có thể. Dữ liệu t và x có thể lên tới 2*10^9, đòi hỏi thuật toán hiệu quả.

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

Cách Quy hoạch động (chỉ dùng cho dữ liệu nhỏ)

// Chỉ khả thi với t <= 10^5
vector<int> dp(t + 1, 1e9);
dp[0] = 0;
for (int i = 1; i <= t; i++) {
    for (int v : base) if (i >= v) dp[i] = min(dp[i], dp[i - v] + 1);
    if (i >= x) dp[i] = min(dp[i], dp[i - x] + 1);
}
return dp[t];

• Time Complexity: O(t * 16)
• Space Complexity: O(t)

Sử dụng mảng dp[i] để lưu số xu tối thiểu để tạo ra số tiền i. Với mỗi số tiền i, ta thử tất cả các mệnh giá có thể trừ đi và cập nhật dp. Cách này chỉ chạy được khi t nhỏ (<= 10^5).

Cách Thử số lượng xu mới (Greedy)

ll ans = LLONG_MAX;
// Thử k xu mới, k từ 0 đến khi k*x > t
for (ll k = 0; k*x <= t; k++) {
    ll rem = t - k*x;
    ll cnt = k;
    // Dùng greedy với bộ base
    for (ll v : base) {
        cnt += rem / v;
        rem %= v;
    }
    if (rem == 0) ans = min(ans, cnt);
    if (k > ans) break; // Pruning
}
cout << ans;

• Time Complexity: O(t/x * 15)
• Space Complexity: O(1)

Phương pháp này dựa trên quan sát: nếu dùng k xu mới, số tiền còn lại (t - k*x) sẽ được tạo bởi các mệnh giá có sẵn. Vì các mệnh giá có sẵn là các bội số của nhau theo một cấu trúc đặc biệt (1, 3, 5, 10, 30...), greedy để chia tiền lẻ là tối ưu. Ta chỉ cần duyệt số lượng xu mới k từ 0 đến t/x. Với x nhỏ, t/x lớn nên cần tối ưu (break khi k > ans).

Cách Tối ưu hóa số lần lặp (Thay đổi góc nhìn)

ll ans = f(t); // f(t) là hàm greedy dùng base
ll maxk = t / x;
// Thay vì duyệt k từ 0 đến maxk, ta dùng hàm f(t - k*x)
// Cấu trúc base cho phép f(n) chạy rất nhanh.
// Tuy nhiên, để tránh duyệt quá nhiều khi x nhỏ, ta chỉ cần duyệt k trong khoảng nhỏ.
// Ví dụ: nếu x nhỏ, ta chỉ cần xét k gần giá trị optimal.
// Thực tế, với bộ base này, số lượng xu dùng để chia t - k*x thay đổi ít.
// Có thể dùng k = 0 đến khi k*x vượt quá t hoặc số lượng xu cơ bản vượt quá ans.
for (ll k = 0; k <= maxk; k++) {
    ans = min(ans, k + f(t - k * x));
}

• Time Complexity: O(t/x * 15) hoặc O(sqrt(t)) nếu tối ưu thêm
• Space Complexity: O(1)

Đây là biến thể của cách 2. Code mẫu thực chất vẫn duyệt từ 0 đến maxk (t/x). Nếu x rất nhỏ (ví dụ x=1), t/x = 10^9, vòng lặp sẽ quá chậm. Tuy nhiên, các giải pháp accepted thường có cơ chế break hoặc giới hạn k (ví dụ k <= 100000). Một cách tiếp cận tổng quát hơn là nhận thấy ta chỉ cần kiểm tra các giá trị k sao cho số lượng xu thay đổi, thường tập trung quanh các giá trị mà tại đó số xu base giảm mạnh (ví dụ khi t - k*x chia hết cho các mệnh giá lớn như 50000).

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

Bài học kinh nghiệm

• Các mệnh giá base {1, 3, 5, 10, 30, 50...} có tính chất 'hệ cơ số lai' hoặc tương tự, cho phép sử dụng chiến lược greedy (lấy số lượng lớn nhất có thể) để chia tiền lẻ một cách tối ưu.
• Bài toán quy hoạch động kinh điển 'Coin Change' với dữ liệu lớn không thể giải trực tiếp. Tuy nhiên, khi có thêm xu mệnh giá x, ta có thể quy về bài toán kiểm tra một số lượng nhỏ các trường hợp 'dùng bao nhiêu xu x'.
• Việc tối ưu vòng lặp là then chốt. Nếu duyệt k từ 0 đến t/x, độ phức tạp là O(t/x). Cần nhận diện giới hạn dữ liệu để chọn ngưỡng lặp phù hợp (ví dụ chỉ lặp tối đa 10^5 hoặc 2*10^5 lần).

Lỗi thường gặp

• Lặp quá nhiều lần khi x rất nhỏ (ví dụ x=1 hoặc x=2). Cần thêm điều kiện break hoặc giới hạn số lần lặp (k <= some_limit).
• Quên kiểm tra trường hợp rem == 0 sau khi dùng greedy. Greedy chỉ đảm bảo chia hết tiền nếu các mệnh giá đủ tốt (đối với bộ base này là tối ưu).
• Sử dụng biến số sai kiểu (int thay cho long long)导致 overflow khi t, x lên tới 2*10^9.