[CF 329E]Evil题解翻译

题解翻译

这道题的解法实际上非常简单:http://codeforces.com/contest/329/submission/4122927

这道题要求我们证明一大堆东西(下面的证明超过80行)。

假设n>=4.显然n<4的情况是平凡的。

首先,我们假设没有两个点的坐标相同。为了得到这一点,我们可以微小地抖动每个点,这不会改变答案。

关键在于:A)“曼哈顿距离”,B)回路的起点和终点是同一点。假设我们已知一个回路。回路的总长是|X2-X1|+|Y2-Y1|+|X3-Y2|+|Y3-Y2|…

为方便起见,让我们把X和Y坐标分开考虑。注意到每个点将在答案中出现两次,例如X2在|X2-X1|中和|X3-X2|中都出现了。曼哈顿距离意味着坐标值(例如X2)将会乘以+1或者-1,这取决于绝对值符号中另一个坐标和它的大小关系。此外,乘以+1的坐标值的数量必须等于乘以-1的坐标值的数量(因为在每个绝对值符号中,一个值乘以+1而另一个乘以-1)。这直接暗示了回路总长的上界。

如果我们列出所有点的X坐标,每个出现两次,然后将它们排序,那么如果我们将后一半乘以+1,前一半乘以-1,最后将它们加起来,就会得到最大值。注意到所有这些推导同样适用于Y坐标,而且将X和Y坐标的最大值加起来,我们就得到了回路总长度的上界。

如果能找到一条长度等于该上界的路径,我们的工作就结束了。在某些情况下,这是可能的。让我们解决它!

首先,如果我们得到了上述列表中X和Y坐标的中位数,我们就可以像下图一样分割整个平面:

A| B
|
---------
|
C| D

直线代表了X和Y坐标的中位数。

每条中位数直线上都有至多一个点(想想我们关于X和Y坐标均不相同的假设)。

让我们将A、B、C、C称作“区域”。下面,我们将把“区域A”简单地称作“A”(同样对B、C、D)。(译者注:区域不包含中位数直线,类似于笛卡尔坐标中的‘象限’)

为了得到上述值,到达B中的某一点后我们必须前往C中的某一点。同理:B->C,C->B,A->D,D->A。这里,点的配对是显然的,A和D配对,同样B和C配对。

首先,如果A+D为空或B+C为空,我们就一定能得到上述上界。我们可以简单地交替选择剩下两个配对区域中的点。因此我们假设A+D非空,B+C也非空。

首先,我们讨论B和C之间的关系(A和D同样符合这一关系)。(译者注:原文为‘A和B’,疑为作者笔误)

定理1:

|B-C|<=1.

证明:

首先,如果两条中位直线上都没有任何点,或者正中心处有一个点:

中位置线将区域分成两部分,两部分中点数相同,因此有:

a) A+B = C+D

b) A+C = B+D

a代入b:

(C+D-B)+C = B+D

2C=2B

B=C

结论成立。

接下来,假设中位直线上共有两个点,每条直线上一个:

让我们假设一个在中心点的上边,一个在中心点右边。其余情况均类似。

a) (A+B+1) = (C+D)

b) (A+C) = (B+D+1)

a代入b:

(C+D-B-1+C) = (B+D+1)

2C=2B+2

C=B+1

同理,也能推出A=D。

对其余三种情况进行类似推理得:

C=B且A=D+1

C=B-1且A=D

C=B且A=D-1

结论成立。

注意,点数较多的那个区域不和任何中位数点相邻(相邻指中位数点位于该区域的边界上)。

在上述论证中,我们得到上界(也就是,将X和Y坐标分别排序,并将前一半乘以-1,后一半乘以+1),并试图找出一个尽可能和上界接近的解。

接下来将是其他的分析。

定理2:

如果中位数直线上有两个点(每条直线上各有一个),那么上界可以达到。

证明:

我们将用“一对区域”称呼A和D,或者B和C。根据定理1证明的第二部分,将有一对区域包含不同数量的点。让我们取这一对,然后从二者中点数较多的那个区域开始。我们不断地在这两个区域中交替行走,直到在起始区域结束。然后,我们只需要前往任意一个中位数点。从那里,我们再前往另外一对区域中最远的那个。然后再在这两个区域内交替行走,最后去往另一个中位数点,然后回到最初的起点。容易看出,这将是最优的,而且能达到上界。

现在,我们来看中位数直线上没有任何点的情况。首先,这意味着点的数量是偶数。然后,这意味着我们的上界,即将X和Y列出并排序后分别乘以-1 -1 -1 … -1 1 … 1 1 1,是无法达到的(因为这意味着我们必须不断地在一对区域中交替行走,然而我们并无法在两对区域之间切换)。因此,我们必须修改至少一个系数。可能的最优方案由交换最中间的两个值得到,即:-1 -1 -1 … -1 -1 1 -1 1 1 … 1 1 1 .这就足够了。为什么?总点数是偶数,故现在有两个点被修改了。而且,此外,这两个点是距离中位数直线最近的(我们假设这些坐标是X坐标,即它们距离竖直的中位数直线最近),并且位于两个不同的区域。那么,我们将如下处理。首先从这两个点之一开始。在它所在的一对区域中交替行走,在另一边终止。如果另外一个点在这个区域,我们就前往该点,从而在那里结束,而且在此情况下,我们可以前往另外一对区域中的一个点,保持符合上述X坐标的系数列表(因为该点离中位数直线最近)。否则,该点将在另外一对区域中,我们只需要前往该点,然后显然我们仍然能符合X坐标的系数序列。在这一对区域中交替行走直到最后,回到起始点。可以看出,所有这些都符合上述的系数列。

这是最优的,因为若上界无法达到,这是第二大的上界。

现在,如果在两条中位数直线上共有一个点(即在正中心,也就是两直线的焦点),那么上界无法达到。可以发现,要想达到上界,我们必须从某区域内的一个点走向这一对区域中的另一个区域,或者去正中心的点。然而,由于两对区域都非空,我们就需要至少两次在它们之间切换。由于只有一个中心点,这是不可能的。

注意到这种情况意味着总的点数为奇数。因此,我们不能简单地交换最中间的两个点,因为最中间只有一个点。那么我们只能这样做:

-1 -1 … -1 -1 1 1 -1 1 … 1 1

或者

-1 -1 … -1 1 -1 -1 1 1 … 1 1

这就是说,交换中间点和相邻的一个点。按照和上面相同的推导,我们可以符合这个X坐标的系数列。

为了得到O(N)的期望复杂度,记住我们需要的操作只有:把元素分进区域,找出中位数。这二者都能在O(N)时间内完成(期望复杂度是因为虽然有一个最坏情况O(N)的选择算法,但它非常不优美)。

发表评论

电子邮件地址不会被公开。 必填项已用*标注