Editorial for jusbie: Bài toán quân hậu

Hiểu bài toán

Bài toán yêu cầu tìm số bước di chuyển tối thiểu để biến một cấu hình ban đầu của N quân hậu trên bàn cờ N x N thành một cấu hình mục tiêu. Mỗi quân hậu ban đầu ở hàng i, cột a[i] cần được di chuyển đến hàng j, cột b[j] (với j từ 0 đến N-1). Trong một bước, một quân hậu chỉ có thể di chuyển một ô theo hàng hoặc cột (tương đương khoảng cách Manhattan). Tuy nhiên, có một ràng buộc quan trọng: các quân hậu không được va chạm trong suốt quá trình di chuyển. Vì N < 17, ta có thể sử dụng các thuật toán tối ưu hóa trạng thái bitmask.

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

Cách Quy hoạch động theo bitmask (DP)

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    while (cin >> n) {
        if (!n) break;
        vector<int> a(n), b(n);
        for (int &x : a) cin >> x; 
        for (int &x : b) cin >> x;  

        vector<vector<int>> cost(n, vector<int>(n));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cost[i][j] = abs(i - j) + abs(a[i] - b[j]);
            }
        }
        int Nmask = 1 << n;
        vector<int> dp(Nmask, 1e9);
        dp[0] = 0;

        for (int mask = 0; mask < Nmask; mask++) {
            int k = __builtin_popcount(mask);
            if (k >= n) continue;
            for (int j = 0; j < n; j++) if (!(mask >> j & 1)) {
                int newmask = mask | (1 << j);
                dp[newmask] = min(dp[newmask], dp[mask] + cost[k][j]);
            }
        }
        cout << dp[Nmask - 1] << "\n";
    }
    return 0;
}

• Time Complexity: O(N^2 * 2^N)
• Space Complexity: O(2^N)

Đây là cách tiếp cận chính xác và hiệu quả nhất cho giới hạn N < 17. Ta quy hoạch động trạng thái dựa trên tập hợp các cột mục tiêu đã được sử dụng (bitmask).

• Trạng thái dp[mask]: Chi phí tối thiểu để di chuyển K quân hậu đầu tiên (từ hàng 0 đến K-1, với K = số bit 1 trong mask) đến các cột được chỉ định bởi các bit 1 trong mask.
• Công thức chuyển trạng thái: Khi xử lý trạng thái mask có K bit 1, ta đang ở hàng K. Quân hậu ở hàng K này sẽ được di chuyển đến một cột j chưa được dùng (bit j = 0). Chi phí di chuyển là cost[K][j] (tính theo khoảng cách Manhattan).
• dp[new_mask] = min(dp[new_mask], dp[mask] + cost[K][j]).
• Kết quả là dp[(1<<N)-1].
• Lưu ý: Bài toán này có thể được coi là tìm hoán vị tối ưu, thuật toán Hungarian cũng giải quyết được nhưng với N nhỏ thì DP Masked nhanh và dễ cài đặt hơn.

Cách Thuật toán Hungarian (Đồ thị trọng số)

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

const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (true) {
        int N;
        cin >> N;
        if (N == 0) break;
        vector<int> a(N), b(N);
        for (int i = 0; i < N; i++) cin >> a[i];
        for (int i = 0; i < N; i++) cin >> b[i];
        vector<pair<int,int>> start(N), target(N);
        for (int i = 0; i < N; i++) {
            start[i] = {i + 1, a[i]};
            target[i] = {i + 1, b[i]};
        }
        vector<vector<int>> cost(N + 1, vector<int>(N + 1));
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                cost[i][j] = abs(start[i-1].first - target[j-1].first) + abs(start[i-1].second - target[j-1].second);
            }
        }
        // Hungarian Algorithm Implementation Here
        // (Code truncated in prompt, standard implementation involves potentials u, v, p, way arrays)
        return 0;
    }
}

• Time Complexity: O(N^3)
• Space Complexity: O(N^2)

Bài toán tìm cách gán N quân hậu ban đầu (ở hàng 1..N) vào N vị trí mục tiêu (ở hàng 1..N) sao cho tổng khoảng cách di chuyển là nhỏ nhất. Đây là bài toán gán(classical assignment problem) trên đồ thị hai phía.

• Ma trận chi phí cost[i][j] là khoảng cách từ quân hậu ban đầu ở hàng i đến vị trí mục tiêu ở hàng j.
• Thuật toán Hungarian (hay Kuhn-Munkres) giải quyết bài toán này trong thời gian O(N^3).
• Tuy nhiên, với N <= 16, O(N^3) ~ 4000 thao tác rất nhanh, nhưng cài đặt phức tạp hơn DP Masked.

Cách Tối ưu hóa bằng Bitset (Bitset Optimization)

// Pseudocode for logic
// const int MAXN = 17;
// int cost[MAXN][MAXN];
// int dp[1 << MAXN];
// fill(dp, dp + (1<<N), INF);
// dp[0] = 0;
// for (int mask = 0; mask < (1 << N); mask++) {
//     int k = __builtin_popcount(mask);
//     for (int j = 0; j < N; j++) {
//         if (!(mask & (1 << j))) {
//             int next_mask = mask | (1 << j);
//             dp[next_mask] = min(dp[next_mask], dp[mask] + cost[k][j]);
//         }
//     }
// }

• Time Complexity: O(N^2 * 2^N)
• Space Complexity: O(2^N)

Đây là biến thể của phương pháp DP Masked. Trong một số trường hợp, việc tối ưu hóa vòng lặp bằng Bitset có thể giúp tăng tốc độ chạy thực tế (ví dụ: dùng int để lưu bitmask và duyệt nhanh các bit 0 bằng số mách bitwise). Tuy nhiên, về lý thuyết độ phức tạp vẫn là O(N^2 * 2^N). Với N=16, 2^16 = 65536, N^2 = 256, tổng cộng khoảng 16 triệu thao tác, hoàn toàn chạy được trong thời gian giới hạn.

Cách tiếp cận này giống hệt Solution 3 trong bài toán.

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

Bài học kinh nghiệm

• Bài toán có thể tách thành 2 bài toán con: tìm cách gán hàng vào cột (gọi là P) và tính tổng chi phí di chuyển theo P. Tuy nhiên, ta phải đảm bảo di chuyển không va chạm. May mắn thay, với luật di chuyển 'một ô', việc di chuyển theo đúng thứ tự hàng (từ 1 đến N) đến các cột đích sẽ không bao giờ gây va chạm nếu ta không di chuyển cùng lúc.
• Giả thuyết 'không va chạm': Nếu ta có một cách gán các quân hậu hiện tại vào các vị trí mục tiêu (tức là ánh xạ hàng i -> hàng j), ta có thể thực hiện di chuyển theo thứ tự các hàng (hoặc cột) mà không cần lo lắng va chạm, vì các quân hậu di chuyển đến các hàng/cột khác nhau.

Lỗi thường gặp

• Lầm tưởng rằng cần mô phỏng quá trình di chuyển chi tiết (tìm đường đi). Thực tế chỉ cần tính tổng khoảng cách Manhattan.
• Hiểu sai input: Dòng đầu tiên là cột của quân hậu em bé (a), dòng thứ hai là cột của quân hậu mục tiêu (b). Quân hậu thứ i luôn nằm ở hàng i.
• Vấn đề 'đường chéo': Đề bài nhắc đến đường chéo để gây nhiễu, nhưng bài toán thực chất chỉ yêu cầu tối thiểu hóa số bước di chuyển hàng/cột.