Editorial for chess: Cờ vua

Hiểu bài toán

Bài toán yêu cầu tính tổng khoảng cách ngắn nhất để N con vua (vua cờ vua, di chuyển sang 8 ô kề nhau, tức là di chuyển theo hình vuông hoặc theo hàng chéo - Chebyshev distance) di chuyển về cùng một vị trí đích (a, b) cho trước. Với mỗi truy vấn, ta cần tìm tọa độ đích để tổng chi phí di chuyển là nhỏ nhất, và tính giá trị tổng đó.

Vua di chuyển theo Chebyshev distance: Khoảng cách từ (x1, y1) đến (x2, y2) là max(|x1 - x2|, |y1 - y2|).

Định lý: max(|dx|, |dy|) = (|dx + dy| + |dx - dy|) / 2.

Đặt U = x - y, V = x + y. Khoảng cách Chebyshev giữa hai điểm A, B tương đương với khoảng cách Manhattan giữa hai điểm (UA, VA) và (UB, VB) chia cho 2.

Vậy bài toán quy về: Với các điểm (Ui, Vi), tìm điểm (U', V') để tổng khoảng cách Manhattan sum(|Ui - U'| + |Vi - V'|) là nhỏ nhất. Sau đó chia đôi tổng đó.

Điểm đặc biệt là U' và V' có thể được chọn độc lập để tối thiểu hóa tương ứng tổng |Ui - U'| và |Vi - V'|. Với tổng khoảng cách Manhattan, giá trị tối ưu nằm giữa các giá trị Ui (hoặc Vi) đã cho. Cụ thể, trung vị là giá trị tối ưu.

Tuy nhiên, trong các giải pháp chấp nhận, người ta tính tổng khoảng cách đến một điểm đích cho trước (query point) chứ không cần tìm điểm tối ưu. Với mỗi truy vấn (a, b), ta biến đổi thành (Uq, Vq) và tính sum(|Ui - Uq|) + sum(|Vi - Vq|).

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

Cách Brute Force (Duyệt toàn bộ)

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<pair<long long, long long>> kings(n);
    for (int i = 0; i < n; i++) {
        cin >> kings[i].first >> kings[i].second;
    }
    while (q--) {
        long long a, b;
        cin >> a >> b;
        long long total_dist = 0;
        for (int i = 0; i < n; i++) {
            long long dx = abs(kings[i].first - a);
            long long dy = abs(kings[i].second - b);
            total_dist += max(dx, dy);
        }
        cout << total_dist << '\n';
    }
}

• Time Complexity: O(N * Q)
• Space Complexity: O(N)

Đây là cách giải quyết trực tiếp nhất. Với mỗi truy vấn, ta duyệt qua từng con vua, tính khoảng cách Chebyshev từ nó đến điểm đích (a, b) và cộng dồn vào tổng. Phù hợp với các test nhỏ (ví dụ N*Q <= 10^8 theo đề bài). Với N, Q lên tới 10^5, độ phức tạp O(10^10) sẽ quá chậm.

Cách Biến đổi tọa độ và Prefix Sum

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    vector<ll> u(N), v(N);
    for (int i = 0; i < N; ++i) {
        ll x, y;
        cin >> x >> y;
        u[i] = x - y;
        v[i] = x + y;
    }

    // Sắp xếp và tính tổng tiền tố
    sort(u.begin(), u.end());
    sort(v.begin(), v.end());

    vector<ll> pref_u(N + 1, 0), pref_v(N + 1, 0);
    for (int i = 0; i < N; ++i) {
        pref_u[i + 1] = pref_u[i] + u[i];
        pref_v[i + 1] = pref_v[i] + v[i];
    }

    while (Q--) {
        ll a, b;
        cin >> a >> b;
        ll u_target = a - b;
        ll v_target = a + b;

        // Tính sum |u[i] - u_target|
        auto it_u = lower_bound(u.begin(), u.end(), u_target);
        int idx_u = it_u - u.begin();
        ll sum_u = (u_target * idx_u - pref_u[idx_u]) + 
                   ((pref_u[N] - pref_u[idx_u]) - u_target * (N - idx_u));

        // Tính sum |v[i] - v_target|
        auto it_v = lower_bound(v.begin(), v.end(), v_target);
        int idx_v = it_v - v.begin();
        ll sum_v = (v_target * idx_v - pref_v[idx_v]) + 
                   ((pref_v[N] - pref_v[idx_v]) - v_target * (N - idx_v));

        // Kết quả là (sum_u + sum_v) / 2
        cout << (sum_u + sum_v) / 2 << '\n';
    }
    return 0;
}

