Nhận xét: Giả sử người dân ở địa điểm ~(x, y)~ đi đến khu chợ tại ~(p, q)~, rồi về nhà tại ~(a, b)~. Ta có tổng khoảng cách di chuyển của người này là ~|x - p| + |y - q| + |a - p| + |b - q|~. Vì các khu chợ cùng nằm trên một đường ngang (hay các ~p_i~ của các khu chợ là như nhau), và ~y, q~ không liên quan đến ~p~ trong đáp án tổng, nên ta có thể tách bài toán thành hai bài toán riêng biệt:

1. Chọn ra tọa độ ~p~ để tối thiểu hóa ~\sum_{i = 1}^d (|x_i - p| + |a_i - p|)~
2. Chọn ra các tọa độ ~q_1, q_2, \ldots, q_k~ là cột của các khu chợ, và chọn ra ~c_1, c_2, \ldots, c_d~ là khu chợ mà người thứ ~i~ sẽ lựa chọn. Ta cần tối thiểu hóa ~\sum_{i = 1}^d (|y_i - q_{c_i}| + |b_i - q_{c_i}|)~

Bài toán 1 thì ta chỉ cần lấy ~p~ là trung vị của các tọa độ ~x, a~, nên lời giải sẽ chỉ tập trung vào bài toán 2.

Subtask 1 & 2

Ta có ~b_i = y_i~, nên tổng được viết lại thành ~\sum_{i = 1}^d 2 \cdot |y_i - q_{c_i}|~. Khi đó bài toán trở thành: Chọn ~k~ điểm trên một trục tọa độ, sao cho tổng khoảng cách nhỏ nhất từ mỗi điểm ~y_i~ đến một trong các điểm được chọn là nhỏ nhất. Khi đó ta có thể sử dụng quy hoạch động:

• Gọi ~f(i, j)~ là tổng nhỏ nhất khi xét đến điểm thứ ~i~, và đã chọn ~j~ điểm. Đồng thời ta cũng có hàm ~cost(l, r)~ là cách chọn một điểm để tổng khoảng cách của các điểm trong đoạn ~l, r~ đến điểm đó là nhỏ nhất. Hàm ~cost(l, r)~ này giống hệt bài toán 1.
• Ta có công thức chuyển vị: ~f(i, j) = min \ f(k, j - 1) + cost(k + 1, i)~.

Vì ~d \le 3000~ nên ta có thể tính trước ~cost(l, r)~ vào một mảng, sau đó thực hiện quy hoạch động. Việc tính ~cost(l, r)~ xin được nhường lại cho người đọc.

ĐPT: ~O(d^2 \cdot k)~.

Subtask 3 & 4

Để giải quyết các subtask từ subtask 3 trở đi, ta cần một nhận xét quan trọng:

• Không mất tính tổng quát ta giả sử ~y \le b~. Giả sử ta đã chọn ra các điểm ~q_1, q_2, \ldots q_k~. Khi đó nếu ~i~ là điểm mà tối thiểu hóa tổng ~|y - q_i| + |b - q_i|~ thì ~i~ cũng là điểm mà gần với điểm ~\displaystyle \frac{y + b}{2}~ nhất, hay nói cách khác là gần với trung điểm đoạn ~[y, b]~ nhất.

Chứng minh:

Ta xét hai điểm ~S, T~ bất kì. nếu ~y \le S, T \le b~ thì ta có ~|y - S| + |b - S| = |y - T| + |b - T|~, nên ta sẽ chỉ xét các trường hợp sau:

• ~S~ thuộc đoạn ~[y, b]~, ~T~ nằm ngoài đoạn ~[y, b]~. Lúc này hiển nhiên chọn điểm ~T~ sẽ tối ưu hơn, và đồng thời ~T~ cũng gần trung điểm đoạn ~[y, b]~ hơn. Trường hợp ~S~ nằm ngoài và ~T~ thuộc đoạn cũng tương tự.
• ~S~ và ~T~ cùng nằm ngoài đoạn ~[y, b]~. Gọi trung điểm đoạn ~[y, b]~ là ~M~. Nếu ~S, T~ cùng nằm ở phía bên trái hoặc bên phải so với đoạn ~[y, b]~, ta hoàn toàn có thể chọn điểm ở bên phải hoặc ở bên trái tương ứng, và hiển nhiên điểm này cũng gần ~M~ hơn. Vì vậy ta sẽ chỉ xét trường hợp mà ~S, T~ nằm khác phía, không mất tính tổng quát ta giả sử ~S \lt y \le b \lt T~ và ~S~ là điểm cho tổng nhỏ hơn.

Ta có ~|y - S| + |b - S| = 2(b - y) + (y - S) < |y - T| + |b - T| = 2(b - y) + (T - b)~, suy ra ~y - S < T - b~. Vì ~M~ là trung điểm nên ~M - y = b - M~, cộng tương ứng hai vế ta thu được ~M - S < T - M~, hay điểm ~S~ gần trung điểm ~M~ hơn so với điểm ~T~.

Từ nhận xét trên, ta có thể sắp xếp lại các điểm theo ~y_i + b_i~ tăng dần, và thực hiện quy hoạch động giống subtask 1 và 2.

Độ phức tạp: ~O(d^2 \cdot k)~.

Subtask 5

Ta tối ưu quy hoạch động bằng chia để trị. Để tính ~cost(l, r)~, ta có thể sử dụng thêm Persistent Segment Tree để tìm trung vị và tìm tổng.

Độ phức tạp: ~O(k \cdot d \cdot \log^2 d)~.