论如何优雅的编出卡最坏复杂度的数据

kino酱在做BZOJ1007水平可见直线。众所周知这是一道单调栈维护凸壳经典题,但是kino却发明了一种妙妙的贪心法,而且没有被卡。

其操作流程是,我们首先找出斜率最小的一条直线,然后我们遍历整个数组,找出交点横坐标最小的直线。随之移动到该交点对应的另一条直线,重复这一过程。由于他的代码太长了,这里用伪代码描述吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Get-Next-Line(lastLine, thisLine) 
let line[] be the array of Lines
let Line.a to be the xielv and Line.b to be the jieju
let Point be a point
mina = minb = minx = INF
minindex = 0
for i = 0 to a.size
if used[i] or thisline.a = line[i].a then
continue
Point = inter(thisline, line[i])
if Point.x <= lastLine.x then
continue
if Point.x = minx and line[i].a > mina then
mina = line[i].a
minindex = i
if Point.x < minx then
minx = Point.x
minindex = i
used[minindex] = 1
return line[minindex]

具体实现见:https://yuyuko.cc/2018/02/26/%E9%A2%98%E8%A7%A3-bzoj10071007-HNOI2008-%E6%B0%B4%E5%B9%B3%E5%8F%AF%E8%A7%81%E7%9B%B4%E7%BA%BF/

在运行过程中,我们用该函数取出下一条直线,直到该直线斜率最大为止。取出的直线就是结果。对于该方法,最坏情况下时间复杂度显然是$O(n^2)$的。这是因为,如果每一条直线都作为凸壳的一个组分,那么这就意味着kino酱的算法必须全部扫描一遍。

但是下面这条结论可以被证明:kino贪心法在整数范围内,对$a, b \in Z$,如果有$a, b \leq |m|$,那么复杂度为$O(n \sqrt m)$。

今天,就让LR来给各位揭示玄妙速度背后的真相(gun)

对于直线$y_1 = k_1x + b_1$和$y_2 = k_2x + b_2$,其交点为$\dfrac{b_2 - b_1}{k_1 - k_2}$。

考虑到如果现在存在$y_3 = k_3x + b_3$,并且斜率递增,那么三条直线均作为凸壳一部分的充要条件应该是交点横坐标逐渐增加,也就是:

$\dfrac{b_2 - b_1}{k_1 - k_2} < \dfrac{b_3 - b_2}{k_2 - k_3}$

同样推广下去的话,我们得到的结论是$\dfrac{b_2 - b_1}{k_1 - k_2} < \dfrac{b_3 - b_2}{k_2 - k_3} <…<\dfrac{b_n - b_{n-1}}{k_{n-1} - k_n}$

不妨设$\dfrac{b_1 - b_2}{k_1 - k_2} = f_1$,那么应该有$f_1 > f_2 > … > f_n$恒成立。我们默认$k$具有单调性,那么$b$也一定是单调的。当$k$单调递增,$b$将单调递减。

乍看上去,只要满足这个比值逐渐增加即可,但是还是有些问题的,也就是:$k \in Z$

也就是说$k$的递增最小也是以$1$为单位的,那么为了保持$b$的递增性我们就必须满足$b$的增加幅度逐渐变大,在最小的情况下我们有$b_{i+1} - b_{i} = i$,这样的话$b_{i+1} = b_i + i$

然后我们转一发通项(似乎是用叠加法),可以得到$b_i = \dfrac{i^2 - i}{2} + b_1$,大功告成。当$b_1$取$-50w$的时候,我们发现$i$最大能取到1000左右,虽然kino酱自带不开O2的STL程度的常数但还是能过的。

可是如果我们再刺激一些呢?比如,把值域改成1亿!下面这个程序就是干这个事的,我们发现这样增加最多有20001条直线。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>

using namespace std;

set<pair<int, int> > s;

int main() {
freopen("line.in", "w", stdout);
srand(time(0));
int N = 20001;
int j = -100000000, k = 100000000;
int i;
cout<<N<<endl;
for(i = 0; i < 20001; ++i) {
//if(j + (i * i - i) / 2 + 1 > 100000000) break;
cout<<j + i<<" "<<k - (i * i - i) / 2 + 1<<endl;

}
cout<<i<<endl;
return 0;
}

然后kino酱就是我的辣! 然后kino酱的程序被卡了10s左右。

不过这种做法还是很妙的,对于随机数据和专门卡单调栈的数据表现会非常好,因为这类数据结果中往往只有很少的几个凸壳。关键的是没有人会卡23333333

论如何优雅的编出卡最坏复杂度的数据

https://lirewriter.cn/2018/02/26/论如何优雅的卡掉kino酱/

Author

LittleRewriter, Kriaeth

Posted on

2018-02-26

Updated on

2021-07-28

Licensed under

Comments