Hiểu bài toán

Cho n que diêm có độ dài khác nhau hoặc bằng nhau. Nhiệm vụ là đếm số lượng hình chữ nhật khác nhau có thể tạo thành từ 4 que diêm. Hai hình chữ nhật được coi là khác nhau nếu chúng không có cùng chiều dài và chiều rộng. Ví dụ, hình chữ nhật có sides (2, 5) là khác với (5, 2) nhưng trong bài toán này, một cặp sides (L, W) được xem là một hình chữ nhật duy nhất (thường (L, W) và (W, L) được xem là một nếu L != W, hoặc chỉ là một nếu L=W). Tuy nhiên, theo các ví dụ và logic bài toán, chúng ta cần chọn 2 cặp sides (có thể bằng nhau) từ các que diêm có sẵn. Một hình chữ nhật được tạo thành từ 2 cặp que diêm có độ dài bằng nhau (ví dụ: 2 que độ dài A và 2 que độ dài B tạo thành hình chữ nhật A x B). Chúng ta cần đếm số cách chọn 2 giá trị độ dài (có thể trùng nhau nếu đủ que) từ tập hợp các độ dài que diêm sao cho mỗi giá trị chọn có ít nhất 2 que tương ứng.

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

Cách Hash Map và Tính toán Tổ hợp

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        freq[a[i]]++;
    }

    long long cnt_pairs = 0; // số lượng các giá trị có ít nhất 2 que
    long long cnt_quads = 0; // số lượng các giá trị có ít nhất 4 que (tạo hình vuông)

    for (auto const& [key, val] : freq) {
        if (val >= 2) {
            cnt_pairs++;
        }
        if (val >= 4) {
            cnt_quads++;
        }
    }

    // Công thức tính số hình chữ nhật:
    // 1. Chọn 2 giá trị khác nhau (i, j) mỗi cái có >= 2 que: C(cnt_pairs, 2)
    // 2. Chọn 1 giá trị có >= 4 que (tạo hình vuông): cnt_quads
    // Note: C(cnt_pairs, 2) = cnt_pairs * (cnt_pairs - 1) / 2
    // Nhưng trong code mẫu, họ cộng cnt_quads vào sau khi tính C(cnt_pairs, 2).
    // Lưu ý: cnt_pairs bao gồm những cái có >= 4 que. Nếu ta dùng C(cnt_pairs, 2), ta đã đếm các cặp (i, i) không hợp lệ.
    // Thực tế, code mẫu: cnt = số lượng >= 2, s = số lượng >= 4.
    // cout << cnt * (cnt - 1) / 2 + s;
    // Giải thích: cnt * (cnt - 1) / 2 là cách tính nhanh của C(cnt, 2).
    // Nếu một phần tử có >= 4 que, nó được tính vào cnt (nên có mặt trong C(cnt, 2)).
    // Tuy nhiên, C(cnt, 2) chỉ chọn 2 phần tử KHÁC NHAU.
    // Để có được hình vuông (L, L), ta cần chọn L 2 lần.
    // Vậy t tổng số hình chữ nhật là:
    // Số cách chọn 2 độ dài KHÁC NHAU, mỗi độ dài có >= 2 que: C(cnt_pairs, 2).
    // Số cách chọn 1 độ dài (L) có >= 4 que để tạo thành hình vuông: cnt_quads.
    // Cộng lại là: C(cnt_pairs, 2) + cnt_quads.
    // Code mẫu: cnt * (cnt - 1) / 2 + s.
    // Ở đây cnt là số lượng >= 2. s là số lượng >= 4.
    // Check lại logic: Ví dụ có 2 độ dài A (>=4), B (>=2). 
    // C(cnt, 2) với cnt=2 là 1 (tức A,B). Thêm s=1 (A,A). Tổng = 2.
    // Đúng.

    long long ans = cnt_pairs * (cnt_pairs - 1) / 2 + cnt_quads;
    cout << ans << endl;

    return 0;
}

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

Cách tiếp cận này sử dụng một hash map (hoặc mảng tần suất) để đếm số lần xuất hiện của mỗi độ dài que diêm.

