Editorial for graduation: Kỳ thi tốt nghiệp

Hiểu bài toán

Bài toán yêu cầu đếm số cách đặt ít nhất một học sinh lên một lưới R x C sao cho các ràng buộc về hướng ngồi được thỏa mãn:

1. Nếu hai học sinh cùng hàng (cùng i), người ở cột nhỏ hơn (j1) phải quay về Tây (W), người ở cột lớn hơn (j2) phải quay về Đông (E).
2. Nếu hai học sinh cùng cột (cùng j), người ở hàng nhỏ hơn (i1) phải quay về Bắc (N), người ở hàng lớn hơn (i2) phải quay về Nam (S).

Phân tích các ràng buộc:

• Trên một hàng bất kỳ, các học sinh nếu có nhiều hơn 1 người phải được sắp xếp sao cho các hướng giảm dần từ trái sang phải: ... W W W E E E ... Điều này có nghĩa là trên mỗi hàng, các ô trống và các học sinh tạo thành các khối W (nếu có) ở bên trái và các khối E (nếu có) ở bên phải. Một hàng hợp lệ có thể là: (các ô trống) rồi (một số W hoặc không) rồi (một số E hoặc không).
• Tương tự, trên một cột bất kỳ, các học sinh phải có hướng giảm dần từ trên xuống dưới: ... N N N S S S ... Tức là các khối N ở trên và các khối S ở dưới.

Đặt các biến:

• w_i: số lượng học sinh quay về hướng W trên hàng i.
• e_i: số lượng học sinh quay về hướng E trên hàng i.
• n_j: số lượng học sinh quay về hướng N trên cột j.
• s_j: số lượng học sinh quay về hướng S trên cột j.

Ràng buộc chéo giữa hàng và cột:

• Các học sinh quay hướng W (ở hàng i) phải nằm trong các cột j sao cho có ít nhất nj học sinh quay N ở trên (tức j nằm trong top nj cột có nhiều N nhất).
• Các học sinh quay hướng E (ở hàng i) phải nằm trong các cột j sao cho có ít nhất sj học sinh quay S ở dưới (tức j nằm trong bottom sj cột có nhiều S nhất).
• Các học sinh quay hướng N (ở cột j) phải nằm trong các hàng i sao cho có ít nhất wi học sinh quay W ở bên trái (tức i nằm trong top wi hàng).
• Các học sinh quay hướng S (ở cột j) phải nằm trong các hàng i sao cho có ít nhất ei học sinh quay E ở bên phải (tức i nằm trong bottom ei hàng).

Điều này dẫn đến các điều kiện:

• wi <= nj nếu (i, j) có thể là W.
• ei <= sj nếu (i, j) có thể là E.
• wi + ei <= C (vị trí trên hàng).
• nj + sj <= R (vị trí trên cột).

Bài toán quy về đếm số bộ (W1...WR, E1...ER, N1...NC, S1...SC) thỏa mãn các điều kiện trên.

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

Cách Quy hoạch động 2 chiều (DP)

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

const long long MOD = 1e9 + 7;
long long dp[3005][3005];

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int R, C;
    cin >> R >> C;

    // dp[i][j]: So cach xep cho i hang va j cot
    // Khoi tao: 1 cach de trong
    for(int i = 0; i <= R; ++i) dp[i][0] = 1;
    for(int j = 0; j <= C; ++j) dp[0][j] = 1;

    for(int i = 1; i <= R; ++i) {
        for(int j = 1; j <= C; ++j) {
            dp[i][j] = 0;
            // Huong 1: Hang i khong co hoc sinh nao
            dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD;
            // Huong 2: Hang i co it nhat 1 hoc sinh, chon 1 cot de bat dau
            // Chon 1 cot trong j cot, dat 4 huong (W, E, N, S)
            // Nhuong dinh giai: 4 * j * dp[i-1][j-1]
            dp[i][j] = (dp[i][j] + dp[i-1][j-1] * 4 % MOD * j % MOD) % MOD;
            // Huong 3: Dat 2 hoc sinh o hang i (W va E) va cot j (N va S)
            if (i > 1) {
                dp[i][j] = (dp[i][j] + dp[i-2][j-1] * (i-1) % MOD * j % MOD) % MOD;
            }
        }
    }
    // Tru di 1 truong hop Empty (R, C) = 0
    long long ans = (dp[R][C] - 1 + MOD) % MOD;
    cout << ans;
    return 0;
}

