Stargazer' blog

对于 $m$ 个点集 $s_1=\{x_{1,1},x_{1,2},…\},s2=\{ x_{2,1}…,\}….,s_m$ 总共 $n$ 个点 $x_1,x_2,…,x_n$（排序后)

定义 $f_i(x)=\sum_{j}|x_{i,j}-x|$ ，选择 $k$ 个位置 $p_1,p_2…,p_k$，最小化$g(p_1,p_2,p_3…p_k)=\sum_{i=1}^m \min(f_i(p_1),f_i(p_2)…,f_i(p_k))$

定义 $M_i=Median(s_i)$

定义 $w(i,j)=\sum_{p,M_p\in[x_i,x_j]} \min(f_p(x_i),f_p(x_j))$

首先一些结论：

1、所有的 $ p_i$ 一定是某个存在的 $x_j$，不可能是一个不在点集内的坐标

故可以设选择的是 $x_{p_1},x_{p_2},…,x_{p_k}$ 这些位置

2、

1、Prove w(i,j) is monge：

设 $F_{l,r}(a,b)=\sum_{p,M_p\in[l,r]}\min(f_p(a),f_p(b))，那么w(i,j)=F_{x_i,x_j}(x_i,x_j)$

设 $a\le b\le c\le d$

需要证明 $w(a,c)+w(b,d)\le w(b,c)+w(a,d)$

我们之前论文里有$g$ 是 monge 的 即 $g(a,c)+g(b,d)\le g(a,d)+g(b,c)$

即 $F_{0,a}(a,c)+F_{a,c}(a,c)+F_{c,\infty}(a,c)+F_{0,b}(b,d)+F_{b,d}(b,d)+F_{d,\infty}(b,d)\le F_{0,a}(a,d)+F_{a,d}(a,d)+F_{d,\infty}(a,d)+F_{0,b}(b,c)+F_{b,c}(b,c)+F_{c,\infty}(b,c)$

由于 $F_{0,a}(a,c)=F_{0,a}(a,d),F_{c,\infty}(a,c)=F_{c,\infty}(b,c),F_{0,b}(b,d)=F_{0,b}(b,c),F_{d,\infty}(b,d)=F_{d,\infty}(a,d)$

即有 $F_{a,c}(a,c)+F_{b,d}(b,d)\le F_{a,d}(a,d)+F_{b,c}(b,c)$，故 $F$ 是 monge的，所以 $w$ 是monge的

2、上面的问题可以转化为 “Minimum-Weight k-Link Path “

求在类似如下的一个带边权的有向图dag中，从1走到n，经过k条边的最小权值和。

首先在原来的问题中添加两个新的集合 $\{-\infty\},\{\infty\}$，这时候这两个点一定排序后是 $x_1$ 和 $x_n$

显然所有最优方案立马一定不会选择 $x_1,x_n$

将选择一种 $p_1,…,p_k$ 的方案视作 $(x_1,p_1)(p_1,p_2),…,(p_{k-1},p_k),(p_k,x_n)$，权值就是 $w(1,p_1)+w(p_1,p_2)+…+w(p_{k},n)$，可以把 $w(i,j)$ 看做从i到j的边权，要求最小化，所以原问题可以规约到”Minimum-Weight k-Link Path ‘’。

根据

Aggarwal, Alok, Baruch Schieber, and Takashi Tokuyama. “Finding a minimum weight K-link path in graphs with Monge property and applications.” Proceedings of the ninth annual symposium on Computational geometry . 1993.

文章中的内容，首先我们的边权 $w$ 是monge的，对于一个a concave Monge DAG，可以在 $O(n\sqrt{klogn}+nlogn)$ 的时间复杂度求解 Minimum-Weight k-Link Path。

问题是我们的算法不能直接快速求解单个 $w(l,r)$，只能对于一个 $w$ 矩阵在 $T(n)=O(nlogn+mlogmlogn)$ 的复杂度求解矩阵最小值。(如果忽略后面的 $m$,那么就是 $T(n)=O(nlogn)$​)；或者在一个矩阵里以 $O(nlogn)$ 的复杂度遍历一段连续路径。

所以要回到该论文的步骤里，看有什么影响。

论文中做法是将 $n$ 的数组分块为 $n/l$ 个大小为 $l$​ 的块分别算

有四个步骤：

step1：需要对于 $n/l$ 个块调用 $logl$ 次大小为 $O(n)$ 的矩阵求解最小值，所以复杂度从 $O(\frac{n^2}{l}\log l)$ 变为 $O(\frac{n^2}{l}\log n\log l)$

step2: 不影响

step3：需要对于所有块进行一个大小为 $l*l$ 的矩阵进行求解，而这个step里的相乘之后的矩阵仍然具有monge性质，复杂度从 $O(kl)$ 变为 $O(kl\log n)$

step4: 利用多线程优化，我们可以把对于h的二分优化为常数时间，现在问题就是不知道 $\tau$ ，所以只需要通过参数化搜索就可以在 $O(kl+\frac{n^2}{l}\log n\log l)$（？)

step4这里需要用到一个 $O(nlogn)$​ 的1D决策单调性动态规划，求解有最少和最多链路数（links）的最小权重路径

但无论如何，总复杂度为 $O(kl\log n+n^2l\log l \log n)$

当 $l=\min\{n\sqrt {\log n/k},n\}$ 时

最优复杂度为 $O(n\sqrt{k\log n}\log n+n\log^2n)$

（当然这里是忽略了前面的 mlogm那一项复杂度)

感觉上其实也只是平淡的爱情故事，或者说剧本，里面甚至还有些我能感受到的瑕疵。

但还是触动了我的心里，也许这就是真挚的情感吧，无论如何，人都是期望着，追寻着幸福前行。

我也期望有着如故事中一般的邂逅，以前总能告诉自己，以后还有时间，总有一天能够触及到这样的幸福。

即使我也知道，现实并不能随人心意，渐渐地，有时候也期望自己至少能够像这些作者一样创作出能够触动人心的作品，如果能把这作为向前的动力就好了

大概是终于结束了。

漫长的竞赛生涯。

题目链接

题目链接

感觉好像有点菜的流脓了，绷。