Editorial for mdist: Khoảng cách xa nhất

Hiểu bài toán

Bài toán yêu cầu tìm khoảng cách Manhattan lớn nhất giữa hai điểm bất kỳ trong N điểm cho trước. Khoảng cách Manhattan giữa hai điểm (x1, y1) và (x2, y2) được định nghĩa là |x1 - x2| + |y1 - y2|. Với N tối đa là 100, ta cần tìm giá trị lớn nhất của biểu thức này trong tất cả các cặp điểm.

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

Cách Brute Force (Lặp kép)

#include <stdio.h>
#include <math.h>

int main() {
    int n;
    scanf("%d", &n);
    int x[105], y[105];
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &x[i], &y[i]);
    }
    int max_dist = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int dist = abs(x[i] - x[j]) + abs(y[i] - y[j]);
            if (dist > max_dist) {
                max_dist = dist;
            }
        }
    }
    printf("%d", max_dist);
    return 0;
}

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

Đây là cách tiếp cận trực tiếp nhất. Ta duyệt qua tất cả các cặp điểm (i, j) với i < j để tránh tính toán trùng lặp. Với mỗi cặp, ta tính khoảng cách Manhattan và cập nhật giá trị lớn nhất. Với N <= 100, số lượng cặp là khoảng 5000, hoàn toàn chấp nhận được trong thời gian chạy.

Cách Optimized (Tối ưu hóa Manhattan)

#include <stdio.h>
#include <limits.h>
#include <math.h>

int main() {
    int n;
    scanf("%d", &n);
    int min_sum = INT_MAX, max_sum = INT_MIN;
    int min_diff = INT_MAX, max_diff = INT_MIN;

    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        // Biến đổi tọa độ
        // P1: (x + y)
        // P2: (x - y)
        if (x + y < min_sum) min_sum = x + y;
        if (x + y > max_sum) max_sum = x + y;
        if (x - y < min_diff) min_diff = x - y;
        if (x - y > max_diff) max_diff = x - y;
    }

    int dist1 = max_sum - min_sum;
    int dist2 = max_diff - min_diff;

    if (dist1 > dist2) printf("%d", dist1);
    else printf("%d", dist2);

    return 0;
}

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

Cách tiếp cận này sử dụng tính chất của khoảng cách Manhattan. Ta có thể biến đổi công thức: |x1 - x2| + |y1 - y2| = max( |(x1+y1) - (x2+y2)|, |(x1-y1) - (x2-y2)| ). Do đó, thay vì xét tất cả cặp điểm, ta chỉ cần tìm giá trị lớn nhất và nhỏ nhất của (x+y) và (x-y). Khoảng cách lớn nhất sẽ là hiệu giữa giá trị lớn nhất và nhỏ nhất của một trong hai biến đổi này. Độ phức tạp giảm từ O(N^2) xuống O(N).

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

Bài học kinh nghiệm

• Khoảng cách Manhattan giữa hai điểm có thể được biểu diễn qua các hàm max của các hiệu tọa độ biến đổi.
• Với N nhỏ (<= 100), giải thuật O(N^2) hoàn toàn khả thi và dễ implement.

Lỗi thường gặp

• Quên sử dụng hàm abs() khi tính hiệu, dẫn đến kết quả âm sai lệch.
• Khởi tạo biến max ban đầu sai (ví dụ bằng 0 thay vì -1 hoặc giá trị của cặp đầu tiên) có thể sai nếu tất cả khoảng cách đều nhỏ hơn 0 (trong bài này khoảng cách luôn >= 0 nên 0 là an toàn, nhưng logic chung nên cẩn thận).
• Biến đổi công thức |x1 - x2| + |y1 - y2| = max(|(x1+y1)-(x2+y2)|, |(x1-y1)-(x2-y2)|) là một kiến thức hữu ích nhưng với N nhỏ thì vòng lặp kép đơn giản và ít lỗi hơn.