• Time Complexity: O(R * C)
• Space Complexity: O(R * C)

Approach này sử dụng quy hoạch động để xây dựng số cách xếp chỗ. Trạng thái dp[i][j] đại diện cho số cách xếp chỗ cho i hàng đầu và j cột đầu.

Công thức chuyển:

• Xét hàng i và cột j:
  1. Không đặt học sinh ở hàng i: Gọi dp[i-1][j].
  2. Đặt một học sinh ở hàng i: Có j cách chọn cột. Nếu chọn cột j, học sinh có thể quay 4 hướng. Tuy nhiên, để tổng quát, ta xem xét việc thêm hàng i với j cột có thể chứa. Đặt 1 học sinh ở hàng i tương ứng với việc chọn 1 trong j cột và chọn 1 hướng (W, E, N, S). Các ràng buộc về hàng/cột được xử lý gián tiếp qua cách đếm này.
  3. Đặt hai học sinh ở hàng i (một W, một E) và cột j (một N, một S): Điều này tương ứng với việc tạo ra một "giao điểm" mới. Có (i-1) cách chọn hàng cho N/S (vì phải khác hàng i) và j cách chọn cột.

Cụ thể, các giải pháp đã cho sử dụng công thức: dp[i][j] = dp[i-1][j] + dp[i-1][j-1] * 4 * j + dp[i-2][j-1] * (i-1) * j

Phân tích:

• dp[i-1][j]: Bỏ qua hàng i.
• dp[i-1][j-1] * 4 * j: Thêm hàng i, và trong các cột cũ, có j cách chọn 1 cột để đặt học sinh mới. Nếu ta tập trung vào việc thêm hàng mới, ta có thể chọn 1 trong j cột để đặt 1 học sinh với 4 hướng.
• dp[i-2][j-1] * (i-1) * j: Thêm hàng i, và có một cặp học sinh mới (N/S hoặc W/E) được tạo ra. Điều này cần truy về dp[i-2][j-1].

Hàm mục tiêu là dp[R][C] - 1 (trừ trường hợp không có ai).

Cách Phân tích tổ hợp (Combinatorial Analysis)

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

const int MOD = 1e9 + 7;
const int MAX = 6005;

long long fact[MAX], invFact[MAX], inv2[MAX];

long long power(long long x, long long y) {
    long long res = 1;
    x %= MOD;
    while (y > 0) {
        if (y & 1) res = (res * x) % MOD;
        y >>= 1;
        x = (x * x) % MOD;
    }
    return res;
}

long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}

