Post Office

Solution Approach

Precomputation: Cost of Serving a Range

For a contiguous group of villages $[i, j]$ served by a single optimally-placed post office, the optimal location is the median village $m = \lfloor(i+j)/2\rfloor$.

Define: \[ w[i][j] = \sum_{k=i}^{j} |x_k - x_m|, \quad m = \lfloor(i+j)/2\rfloor. \]

Proof (Proof of the recurrence $w[i][j] = w[i][j{-}1] + x_j - x_m$).

When extending from $[i, j{-}1]$ to $[i, j]$, the new median is $m' = \lfloor(i+j)/2\rfloor$. If $j - i$ is even, then $m' = m + 1$ where $m = \lfloor(i+j-1)/2\rfloor$ was the previous median. If $j - i$ is odd, then $m' = m$. In either case, the incremental cost formula $w[i][j] = w[i][j{-}1] + x_j - x_{m'}$ holds. This can be verified by noting that moving the median from $m$ to $m'$ changes costs symmetrically for the elements that switch sides, and $x_j - x_{m'}$ is the cost for the new village.

We compute $w[i][j]$ incrementally in $O(V^2)$ total time.

DP Formulation

Let $\mathrm{dp}[i][j]$ = minimum total distance for villages $1, \ldots, i$ using $j$ post offices.

Base case: $\mathrm{dp}[i][1] = w[1][i]$.

Transition: \[ \mathrm{dp}[i][j] = \min_{k = j-1}^{i-1} \bigl(\mathrm{dp}[k][j{-}1] + w[k{+}1][i]\bigr). \]

Answer: $\mathrm{dp}[V][P]$.

Reconstruction

Store the optimal split point $k$ in an auxiliary array $\mathrm{opt}[i][j]$. Trace backward to identify which group of villages each post office serves, placing each post office at the median of its group.

C++ Solution

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int V, P;
    scanf("%d %d", &V, &P);

    vector<int> x(V + 1);
    for (int i = 1; i <= V; i++)
        scanf("%d", &x[i]);

    // Precompute w[i][j] = cost of one post office serving villages i..j
    vector<vector<int>> w(V + 1, vector<int>(V + 1, 0));
    for (int i = 1; i <= V; i++) {
        for (int j = i + 1; j <= V; j++) {
            int med = (i + j) / 2;
            w[i][j] = w[i][j - 1] + x[j] - x[med];
        }
    }

    // DP
    const int INF = 1000000000;
    vector<vector<int>> dp(V + 1, vector<int>(P + 1, INF));
    vector<vector<int>> opt(V + 1, vector<int>(P + 1, 0));

    for (int i = 1; i <= V; i++)
        dp[i][1] = w[1][i];

    for (int j = 2; j <= P; j++) {
        for (int i = j; i <= V; i++) {
            for (int k = j - 1; k <= i - 1; k++) {
                int cost = dp[k][j - 1] + w[k + 1][i];
                if (cost < dp[i][j]) {
                    dp[i][j] = cost;
                    opt[i][j] = k;
                }
            }
        }
    }

    printf("%d\n", dp[V][P]);

    // Reconstruct post office positions
    vector<int> postOffices;
    int curV = V, curP = P;
    while (curP > 1) {
        int k = opt[curV][curP];
        int med = (k + 1 + curV) / 2;
        postOffices.push_back(x[med]);
        curV = k;
        curP--;
    }
    int med = (1 + curV) / 2;
    postOffices.push_back(x[med]);

    reverse(postOffices.begin(), postOffices.end());
    for (int i = 0; i < (int)postOffices.size(); i++)
        printf("%d%c", postOffices[i], i + 1 < (int)postOffices.size() ? ' ' : '\n');

    return 0;
}

Complexity Analysis

• Time complexity: $O(V^2 \cdot P)$ for the DP, plus $O(V^2)$ for precomputing $w$. With $V, P \le 300$: at most $300^2 \times 300 = 27{,}000{,}000$ operations.

• Space complexity: $O(V^2 + V \cdot P)$.

Possible Optimization

The optimal split point $\mathrm{opt}[i][j]$ is non-decreasing in $i$ for fixed $j$ (the ``divide and conquer'' or ``Knuth'' optimization). This reduces the DP to $O(V \cdot P)$ amortized. However, $O(V^2 P)$ is sufficient for $V \le 300$.