Hiểu bài toán

Bài toán yêu cầu đếm số bộ ba số nguyên không âm (X, Y, Z) sao cho 0 ≤ X, Y, Z ≤ K và X + Y + Z = S. Với K và S được cho trước. Nói cách khác, ta cần tìm số cách phân chia S thành ba phần (có thể bằng 0) mà mỗi phần không vượt quá K.

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

Cách Brute Force (Lặp kép)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int K, S;
    cin >> K >> S;
    long long ans = 0;
    for (int x = 0; x <= K; x++) {
        for (int y = 0; y <= K; y++) {
            int z = S - x - y;
            if (0 <= z && z <= K) ans++;
        }
    }
    cout << ans;
}

• Time Complexity: O(K^2)
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp nhất. Ta lặp qua tất cả các giá trị có thể của X (từ 0 đến K). Với mỗi X, ta lặp qua tất cả các giá trị có thể của Y (từ 0 đến K). Sau đó, ta tính Z = S - X - Y. Nếu Z nằm trong khoảng [0, K], thì bộ (X, Y, Z) hợp lệ và ta tăng biến đếm lên 1. Với K tối đa là 2500, số lượng phép toán là khoảng 6.25 * 10^6, hoàn toàn chấp nhận được trong thời gian chạy của C++.

Cách Optimized Iteration (Tối ưu hóa lặp)

#include <iostream>
using namespace std;

int main() {
    int K, S;
    cin >> K >> S;
    long long count = 0;

    for (int x = 0; x <= K; ++x) {
        // Với mỗi x, ta cần Y + Z = S - X
        // Y và Z phải nằm trong [0, K]
        int sum_yz = S - x;

        // Y phải nằm trong [0, K]
        // Z = sum_yz - Y phải nằm trong [0, K]
        // => sum_yz - Y >= 0  => Y <= sum_yz
        // => sum_yz - Y <= K  => Y >= sum_yz - K
        // Vậy Y phải nằm trong đoạn [max(0, sum_yz - K), min(K, sum_yz)]

        int min_y = max(0, sum_yz - K);
        int max_y = min(K, sum_yz);

        if (min_y <= max_y) {
            count += (max_y - min_y + 1);
        }
    }

    cout << count << endl;
    return 0;
}

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

Thay vì lặp qua tất cả các giá trị của Y, ta có thể tính toán số lượng giá trị Y hợp lệ cho mỗi giá trị X cố định. Với một giá trị X cho trước, ta cần Y + Z = S - X. Giả sử tổng này là T. Để Y và Z đều nằm trong [0, K], Y phải thỏa mãn max(0, T - K) ≤ Y ≤ min(K, T). Số lượng giá trị Y hợp lệ là min(K, T) - max(0, T - K) + 1 (nếu đoạn này hợp lệ). Bằng cách này, ta giảm độ phức tạp từ O(K^2) xuống O(K).

Cách Mathematical Formula

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    long long K, S;
    cin >> K >> S;
    long long ans = 0;

    // Duyệt qua X từ 0 đến K
    for (long long x = 0; x <= K; x++) {
        long long remainder = S - x;
        // Y + Z = remainder, với 0 <= Y, Z <= K
        // Biến đổi phương trình: Z = remainder - Y
        // Điều kiện: 0 <= remainder - Y <= K
        // Suy ra: remainder - K <= Y <= remainder
        // Kết hợp với 0 <= Y <= K, ta có:
        // Y >= max(0, remainder - K)
        // Y <= min(K, remainder)

        long long lower_bound = max(0LL, remainder - K);
        long long upper_bound = min(K, remainder);

        if (lower_bound <= upper_bound) {
            ans += (upper_bound - lower_bound + 1);
        }
    }

    cout << ans << endl;
    return 0;
}

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

Đây là biến thể của cách tiếp cận O(K) ở trên, nhấn mạnh logic toán học. Với mỗi X, ta xác định phạm vi giá trị hợp lệ của Y dựa trên các ràng buộc về Y và Z. Logic này loại bỏ hoàn toàn vòng lặp thứ hai, chỉ cần xử lý tính toán toán học đơn giản trong mỗi bước lặp của X.

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

Bài học kinh nghiệm

• Bài toán có thể coi là bài toán tìm số nguyên không âm (X, Y, Z) trong một khối lập phương kích thước K+1.
• Giảm độ phức tạp bằng cách loại bỏ một vòng lặp: Thay vì lặp Y, tính toán trực tiếp số lượng Y hợp lệ cho mỗi X.
• Khi K khá nhỏ (≤ 2500), giải pháp O(K^2) cũng hoàn toàn khả thi và dễ hiểu.

Lỗi thường gặp

• Quên kiểm tra điều kiện Z >= 0 khi dùng phương pháp lặp kép (sai sót khi S - X - Y âm).
• Sai kiểu dữ liệu: S có thể lên tới 7500, nhưng khi dùng phép cộng nhiều số, nên dùng kiểu long long để tránh tràn số nếu K lớn hơn.
• Lỗi logic trong việc xác định biên (off-by-one error): Khi tính số lượng Y hợp lệ, cần chú ý include cả hai đầu mút của đoạn [min, max].