int main() {
    int R, C;
    cin >> R >> C;

    fact[0] = 1;
    for (int i = 1; i < MAX; i++) fact[i] = (fact[i - 1] * i) % MOD;
    invFact[MAX - 1] = power(fact[MAX - 1], MOD - 2);
    for (int i = MAX - 2; i >= 0; i--) invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;

    inv2[0] = 1;
    long long inv_2 = power(2, MOD - 2);
    for (int i = 1; i < MAX; i++) inv2[i] = (inv2[i - 1] * inv_2) % MOD;

    long long ans = 0;
    // Tong hop cac truong hop theo so luong W (w) va E (e) trong hang
    // Tuong tu cho N (n) va S (s) trong cot
    // De y rang: W phai o ben trai E, N phai o ben tren S.
    // Do do, chung ta chi can xet so luong (w, e) va (n, s)

    // Cong thuc tinh toan:
    // Ans = Sum_{k=0}^{min(R,C)} C(min(R,C), k) * 2^k * S(R, k) * S(C, k) * (k!)^2 ?
    // Khong, day khong phai Stirling.

    // Cach tiep can tu cac solution:
    // Khoi tao: 1 (Empty)
    // Cong them:
    // 1. Dat 1 hoc sinh: 4 * R * C
    // 2. Dat nhieu hon: Phuc tap.

    // Cach 1: Duyet w, e, n, s.
    // Dieu kien: w + e <= C, n + s <= R.
    // W: chon w hang co w > 0, chon w cot co n >= w.
    // E: chon e hang co e > 0, chon e cot co s >= e.
    // N: chon n cot co n > 0, chon n hang co w >= n.
    // S: chon s cot co s > 0, chon s hang co e >= s.

    // Cach don gian hon tu DP:
    // Ans = (R+1) * (C+1) * 2^(R+C) ? Khong.
    // 
    // Dung nhat tu solution 1:
    // Cach 1 (don gian nhat):
    // Tong quat hoa tu DP.
    // Ans = 1 + sum_{r=1}^R sum_{c=1}^C C(R, r) * C(C, c) * F(r, c)
    // Trong do F(r, c) so cach dat tren bang r x c.
    // 
    // Cach 2 (Optimal):
    // Khoi tao ans = 1.
    // Cong them:
    // - Cac truong hop chi co 1 cot: 2^R - 1 (R cach dat N/S) + R (R cach dat W/E) ?
    // 
    // Dung nhat: 
    // Sum_{i=0}^{R} Sum_{j=0}^{C} C(R, i) * C(C, j) * 2^{i+j} * (i+j)! / (i! j!)? Khong.
    // 
    // Phan tich tu bai toan:
    // Moi hang i co 2 bien W_i, E_i.
    // Moi cot j co 2 bien N_j, S_j.
    // Tong so cach = Sum_{config} 1.
    // 
    // Giai phap tu solution 1:
    // dp[i][j] la so cach
    // Cong thuc: dp[i][j] = dp[i-1][j] + dp[i-1][j-1]*4*j + dp[i-2][j-1]*(i-1)*j
    // Tinh toan O(R*C).
    // 
    // Cong thuc dong (kho):
    // Ans = sum_{k=0}^{min(R,C)} C(R, k) * C(C, k) * 2^k * k! * S(R, k) * S(C, k)? 
    // Khong.
    // 
    // Dung lai:
    // DP[i][j] = so cach xep i hang, j cot.
    // 1. Hang i rong: DP[i-1][j]
    // 2. Hang i co 1 hoc sinh (W/E/N/S):
    //    Neu dat W/E: Can 1 cot.
    //    Neu dat N/S: Can 1 cot.
    //    Tat ca 4 huong deu can 1 cot.
    //    Vay them hang i, chon 1 cot: 4 * j * DP[i-1][j-1]
    // 3. Hang i co 2 hoc sinh (W va E) va cung cot j co 2 hoc sinh (N va S):
    //    2 hoc sinh o hang i (W, E) va cot j (N, S).
    //    Nhuong dinh: DP[i-2][j-1] * (i-1) * j.
    //    
    // Code:
    // dp[0][0] = 1;
    // for(i...)
    // for(j...)
    // dp[i][j] = (dp[i-1][j] + dp[i-1][j-1]*4*j + (i>=2 ? dp[i-2][j-1]*(i-1)*j : 0)) % MOD;
    // ans = dp[R][C] - 1.

    // Day la cach hieu don gian nhat va chinh xac nhat.
    // Cac solution 2 va 3 cung su dung DP nay.

    long long dp[C + 1];
    long long dp_prev[C + 1];

    for (int j = 0; j <= C; j++) {
        dp[j] = 1;
    }

    for (int i = 1; i <= R; i++) {
        dp_prev[0] = 1;
        for (int j = 1; j <= C; j++) {
            long long term1 = dp[j]; // dp[i-1][j] - khong dat o hang i
            long long term2 = dp[j-1] * 4 % MOD * j % MOD; // dat 1 o hang i
            long long term3 = 0;
            if (i >= 2) {
                term3 = dp_prev[j-1] * (i-1) % MOD * j % MOD; // dat 2 o hang i
            }
            dp_prev[j] = (term1 + term2 + term3) % MOD;
        }
        for (int j = 0; j <= C; j++) dp[j] = dp_prev[j];
    }

    long long ans = (dp[C] - 1 + MOD) % MOD;
    cout << ans << endl;
    return 0;
}

