Hiểu bài toán

Bài toán yêu cầu tính số lượng cái bắt tay giữa n người bạn tại một bữa tiệc. Quy tắc là mỗi người bắt tay với tất cả những người còn lại và mỗi cặp người chỉ bắt tay nhau đúng một lần. Đây thực chất là bài toán tính số đường kính của đồ thị đầy đủ K_n (đồ thị có n đỉnh và tất cả các cạnh giữa các đỉnh đều t tồn tại).

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

Cách Công thức tổ hợp

#include <iostream>
using namespace std;

int main() 
{
    int n;
    cin >> n;
    cout << 1LL*n*(n-1)/2;
    return 0;
}

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

Đây là cách tiếp cận trực tiếp và hiệu quả nhất. Số cái bắt tay tương đương với số cách chọn 2 người khác nhau từ n người. Theo công thức tổ hợp, số cách chọn 2 người từ n người là C(n, 2) = n(n-1)/2. Ta phải dùng phép nhân với số lớn (1LL) hoặc kiểu dữ liệu long long để tránh tràn số khi n lên tới 10^6 (kết quả ~510^11).

Cách Vòng lặp (Brute Force)

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long res = 0;
    for (long long i = 1; i < n; i++) {
        res += i;
    }
    cout << res;
    return 0;
}

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

Giả sử các người được đánh số từ 1 đến n. Người thứ 1 bắt tay với n-1 người, người thứ 2 bắt tay với n-2 người (đã tính với người 1), ..., người thứ n-1 bắt tay với 1 người. Tổng số bắt tay là tổng các số từ 1 đến n-1. Cách này đúng nhưng chậm hơn công thức trực tiếp.

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

Bài học kinh nghiệm

• Bài toán này là biến thể của bài toán tính số cạnh trong đồ thị đầy đủ (Complete Graph).
• Số cái bắt tay chính là giá trị của tổ hợp chập 2 của n: C(n, 2).

Lỗi thường gặp

• Lỗi tràn số (Integer Overflow): Nếu khai báo biến kiểu int và n lớn (ví dụ 10^6), thì n(n-1) sẽ vượt quá giới hạn của kiểu int (khoảng 210^9). Cần dùng kiểu long long hoặc ép kiểu sang long long (1LL*n).
• Đếm thừa: Nếu tính sai công thức như n*(n+1)/2 hoặc n^2/2 sẽ ra kết quả sai.