Editorial for mkrect: Tìm cách xếp hình lớn nhất

Hiểu bài toán

Bài toán yêu cầu tìm hình chữ nhật có diện tích lớn nhất tạo được từ 4 que diêm trong N que diêm cho sẵn. Một hình chữ nhật cần 2 đôi cạnh song song và bằng nhau. Do đó, ta cần chọn 2 giá trị độ dài (ví dụ L và W) sao cho mỗi giá trị này xuất hiện ít nhất 2 lần trong mảng đầu vào để tạo thành 2 cạnh chiều dài và 2 cạnh chiều rộng. Diện tích hình chữ nhật là tích của hai giá trị này (L * W). Nếu không có đủ số que diêm để tạo thành hình chữ nhật, in ra 0.

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

Cách Sắp xếp và duyệt (Tối ưu hóa từ Brute Force)

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    long long x = *(long long *)a;
    long long y = *(long long *)b;
    if (x < y) return 1; // Sắp xếp giảm dần
    if (x > y) return -1;
    return 0;
}

int main() {
    int n;
    scanf("%d", &n);
    long long *a = (long long *)malloc(n * sizeof(long long));
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }
    qsort(a, n, sizeof(long long), cmp);

    long long s1 = 0, s2 = 0; // s1 là cạnh lớn nhất, s2 là cạnh lớn thứ 2

    for (int i = 0; i < n - 1; i++) {
        if (a[i] == a[i+1]) {
            if (s1 == 0) {
                s1 = a[i];
                i++; // Bỏ qua que diêm cạnh
            } else if (s2 == 0) {
                s2 = a[i];
                break; // Đã đủ 2 đôi
            }
        }
    }

    if (s1 != 0 && s2 != 0) {
        printf("%lld", s1 * s2);
    } else {
        printf("0");
    }

    free(a);
    return 0;
}

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

Cách tiếp cận này dựa trên việc sắp xếp mảng độ dài giảm dần. Sau đó, ta duyệt qua mảng để tìm hai cặp giá trị bằng nhau đầu tiên. Vì mảng đã sắp xếp giảm dần, cặp giá trị đầu tiên tìm được là cặp lớn nhất (s1), và cặp tiếp theo là cặp lớn thứ hai (s2). Tích của chúng chính là diện tích lớn nhất. Ví dụ: Mảng sau khi sort: [9, 5, 5, 3, 3, 2, 1]. Duyệt: 9 != 5 -> bỏ. 5 == 5 -> tìm thấy s1 = 5. 5 != 3 -> bỏ. 3 == 3 -> tìm thấy s2 = 3. Dừng lại. Kết quả: 5 * 3 = 15.

Cách Hash Map (Đếm tần suất)

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    map<long long, int> counts;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        counts[x]++;
    }

    vector<long long> candidates;
    for (auto const& [val, count] : counts) {
        if (count >= 2) {
            // Nếu có 2 hoặc 3 que, ta có thể dùng 1 cạnh.
            // Nếu có >= 4 que, ta vẫn chỉ cần 1 cạnh (dùng 2 que).
            // Tuy nhiên, nếu count >= 4, ta có thể dùng 2 cạnh từ cùng một giá trị.
            // Logic: Với mỗi val, ta có thể chèn val vào danh sách cạnh.
            // Nếu count >= 4, ta có thể chèn 2 lần (tạo hình vuông).
            candidates.push_back(val);
            if (count >= 4) {
                candidates.push_back(val);
            }
        }
    }

    // Sắp xếp giảm dần để dễ tìm max
    sort(candidates.rbegin(), candidates.rend());

    if (candidates.size() < 2) {
        cout << 0 << endl;
    } else {
        // Ta cần 2 giá trị lớn nhất.
        // Do ta đã chèn 2 lần nếu count >= 4, nên candidates[0] và candidates[1]
        // chính là 2 cạnh lớn nhất có thể.
        cout << candidates[0] * candidates[1] << endl;
    }

    return 0;
}

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

Sử dụng map (hoặc hash map) để đếm tần suất các độ dài. Sau đó, tạo một danh sách 'candidates' chứa các độ dài có thể dùng làm cạnh. Nếu một độ dài xuất hiện >= 2 lần, thêm nó vào danh sách (mỗi cặp que cho 1 độ dài cạnh). Nếu xuất hiện >= 4 lần, nó có thể tạo thành hình vuông, do đó thêm nó hai lần vào danh sách. Cuối cùng, sắp xếp danh sách này giảm dần và lấy tích của hai phần tử đầu tiên. Ví dụ: [4, 4, 4, 4, 1] -> counts[4]=4, counts[1]=1. Candidates = [4, 4]. Result = 4*4 = 16.

Cách Brute Force (Đối với N nhỏ)

long long max_area = 0;
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
            for (int l = k + 1; l < n; l++) {
                // Kiểm tra 4 que có thể tạo hình chữ nhật
                // Sắp xếp 4 giá trị: a, b, c, d (a <= b <= c <= d)
                // Cần a == b và c == d
                long long sides[4] = {arr[i], arr[j], arr[k], arr[l]};
                sort(sides, sides + 4);
                if (sides[0] == sides[1] && sides[2] == sides[3]) {
                    max_area = max(max_area, sides[0] * sides[2]);
                }
            }
        }
    }
}

• Time Complexity: O(N^4)
• Space Complexity: O(1)

Đây là giải pháp thô (Brute Force) thử tất cả các tổ hợp 4 que diêm khác nhau. Với mỗi tổ hợp, ta kiểm tra xem chúng có thể tạo thành một hình chữ nhật hay không (cần hai cặp bằng nhau). Phương pháp này chỉ khả thi cho N rất nhỏ (ví dụ N <= 50) và sẽ quá thời gian chạy cho các giới hạn lớn hơn của bài toán.

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

Bài học kinh nghiệm

• 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. Do đó, ta cần tìm 2 độ dài (L, W) sao cho mỗi độ dài có ít nhất 2 que.
• Để có diện tích lớn nhất, ta nên ưu tiên chọn các độ dài lớn nhất có thể. Sắp xếp mảng giảm dần giúp ta dễ dàng tìm thấy các cặp lớn nhất đầu tiên.
• Nếu một độ dài xuất hiện 4 lần trở lên, nó có thể tạo thành hình vuông (cạnh L, cạnh W với L=W), chiếm 2 vị trí trong danh sách ứng cử viên.

Lỗi thường gặp

• Không xử lý đúng số lượng que (ví dụ: cần 4 que, nhưng nếu một độ dài có tần suất 3, ta chỉ có thể dùng 2 que cho cạnh đó, que còn lại không đủ để tạo cặp).
• Tràn số (Integer Overflow): Diện tích có thể lên tới 10^9 * 10^9 = 10^18, vượt quá giới hạn của kiểu int (2*10^9). Phải sử dụng kiểu long long (64-bit).
• Xử lý sai thứ tự khi sắp xếp (tăng dần/giảm dần) có thể dẫn đến việc chọn sai cặp cạnh nếu logic duyệt không cẩn thận.