#1077 · Ghép hình chữ nhật - MAREC

Ta sẽ ví dụ với case mẫu ở hướng dẫn:

n = 9
2 4 5 2 2 4 5 4 3

Đầu tiên ta sẽ dùng mảng tần suất hoặc dùng hashmap hoặc ... để đếm số lượng giá trị a[i]

Giá trị a[i] | số lượng
     2       |    3
     3       |    1
     4       |    3
     5       |    2

Đơn giản với mảng tần suất:

#define MAX 10000

// Khởi tạo mảng tần suất
int b[MAX] = {0}; // Khởi tạo giá trị mặc định là 0

// Cách sử dụng:
// Dùng chính giá trị trong mảng a[i] để làm index
// Đảm bảo toàn bộ giá trị mảng là số nguyên dương và MAX >= giá trị max trong mảng
// Ví dụ sử dụng: b[a[i]]

Đầu tiên ta sẽ tạo 2 biến đếm riêng biệt để xử lý từng tình huống:

int dem_kq = 0; biến đếm kết quả (output)

int dem_2 = 0 biến đếm cho trường hợp hình CHỮ NHẬT.

Đầu tiên ta nhận ra rằng nếu a[i] có số lượng >= 4 thì chắc chắn sẽ tạo 1 hình vuông. Ta sẽ tạo 1 vòng for để tìm tới các a[i] có sl >= 4 và đếm. Đảm bảo không trùng lặp giá trị trước đó khi duyệt. (Tránh lặp thì ta có thể tạo mảng tần suất để làm mảng true/false hoặc đơn giản hơn là dùng kiểu dữ liệu bool với index chính là a[i]) Thì input trên ko có giá trị nào thoả mãn thế nên biến dem_kq = 0

Tiếp theo ta sẽ dùng biến đếm dem_2 để đếm các a[i] có số lượng >= 2

Lúc này dem_2 = 3 với các giá trị thoả mãn là 2,4,5 đều có sl >= 2

Sau đó ta sẽ dùng công thức (dem_2*(dem_2 - 1))/2

Rồi cộng dồn vào biến dem_kq: dem_kq += (dem_2*(dem_2 - 1))/2

Cuối cùng output là 3 cho case này!

Tại sao ta dùng đến công thức này? (dem_2*(dem_2 - 1))/2

Các cặp thoả mãn để tạo hình chữ nhật là: (2,4) (2,5) (4,5) = 3

Lập ma trận 3x3:

--2 4 5
2 X T T
4 X X T
5 X X X
X là không thoả mãn
T là thoả mãn

Thì bn học qua đại số tuyến tính thì nhận ra rằng các cặp thoả mãn là nửa tam giác trên.

Đầu tiên là n nhân n sẽ tính được toàn bộ hình vuông này ở đây là 3x3

Mà dòng cuối cùng không thoả mãn do cả dòng đều là X hết thế nên ta sẽ phải trừ đi 1 dòng.

=> n*(n - 1)

Lúc này ma trận còn:
--2 4 5
2 X T T
4 X X T

Ta nhận ra ngay rằng toàn bộ số lượng cặp thoả mãn = không thoả mãn thì ta sẽ chia 2 đi. Vậy ta sẽ hoàn thành công thức (n*(n-1))/2) để tính các cặp thoả mãn tạo nên hình chữ nhật với độ phức tạp o(1) cho việc tính toán và o(n) cho tìm a[i] có số lượng >= 2

Cuối cùng là cộng dồn dem_kq là xong bài toán :v Toàn bộ độ phức tạp là o(n)

Đọc đến đây chắc ae cũng mỏi mắt rồi nhỉ :v Mình viết lại để vững kiến thức. Ae nhớ tự cài đặt lại nhé :vv

Code mẫu cho ý tưởng trên:

#include <stdio.h>
#define MAX 10000

int main()
{
    int n;
    scanf("%d", &n);
    
    int a[n];
    int b[MAX] = {0}; // Mảng tần suất
    int c[MAX] = {0}; // Mảng true/false với 0 là false, 1 là true
    
    for(int i=0; i<n; i++)
    {
      scanf("%d", &a[i]);
      b[a[i]]++; // Cập nhật số lượng của phần tử a[i]
    }
    
    
    int dem_kq = 0;
    int dem_2 = 0;

    for(int i=0; i<n; i++)
    {
      if(c[a[i]] == 0)
      {
        if(b[a[i]] >= 4)
          dem_kq++;
        if(b[a[i]] >= 2)
          dem_2++;
        c[a[i]] = 1; // Khoá lại giá trị này để tránh bị trùng lặp khi duyệt
      }
    }
    
    printf("%d", dem_kq += (dem_2 * (dem_2-1))/2);
}