• Time Complexity: O(R * C)
• Space Complexity: O(C)

Cách tiếp cận này dựa trên việc tổng quát hóa quy hoạch động. Thay vì chỉ xét các trường hợp cơ bản, ta xét tổng số cách cho R hàng và C cột.

Công thức: dp[i][j] = dp[i-1][j] + 4*j*dp[i-1][j-1] + (i-1)*j*dp[i-2][j-1]

Giải thích các thành phần:

1. dp[i-1][j]: Trường hợp hàng thứ i không có học sinh nào.
2. 4*j*dp[i-1][j-1]: Trường hợp hàng thứ i có đúng 1 học sinh.
   • Khi thêm hàng i, ta có j cột.
   • Nếu ta chọn đặt 1 học sinh, có 4 hướng (W, E, N, S).
   • Tuy nhiên, để thỏa mãn ràng buộc với các hàng/cột khác, việc thêm 1 học sinh vào hàng i thường tương ứng với việc chọn 1 trong j cột.
   • Vế 4*j thể hiện việc chọn 1 cột và 1 hướng.
   • dp[i-1][j-1] là cách sắp xếp cho phần còn lại.
3. (i-1)*j*dp[i-2][j-1]: Trường hợp hàng thứ i có 2 học sinh (W và E) và cột thứ j có 2 học sinh (N và S).
   • Điều này có nghĩa là ta đang tạo ra một "điểm giao" mới.
   • j là cách chọn cột.
   • (i-1) là cách chọn hàng cho các học sinh N/S.
   • dp[i-2][j-1] là cách sắp xếp cho phần còn lại.

Cách tiếp cận này là trực tiếp nhất để tính toán kết quả.

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

Bài học kinh nghiệm

• Ràng buộc về hướng (W/E/N/S) quy định rằng trên mỗi hàng, các học sinh W phải nằm bên trái các học sinh E. Trên mỗi cột, các học sinh N phải nằm bên trên các học sinh S.
• Bài toán có thể được quy hoạch động bằng cách xây dựng lưới theo hàng hoặc cột. Trạng thái dp[i][j] có ý nghĩa là số cách sắp xếp hợp lệ cho i hàng và j cột.
• Công thức chuyển trạng thái dp[i][j] dựa trên việc xem xét các trường hợp: (1) Hàng i rỗng, (2) Hàng i có 1 học sinh, (3) Hàng i có 2 học sinh (tương ứng với 2 học sinh trên cột j).

Lỗi thường gặp

• Đặt sai công thức chuyển trạng thái, ví dụ quên nhân với các hệ số như 4*j hay (i-1)*j.
• Quên trừ đi 1 trường hợp rỗng (empty configuration) trong kết quả cuối cùng, vì bài toán yêu cầu "ít nhất một học sinh".
• Lỗi tràn số (integer overflow) khi tính toán các tích lớn, cần sử dụng long long và chia lấy dư thường xuyên.
• Sử dụng sai thứ tự các chỉ số trong DP (ví dụ dp[i-1][j-1] thay vì dp[i-2][j-1] cho trường hợp 2 học sinh).