Phân tích

Nếu đặt bến xe buýt ở tất cả các điểm nguyên trên lưới 1000×1000, thì điều kiện khoảng cách của bài toán chắc chắn được thỏa mãn.
Tuy nhiên khi đó tổng cộng sẽ có 10^6 bến, vượt quá giới hạn cho phép \((10^4)\).
Ta có thể giả định rằng không có hàng hoặc cột nào trống hoàn toàn (không có bến nào), bởi vì nếu có, thì điểm đó không cần xét đến trong bài toán.
Điều này cho phép ta sử dụng nén tọa độ nén để giảm kích thước không gian.
Sau khi nén tọa độ, giả sử có \(N_x\) hoành độ và \(N_y\) tung độ, đặt bến xe buýt tại tất cả các giao điểm trong lưới nén.
Có thể đặt tối đa \(N_x × N_y\) bến, sẽ thoả mãn yêu cầu số lượng nếu \(N_x⋅N_y≤10^4\).
Ta cần giải pháp không đặt trên toàn bộ lưới. Xét ý tưởng sau

• Đặt bến ở tất cả điểm trong một cột duy nhất, chẳng hạn cột ở giữa.
• Khi đó, mỗi hàng có ít nhất một điểm giao với cột giữa → có thể đi từ bất kỳ điểm nào sang cột giữa, sau đó sang hàng đích.
• Ví dụ: từ \((x_1,y_1 )→(x_1,y_m )→(x_2,y_m )→(x_2,y_2 )\)
• Tức là khoảng cách thực sự \(=|x_1-x_2 |+|y_1-y_2 | →\) đúng bằng khoảng cách Manhattan.

Từ ý tưởng trên, xây dựng được giải pháp chia để trị.

Giải pháp chia để trị

• Chia: Chọn một cột m sao cho số lượng bến ở bên trái và số lượng bến ở bên phải cột m là gần bằng nhau.
• Trị: Đệ quy xử lí đặt bến thoả mãn điều kiện khoảng cách cho tập các bến bên trái, tập các bến bên phải
• \(Kết hợp\): Đặt bến ở toàn bộ các hàng giao với cột \(m\).

Kiểm tra điều kiện số lượng

Gọi \(f(N)\) là số lượng bến cần có với \(N\) bến ban đầu.
Ta có: \(f(N)=N+f(N/2)+f(N/2)\) (\(N\) là số bến trên cột \(m\))
Áp dụng định lí Thợ, suy ra \(f(N)=O(N log⁡N )\)
Với \(N≤1000\) thì \(N log⁡N<10^4\) thoả mãn điều kiện số lượng.

Giải thuật có độ phức tạp \(O(N log⁡N )\)