P10336 [UESTCPC 2024] 2-Clustering Algorithm

Alice and Bob are two creatures in a $k$-dimensional space. In the space they live in, there are $2n$ feature points. The coordinates of the $i$-th feature point are $(x_{i,1}, x_{i,2}, \ldots, x_{i,k})$. In this space, the distance between two points is defined as the Manhattan distance between them (that is, the distance between point $i$ and point $j$ is $\text{dist}_{i,j}=\sum_{p=1}^{k}|x_{i,p}-x_{j,p}|$). Alice and Bob need to collect these feature points. They take turns choosing one point from these $2n$ points, and a point that has already been chosen cannot be chosen again. Alice moves first. Alice puts the points she chooses into set $S_1$, and Bob puts the points he chooses into set $S_2$. Define the value of a set $\text{val}(S)$ as the sum of distances between every pair of points in it. Alice wants to maximize $\text{val}(S_1)-\text{val}(S_2)$, while Bob wants to minimize $\text{val}(S_1)-\text{val}(S_2)$. If both Alice and Bob use optimal strategies, find the final value of $\text{val}(S_1)-\text{val}(S_2)$.

The first line contains two integers $n,k$ $(1\leq n,k\leq 10^5, n\times k\leq 10^5)$, representing half the number of feature points and the number of dimensions in the space. The next $2n$ lines each contain $k$ integers $x_{i,1}, x_{i,2}, \ldots, x_{i,k}$ $(-10^8\leq x_{i,j}\leq 10^8)$, representing the coordinates of the $i$-th feature point.

Output one integer, representing the value of $\text{val}(S_1)-\text{val}(S_2)$ when both Alice and Bob use optimal strategies. “The sum of distances between every pair of points” counts each unordered pair only once.

Translated by ChatGPT 5