Editorial for tricount: Thiết kế tam giác

Hiểu bài toán

Cho N thanh sắt với độ dài lần lượt là A_i. Yêu cầu đếm số bộ ba chỉ số (i, j, k) với 1 ≤ i < j < k ≤ N sao cho ba thanh sắt tương ứng có độ dài tạo thành một tam giác. Điều kiện để ba cạnh a, b, c tạo thành tam giác là a + b > c (với giả định a ≤ b ≤ c).

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

Cách Brute Force

long long cnt = 0;
for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
        for (int k = j + 1; k < N; k++) {
            if (A[i] + A[j] > A[k]) cnt++;
        }
    }
}

• Time Complexity: O(N^3)
• Space Complexity: O(N)

Duyệt tất cả các bộ ba (i, j, k) có i < j < k và kiểm tra điều kiện A[i] + A[j] > A[k]. Với N tối đa 8000, độ phức tạp này quá lớn và không thể chấp nhận.

Cách Binary Search

sort(A.begin(), A.end());
ll cnt = 0;
for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
        int sum = A[i] + A[j];
        int lo = j + 1, hi = N - 1, pos = j;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (A[mid] < sum) {
                pos = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        cnt += (pos - j);
    }
}

• Time Complexity: O(N^2 log N)
• Space Complexity: O(N)

Sau khi sắp xếp mảng, với mỗi cặp (i, j) cố định, ta cần tìm số lượng k > j sao cho A[k] < A[i] + A[j]. Do mảng đã sắp xếp, ta có thể dùng binary search để tìm vị trí cuối cùng (pos) thỏa mãn A[pos] < A[i] + A[j]. Số lượng k hợp lệ là pos - j. Với N=8000, độ phức tạp khoảng 8000^2 * log(8000) ≈ 7.4*10^8, có thể chạy trong 1s nhưng khá sát.

Cách Two Pointers

sort(a, a + n);
long long ans = 0;
for (int k = 0; k < n; ++k) {
    int i = 0, j = k - 1;
    while (i < j) {
        if (a[i] + a[j] > a[k]) {
            ans += (j - i);
            --j;
        } else {
            ++i;
        }
    }
}

• Time Complexity: O(N^2)
• Space Complexity: O(N)

Sau khi sắp xếp, ta xét biến k làm cạnh lớn nhất. Với mỗi k, ta dùng hai con trỏ i (bắt đầu từ 0) và j (bắt đầu từ k-1). Nếu a[i] + a[j] > a[k], thì mọi chỉ số từ i đến j-1 đều thỏa mãn cùng với j (vì a[i] tăng dần), nên ta cộng j-i vào kết quả và giảm j. Ngược lại, ta tăng i để tìm giá trị a[i] lớn hơn. Cách này tối ưu hơn binary search vì chỉ cần duyệt O(N) cho mỗi k.

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

Bài học kinh nghiệm

• Sau khi sắp xếp mảng, điều kiện tam giác chỉ cần kiểm tra a + b > c với a ≤ b ≤ c.
• Với biến k cố định (cạnh lớn nhất), bài toán trở thành tìm số cặp (i, j) với i < j < k sao cho a[i] + a[j] > a[k].
• Kỹ thuật hai con trỏ (two pointers) có thể giải quyết bài toán con này trong thời gian tuyến tính O(k).

Lỗi thường gặp

• Quên sắp xếp mảng trước khi áp dụng các thuật toán tối ưu.
• Sử dụng biến số(int) cho kết quả trung gian thay vì long long do số lượng bộ ba có thể lên tới ~N^3/6 (với N=8000, kết quả ~8.5*10^10).
• Lỗi chỉ số trong vòng lặp two pointers: j phải bắt đầu từ k-1 và điều kiện dừng là i < j.