• Time Complexity: O(N log N + Q log N)
• Space Complexity: O(N)

1. Biến đổi tọa độ: Đặt u = x - y, v = x + y. Khoảng cách Chebyshev max(|dx|, |dy|) = (|du| + |dv|) / 2.
2. Bài toán trở thành tính tổng khoảng cách Manhattan: sum(|ui - uq| + |vi - vq|) / 2.
3. Tối ưu hóa tính sum(|arr[i] - val|) bằng cách sắp xếp mảng arr và dùng mảng tổng tiền tố (prefix sum).
4. Với một giá trị val, dùng binary search (lower_bound) để tìm số lượng phần tử nhỏ hơn val. Gọi chỉ số là k.
5. Giá trị tổng là: val * k - sumcacphantunhohon + sumcacphantulonhonorbang - val * (N - k).
6. Áp dụng cho cả u và v, rồi cộng lại và chia 2.

Cách Tối ưu với Median (Tìm điểm gặp mặt lý tưởng)

// Chỉ minh họa logic tìm điểm tối ưu, không phải giải quyết truy vấn ngẫu nhiên
// Tuy nhiên, nếu truy vấn yêu cầu tìm TỔNG NHỎ NHẤT (không bắt buộc phải qua điểm cụ thể):
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<long long> u(n), v(n);
    for(int i=0; i<n; ++i) {
        long long x, y;
        cin >> x >> y;
        u[i] = x - y;
        v[i] = x + y;
    }
    sort(u.begin(), u.end());
    sort(v.begin(), v.end());

    long long median_u = u[n/2];
    long long median_v = v[n/2];

    // Tính tổng khoảng cách đến median
    long long sum_u = 0, sum_v = 0;
    for(long long val : u) sum_u += abs(val - median_u);
    for(long long val : v) sum_v += abs(val - median_v);

    // Kết quả nhỏ nhất có thể là (sum_u + sum_v) / 2
    // Lưu ý: Nếu n chẵn, bất kỳ giá trị nào giữa 2 giá trị ở giữa đều tối ưu.

    // Code này chỉ giải quyết 1 truy vấn duy nhất (tìm tổng nhỏ nhất).
    // Để xử lý Q truy vấn (a, b) như đề bài, cần dùng Approach 2.
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Nếu câu hỏi chỉ yêu cầu tìm tổng khoảng cách ngắn nhất mà không cần chỉ ra điểm gặp cụ thể (hoặc điểm gặp là trung vị):

1. Biến đổi sang (u, v).
2. Với tọa độ u, giá trị tối ưu để lấy tổng |u_i - u'| nhỏ nhất là trung vị (median) của mảng u.
3. Tương tự với v.
4. Tính tổng khoảng cách đến trung vị. Lưu ý: Đề bài yêu cầu tính tổng đến một điểm đích cho trước (ai, bi), nên Approach 2 là chính xác nhất. Approach này chỉ minh họa tính chất tối ưu của bài toán.

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

Bài học kinh nghiệm

• Chebyshev distance max(|dx|, |dy|) có thể chuyển đổi thành Manhattan distance (|dx+dy| + |dx-dy|) / 2 bằng cách xoay và scale tọa độ.
• Bài toán tính tổng khoảng cách absolutes với nhiều truy vấn có thể giải quyết hiệu quả bằng cách sắp xếp và sử dụng mảng tổng tiền tố (Prefix Sum).

Lỗi thường gặp

• Sai đơn vị/kiểu dữ liệu: Tọa độ lên tới 10^9, khoảng cách và tổng có thể vượt quá giới hạn của int 32-bit. Phải dùng long long (int64).
• Lỗi logic biến đổi:混淆 Chebyshev và Manhattan distance.
• Hiệu năng: Dùng brute force cho Q lớn sẽ bị TLE.