Hướng dẫn thuật toán - Đăng - Chuyên Sơn La Online Judge

Nhận xét

Đây là một bài toán kinh điển trong lập trình thi đấu, thường được giải quyết bằng phương pháp Quy hoạch động sử dụng Bitmask (Bitmask Dynamic Programming) hoặc Đệ quy có nhớ (Memoization) do giới hạn của khá nhỏ ().

1. Phân tích đề bài

Yêu cầu: Đếm số cách ghép cặp hoàn hảo ( chàng trai với cô gái) sao cho tất cả các cặp đều hợp nhau (tương ứng với ).
Đầu vào: Số () và ma trận tương hợp .
Đầu ra: Số lượng cách ghép cặp hợp lệ.
Ràng buộc quan trọng: . Ràng buộc này cho phép chúng ta sử dụng các thuật toán có độ phức tạp mũ, cụ thể là .

2. Ý tưởng thuật toán: Quy hoạch động Bitmask

Vì nhỏ, ta có thể dùng một Bitmask (mặt nạ bit) để biểu diễn trạng thái của các cô gái đã được ghép cặp.

Ta sẽ cố gắng ghép cặp lần lượt từng chàng trai một, từ Chàng trai 1 đến Chàng trai .
Bitmask sẽ là một số nguyên có bit, trong đó:
- Bit thứ bằng 1 nếu Cô gái đã được ghép cặp.
- Bit thứ bằng 0 nếu Cô gái chưa được ghép cặp.

Định nghĩa trạng thái DP

Ta định nghĩa mảng DP như sau:

Trong đó, chính là số lượng bit 1 (set bits) trong mask.

3. Các bước cơ bản của thuật toán

Bước 1: Khởi tạo

Khai báo mảng dp có kích thước .
Khởi tạo dp[0] = 1. (Trạng thái ban đầu: 0 chàng trai được ghép với 0 cô gái, có 1 cách duy nhất).
Khởi tạo các giá trị dp khác bằng 0.

Bước 2: Chuyển trạng thái (Transition)

Ta sẽ duyệt qua tất cả các trạng thái (mask) từ đến .

Duyệt qua các mask: for mask from 0 to (1 << N) - 2
Xác định chàng trai tiếp theo:
- Gọi là chỉ số của chàng trai tiếp theo cần ghép cặp.
- chính là số lượng bit 1 hiện có trong mask. (Ví dụ: Nếu mask có 3 bit 1, tức là 3 cô gái đã được ghép, thì chàng trai tiếp theo cần ghép là chàng trai thứ 4, hay chỉ số nếu ta dùng chỉ số từ 0).
- Lưu ý: Nếu bạn dùng chỉ số 1-based cho chàng trai, thì sẽ là .
Duyệt qua các cô gái chưa được ghép:
- for j from 0 to N - 1
- Kiểm tra điều kiện: a. Cô gái chưa được ghép: (Bit thứ trong mask là 0). Tức là: (mask & (1 << j)) == 0. b. Chàng trai và Cô gái hợp nhau: A[i][j] == 1.
Cập nhật DP:
- Nếu cả hai điều kiện trên đều thỏa mãn, ta có thể ghép .
- Trạng thái mới: new_mask = mask | (1 << j).
- Cập nhật số cách:

Bước 3: Kết quả

Kết quả cuối cùng là giá trị của (mask mà tất cả các bit đều là 1, tức là tất cả cô gái đã được ghép).

4. Lưu ý khi triển khai bằng C++ hoặc Python

Mục	C++	Python
Kiểu dữ liệu	Dùng `long long` cho mảng `dp` vì số cách có thể lớn.	Số nguyên Python tự động lớn, không cần lo lắng.
Kích thước mảng DP	`long long dp[1 << 21];`	`dp = [0] * (1 << N)`
Đếm số bit 1	Sử dụng hàm có sẵn: `__builtin_popcount(mask)` (rất nhanh).	Dùng phương thức: `bin(mask).count('1')` hoặc tự viết hàm đếm.
Truy cập ma trận	Cần đảm bảo chỉ số (chàng trai) và (cô gái) khớp với cách bạn lưu ma trận (0-based hay 1-based).	Tương tự C++.

Ví dụ về cách xác định chàng trai trong vòng lặp DP (C++):

// i là chỉ số của chàng trai tiếp theo (0-based)
int i = __builtin_popcount(mask); 

// Duyệt qua các mask
for (int mask = 0; mask < (1 << N) - 1; ++mask) {
    if (dp[mask] == 0) continue; // Bỏ qua trạng thái không thể đạt được

    int boy_index = __builtin_popcount(mask); // Chàng trai thứ "popcount(mask)" (0-based)

    // Duyệt qua các cô gái
    for (int girl_index = 0; girl_index < N; ++girl_index) {
        // 1. Cô gái chưa được ghép VÀ 2. Hai người hợp nhau
        if (!(mask & (1 << girl_index)) && A[boy_index][girl_index] == 1) {
            int new_mask = mask | (1 << girl_index);
            dp[new_mask] += dp[mask];
        }
    }
}