1. Duyệt qua danh sách que diêm và cập nhật tần suất vào map.
2. Duyệt qua map để đếm:
   • cnt_pairs: Số lượng độ dài có ít nhất 2 que (tức là có thể dùng làm 1 cạnh).
   • cnt_quads: Số lượng độ dài có ít nhất 4 que (tức là có thể dùng làm cả hai cạnh của hình vuông).
3. Số lượng hình chữ nhật được tính bằng:
   • Số cách chọn 2 độ dài KHÁC NHAU từ cnt_pairs để tạo thành hình chữ nhật (chiều dài L, chiều rộng W): Đây là tổ hợp chập 2 của cnt_pairs, tức là cnt_pairs * (cnt_pairs - 1) / 2.
   • Số cách chọn 1 độ dài từ cnt_quads để tạo thành hình vuông (chiều dài L, chiều rộng L): Đây chính là cnt_quads.
   • Tổng số hình chữ nhật là tổng của hai giá trị trên.
   • Lưu ý: Code mẫu cnt * (cnt - 1) / 2 + s là cách viết gọn của logic trên với cnt là cnt_pairs và s là cnt_quads.

Cách Sử dụng Mảng Tần suất (Cố định)

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

const int MAX_VAL = 1000;

int main() {
    int n;
    cin >> n;
    vector<int> counts(MAX_VAL + 1, 0);

    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        counts[val]++;
    }

    long long pairs = 0;
    long long squares = 0;

    for (int i = 1; i <= MAX_VAL; i++) {
        if (counts[i] >= 2) {
            pairs++;
        }
        if (counts[i] >= 4) {
            squares;
            squares++;
        }
    }

    long long ans = pairs * (pairs - 1) / 2 + squares;
    cout << ans << endl;

    return 0;
}

• Time Complexity: O(n + K)
• Space Complexity: O(K)

Vì độ dài que diêm (a_i) bị giới hạn trong khoảng [1, 1000], ta có thể sử dụng một mảng tần suất cố định thay cho hash map. Độ phức tạp không gian sẽ giảm đi đáng kể so với hash map (tránh overhead).

1. Khởi tạo mảng counts với kích thước 1001 (hoặc 1005).
2. Đọc dữ liệu và cập nhật trực tiếp vào counts[a_i].
3. Duyệt mảng counts từ 1 đến 1000 để đếm pairs và squares tương tự như cách tiếp cận trước.
4. Tính kết quả bằng công thức tổ hợp: pairs * (pairs - 1) / 2 + squares. Độ phức tạp thời gian là O(n) để đọc dữ liệu và O(1000) để duyệt mảng, t tổng là O(n).

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

Bài học kinh nghiệm

• Bài toán có thể quy về bài toán đếm các cặp độ dài (L, W). Nếu L != W, ta cần ít nhất 2 que độ dài L và 2 que độ dài W. Nếu L == W, ta cần ít nhất 4 que độ dài L.
• Sử dụng cấu trúc dữ liệu đếm tần suất (Hash Map hoặc Mảng) là bước đầu tiên không thể thiếu để tổng hợp thông tin về các que diêm.
• Số lượng hình chữ nhật khác nhau tương ứng với số cách chọn các cặp độ dài thỏa mãn điều kiện về số lượng que, chứ không phải cách xếp các que.

Lỗi thường gặp

• Đếm trùng lặp: Ví dụ, nếu có 3 độ dài A, B, C đều có >= 2 que. Số cách chọn 2 độ dài là C(3, 2) = 3 (AB, AC, BC). Đừng đếm thành 6 (AB, BA, ...).
• Quên trường hợp hình vuông: Nếu chỉ tính số cách chọn 2 độ dài khác nhau, ta sẽ bỏ sót các hình vuông (L, L). Cần cộng thêm số lượng độ dài có ít nhất 4 que.
• Lựa chọn cấu trúc dữ liệu: Nếu n nhỏ nhưng a_i lớn, dùng Hash Map là bắt buộc. Nếu a_i nhỏ (như đề bài này), mảng tần suất hiệu quả hơn.