\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\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;
}