~\color{orange}{\text{Hướng dẫn}}~

• Gọi cách chia ~X~ là chia ~2n~ chương trình thành ~n~ cặp ~(A_1, B_1), (A_2, B_2), \dots, (A_n, B_n)~

Gọi thời gian xử lí của một cặp ~(A_i, B_i)~ là ~f(A_i, B_i)~

Thời gian xử lí toàn bộ chương trình cách chia ~P~ là ~g(X) = max(f(A_i, B_i))~

Yêu cầu bài toán là tìm ~res = min(g(X)) = min(max(f(A_i, B_i)))~ [1]

• Với mỗi cặp ~(A, B)~

Từ [1] ta có ~f(A, B)~ càng nhỏ càng tốt, nên ta phải tìm cách để xử lí 2 chương trình một cách tối ưu

Khi phát xung nhịp, gọi ~a~ là kí tự đầu của ~A~ và ~b~ là kí tự đầu của ~B~

Khi ~a = b~ thì ta loại cả ~a~ và ~b~ cùng lúc và tăng một đơn vị thời gian

Khi ~a \neq b~ thì ta sẽ thử loại một trong hai và tăng một đơn vị thời gian

~\color{goldenrod}{\text{Tiếp cận}}~

• Để xử lí cặp ~(A, B)~, ta dùng quy hoạch động đếm

Xét ~f(i, j)~ là thời gian nhỏ nhất để loại bỏ ~A[i \dots n]~ và ~B[j \dots m]~ với ~n = |A|~ và ~m = |B|~

Khi ~A_i = B_j~ thì ~f(i, j) = f(i + 1, j + 1) + 1~

Khi ~A_i \neq B_i~ thì ~f(i, j) = min(f(i + 1, j), f(i, j + 1)) + 1~

• Để xử lí ~res = min(max(f(A_i, B_i)))~, ta dùng quy hoạch động trạng thái

Vì ~2n~ nhỏ, xét ~2^{2n}~ trạng thái ~S~ đánh dấu các chương trình đã được ghép cặp

Khi xét tới chương trình thứ ~i~ chưa được ghép cặp, ta thử xét trong ~2n~ chương trình còn lại có cái nào chưa ghép cặp ta ghép luôn

~g(i, S) = min\Bigg(\ max\bigg(\ g(i + 1, S\ \cup~ {~\ j\ ~}~\ )\ \ ,\ \ f(A_i, A_j)\ \bigg)\ \Bigg)~

• Khi đó kết quả bài toán sẽ là ~res = min(g(i, S))~

~\color{purple}{\text{Độ phức tạp}}~

• Với cách đề cập trên

Có tất cả ~O(n \times 2^{2n})~ giá trị ~g(i, S)~ cần duyệt qua để tính ~res~

Hàm ~g(i, S)~ chuyển trạng thái mất ~|S| \times f(i, j) = 2n \times |A_i| \times |A_j|~

Vậy độ phức tạp rơi vào khoảng ~O(2n^2 \times 2^{2n} \times max(|A_i|)^2)~

Có thể coi là ~O(2^{2n})~ với hằng số cao

• Tối ưu

Ta truyền bitmask thay vì tập đánh dấu

Ta sẽ tiền xử lí tính toán trước các giá trị ~f(i, j)~

Ta sẽ luôn ghép cặp từ thằng ~i~ với các thằng khác, nên biến ~i~ là không quan trọng, vì với mọi ~S~ bất kì ta có thểm tìm được ~i~ tương ứng

Độ phức tạp lúc này chỉ còn ~O(n^2 \times max(|A_i|)^2 + 2^{2n})~

~\color{green}{\text{Code tham khảo }}~: Approach

~^{^{\color{purple}{\text{Độ phức tạp : }} O(2^{2n})\ \color{purple}{\text{thời gian}}\ ||\ O(2^{2n})\ \color{purple}{\text{bộ nhớ}}}}~

const int INF = 0x3f3f3f3f;
const int LIM = 111;

int n, k;
string a[111];
int cost[111][111];

string u, v;
int f[111][111];

/// Solve for each pair
int calc(int i = 0, int j = 0)
{
    if (i >= u.size()) return int(v.size()) - j; /// da xoa het (u), con lai (|v| - j) ki tu cua (v)
    if (j >= v.size()) return int(u.size()) - i; /// tuong tu nhu tren

    int &res = f[i][j];
    if (res != -1) return res;
    res = +INF;

    res = min(calc(i + 1, j), calc(i, j + 1)) + 1;
    if (u[i] == v[j])
        minimize(res, calc(i + 1, j + 1) + 1);

    return res;
}

int g[1 << 22];
/// Solve for all pairs
int solve(int i = 1, int mask = 0)
{
    if (i > n) return 0;
    if (mask >> i & 1) return solve(i + 1, mask);

    int &res = g[mask];
    if (res != -1) return res;
    res = +INF;

    for (int j = i + 1; j <= n; ++j)
    {
        if (mask >> j & 1) continue; /// (j) is used
        minimize(res, max(solve(i + 1, mask | (1 << j)), cost[i][j]));
    }

    return res;
}

int main()
{
    /// Input
    cin >> n;
    k = 1 * n;
    n = 2 * n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    /// Precalculating
    for (int i = 1; i <= n; ++i)
    {
        for (int j = i + 1; j <= n; ++j)
        {
            u = a[i];
            v = a[j];
            memset(f, -1, sizeof(f));
            cost[i][j] = cost[j][i] = calc();
        }
    }

    /// Solving
    memset(g, -1, sizeof(g));
    cout << solve();
    return 0;
}