Editorial for tgd: Chọn bộ ba

Hiểu bài toán

Cho một dãy số nguyên gồm N phần tử. Nhiệm vụ là đếm số cách chọn ba chỉ số (i, j, k) sao cho ba giá trị tương ứng ai, aj, ak tạo thành ba cạnh của một tam giác đều. Điều kiện để ba cạnh tạo thành tam giác đều là chúng phải bằng nhau (ai = aj = ak) và có giá trị dương (vì độ dài cạnh không thể âm hoặc 0 trong tam giác đều).

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

Cách Hash Map (Băm)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    unordered_map<long long, long long> freq;
    for (int i = 0; i < n; ++i) {
        long long x;
        cin >> x;
        if (x > 0) {
            freq[x]++;
        }
    }

    long long ans = 0;
    for (auto &p : freq) {
        long long count = p.second;
        if (count >= 3) {
            // Chọn 3 phần tử từ count phần tử giống hệt nhau
            ans += count * (count - 1) * (count - 2) / 6;
        }
    }

    cout << ans;
    return 0;
}

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

Approach này dựa trên việc nhận thấy rằng để ba cạnh tạo thành tam giác đều, chúng phải có độ dài bằng nhau và dương. Do đó, bài toán quy về đếm số cách chọn 3 phần tử trong nhóm các phần tử có giá trị giống nhau (và dương).

1. Duyệt qua mảng đầu vào. Sử dụng một hash map (unordered_map) để lưu tần suất xuất hiện của các số dương.
2. Với mỗi số dương x, ta cập nhật freq[x].
3. Sau khi có bảng tần suất, duyệt qua từng cặp (giá trị, số lần xuất hiện).
4. Nếu một giá trị xuất hiện k lần, số cách chọn 3 số hạng từ k số này là tổ hợp chập 3 của k: C(k, 3) = k * (k-1) * (k-2) / 6.
5. Tổng tất cả các kết quả này cho ra đáp án cuối cùng.

Ví dụ: Dãy 1, 2, 2, 2, 2.

• Tần suất: 1: 1, 2: 4.
• Với 1: không đủ 3.
• Với 2: C(4, 3) = 4. Đáp án là 4.

Cách Brute Force (Đối sánh trực tiếp - Hiểu sai đề)

// Lưu ý: Code này chỉ minh họa cách tiếp cận logic,
// không phải code tối ưu cho bài toán hiện tại.
// Nó giả định bài toán đếm tam giác cân hoặc đều.
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for(int i=0; i<n; i++) cin >> a[i];

    sort(a.begin(), a.end());
    long long ans = 0;

    // Logic cho tam giác đều (giả sử cần a[i] == a[j] == a[k])
    // Cần map hoặc sort + 2 pointers
    // Dưới đây là ví dụ Brute force đơn giản O(N^3)
    // Chỉ dùng để giải thích, không dùng cho N=10^5

    return 0;
}

• Time Complexity: O(N^3) hoặc O(N^2)
• Space Complexity: O(1)

Đây là cách tiếp cận trực quan nhất nhưng không khả thi với giới hạn N=10^5.

1. Duyệt qua tất cả các bộ ba (i, j, k) để kiểm tra xem a[i], a[j], a[k] có bằng nhau hay không.
2. Độ phức tạp O(N^3) là quá lớn, dẫn đến Time Limit Exceeded.

Tuy nhiên, nhiều người mới làm bài hay nhầm lẫn giữa Tam giác đều (Equilateral) và Tam giác cân (Isosceles) hoặc Tam giác thường. Đề bài yêu cầu 'Tam giác đều' (Equilateral triangle), nghĩa là 3 cạnh bằng nhau. Nếu đề bài yêu cầu tam giác cân, ta cần 2 cạnh bằng nhau và lớn hơn cạnh còn lại. Approaches trên chỉ giải quyết đúng bài toán 'Tam giác đều'.

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

Bài học kinh nghiệm

• Tam giác đều yêu cầu 3 cạnh bằng nhau và dương. Do đó, bài toán chỉ cần đếm số bộ 3 phần tử có giá trị bằng nhau trong dãy (chỉ xét các số dương).
• Tổng quan bài toán là bài toán đếm tổ hợp: Với mỗi giá trị xuất hiện k lần, có C(k, 3) cách chọn.

Lỗi thường gặp

• Quên kiểm tra điều kiện số dương (x > 0).
• Quên xử lý trường hợp số lượng phần tử lớn (sử dụng biến kiểu long long để lưu kết quả).
• Sử dụng sort và unique không đúng cách có thể gây phức tạp hóa bài toán đơn giản là đếm tần suất.