UOJ Logo WrongAnswer的博客

博客

APIO2013 TASKSAUTHOR 题解

2016-04-26 10:56:11 By WrongAnswer

题目描述

http://uoj.ac/problem/109

解法分析

要区分两个程序 $A$ 和 $B$,就要知道 $A$ 和 $B$ 各自的优缺点.

1. SSSP

FloydWarshall 的运行效率取决于点数 $V$,通过代码可以发现 $\mathrm{counter}=V^3$,与询问数 $Q$ 无关.

OptimizedBellmanFord 通过多轮松弛求出最短路,从代码中可以看出,每轮按照边在输入文件中的顺序松弛,当 $s$ 出发的最短路恰好沿着输入边的顺序时,一轮松弛就能求出最短路,但如果恰好逆着这个顺序,则要松弛 $V-1$ 次才能求出最短路.

ModifiedDijkstra 当边权均为正时就是复杂度有保证的 Dijkstra 算法,而当有负边权时类似贪心的 SPFA. 不难发现当从 $s$ 出发的最短路第一条边不是 $s$ 边权最小的出边时,可能有大量无用的松弛操作.

2. Mystery

Gamble 为题目设计所用,不考虑.

RecursiveBacktracking 为暴力迭代深搜求解图的色数的程序,复杂度指数级,随便的图就能使其 TLE,要使其不 TLE 就要构造答案接近于程序的枚举顺序的图.

详细题解

测试点1

问题为 SSSP,$A$ 为 ModifiedDijkstra,$B$ 为 FloydWarshall,$T=107$.

要使 FloydWarshall 程序 TLE,只需令 $\mathrm{counter}=V^3>10^6$,即 $V>100$. 由于输入文件不能包含超过 $107$ 个数,只要生成 $V=101$ 的空图(没有边)以及任意 $1$ 组询问即可.

测试点2

问题为 SSSP,$A$ 为 FloydWarshall,$B$ 为 OptimizedBellmanFord,$T=2222$.

显然 FloydWarshall 通过的条件是 $\mathrm{counter}=V^3\le 10^6$,即 $V\le 100$,因此可取 $V=100$. 因为输入一条边有 $2$ 个整数,所以图 $G$ 的边数应当在 $E=1100$ 左右. 在此基础上要使 OptimizedBellmanFord 程序 TLE,应使最短路逆着松弛顺序,这样 $\mathrm{counter}$ 约等于 $VEQ=1.1\times 10^6$.

最简单的方法就是构造从点 $99$ 到点 $0$ 最短路 $99,98,...,1,0$,为增加边数,每个点 $i$ 往前连 $11$ 条边 $(i,i-1),(i,i-2),...,(i,i-11)$,但只有 $(i,i-1)$ 出现在最短路上,这可通过控制边权得到(以下是伪代码):

for(int i=99;i>=0;i--){
    int n=(i>11?11:i);
    for(int j=1;j<=n;j++)link(i,i-j,j*j);
}

其中 link(i,j,w) 表示连边 $(i,j)$,权值为 $w$. $10$ 组询问均为 $s=99$,$t=0$ 即可.

测试点3

问题为 SSSP,$A$ 为 OptimizedBellmanFord,$B$ 为 FloydWarshall,$T=105$.

测试点3与测试点1类似,事实上,直接使用之前测试点1构造的图即可通过测试点3.

测试点4

问题为 SSSP,$A$ 为 FloydWarshall,$B$ 为 ModifiedDijkstra,$T=157$.

$T$ 很小意味着点数和边数都不能太大,也就是说要将 $B$ 的复杂度卡到指数级.

只有 $G$ 中有负边权,ModifiedDijkstra 才会出现 $s$ 的边权最小的出边不在最短路上的情况,这样才能使其做大量无用的松弛操作,如下图:

      -1   -2
    0 -> 1 -> 2
 -2 |         | -2
    v         v
    3 -> 4 -> 5
      -1   -1

起点 $s=0$,终点 $t=5$,则 ModifiedDijkstra 就会按照 $0,3,4,5$ 顺序加入优先队列松弛(此时 dist[5]=-4),接着队首为 $1$(dist[1]=-1),再按照 $1,2,5$ 顺序松弛(此时 dist[5]=-5).

如果有 $k$ 个这样的子图串联,那么可以得到 $2^k$ 条不同的路径,通过合理设置边权即可使所有的路径都走一遍. 为了减少边数,图按如下方式简化:

    -2      -2      -2      -2
 0 ----> 2 ----> 4 ----> 6 ----> 8
  \    -* \    -* \    -* \    -*
 -1\|  /|-1\|  /|-1\|  /|-1\|  /|
   -* /-9  -* /-5  -* /-3  -* /-2
     1       3       5       7

每个子图为 $(i,i+1)$,$(i,i+2)$,$(i+1,i+2)$三条边,边权指数级递减,就能保证每次更新 dist[t] 都会减少.

设有 $k$ 个这样的子图,则点数为 $2k+1$,边数为 $3k$,询问数 $Q=10$时,输入文件中数的个数为 $1+2k+1+2\cdot 3k+1+20=8k+22$,由 $8k+22\le 157$ 得 $k\le 16$,因此将 $16$ 个这样的子图串联即可(以下是伪代码):

for(int i=0,w=-32768;i<32;i+=2,w/=2){
    link(i,i+1,-1);
    link(i,i+2,-2);
    link(i+1,i+2,w-1);
}

$10$ 组询问均为 $s=0$,$t=32$ 即可.

测试点5

问题为 SSSP,$A$ 为 ModifiedDijkstra,$B$ 为 OptimizedBellmanFord,$T=1016$.

ModifiedDijkstra 对于大多数的图 $G$,运行效率都很高,所以关键在于使 OptimizedBellmanFord 程序 TLE。

当 $Q=10$ 时,设边数为 $E$,则输入数的个数为 $1+V+2E+1+20=V+2E+22$,而 OptimizedBellmanFord 的最坏情况下 $\mathrm{counter}=(V-1)E$,由基本不等式 $\frac{V-1+2E}{2}\ge\sqrt{2E(V-1)}$,因此在输入数的个数一定时,要使 $\mathrm{counter}$ 最大,则 $V-1=2E$. 然而这样边数不足点数,实际可达的点不足 $V$,无法令程序复杂度达到最坏情况.

因此可以令 $E=V-1$,并将所有点连成一个链. 注意题目要求 $V\le 300$,所以可以构造链 $299,298,297...,0$. 输入还没满,可以再加一些不在最短路上的边(伪代码如下):

for(int i=1;i<300;i++){
    link(i,i-1,1);
    if(i>=255)link(i,i-2,4);
}

$10$ 组询问均为 $s=299$,$t=0$ 即可.

测试点6

SSSP,$A$ 为 OptimizedBellmanFord,$B$ 为 ModifiedDijkstra,$T=143$.

测试点4构造的图可以使 $A$ 通过,唯一的问题在于输入数的个数超过了限制.

但经过测试可以发现,测试点4构造的图 ModifiedDijkstra 只处理 $6$ 组询问就会 TLE,所以将询问数减少为 $6$ 组即可通过该测试点.

测试点7

问题为 Mystery,$A$ 为 Gamble1,$B$ 为 RecursiveBacktracking,$T=3004$.

这是一个送分点,任意生成一个 $V=71$,$E=1501$ 的稠密图基本上就能令 $B$ 程序 TLE.

测试点8

问题为 Mystery,$A$ 为 RecursiveBacktracking,$B$ 为 Gamble2,$T=3004$.

首先明确数据范围,只能是 $V=71$,$E=1501$,这样输入文件恰好包含 $3004$ 个数.

要让迭代深搜通过,不难想到要使答案 $X$ 尽可能小,也就是 $X=2$,然而这样的图无法构出,这是因为,设编号为 $0$ 和 $1$ 的点数分别为 $n_1$ 和 $n_2$ 个,则边数 $E\le n_1n_2$,由基本不等式 $E\le n_1n_2\le (\frac{n_1+n_2}{2})^2=(\frac{71}{2})^2<1501$.

(感谢r_64提醒,上面的说法是错的……以下是本人的逗比做法)

所以我们考虑构造一个 $X=3$ 的图.

为了让 $A$ 通过,第一步 $A$ 在尝试 $X=2$ 时需要较快地退出,我们可以构造一个编号较小的三元环 $0,1,2$,即连边 $(0,1)(1,2)(2,0)$.

接着尝试 $X=3$,我们把编号在 $[3,70]$ 之间的点分为 $3$ 组,所有的边 $(i,j)$ 满足 $i$ 和 $j$ 不在同一组,第一步程序确定 $0,1,2$ 的编号分别为 $0,1,2$ 后,程序将会先将第一组的点标号为 $0$,再将第二组的点标号为 $1$,最后将第三组的点标号为 $2$. 这样就不会回溯了(伪代码如下):

link(0,1);
link(1,2);
link(2,0);
int m=1498;
for(int i=3;i<25&&m;i++){
    for(int j=26;j<50&&m;j++){
        for(int k=51;k<71&&m;k++){
            link(i,j);m--;
            if(m)link(j,k),m--;
            if(m)link(i,k),m--;
        }
    }
}

其中 link(i,j) 为连边 $(i,j)$.

UPDATE:Mystery 问题与 SSSP 的输入方式不同,输入规模只和 $E$ 有关,和 $V$ 无关,所以令 $V=78$ 就能构造二分图(即 $X=2$ 的图)了(伪代码如下):

int m=1501;
for(int i=0;i<39&&m;i++){
    for(int j=39;j<78&&m;j++){
        link(i,j);m--;
    }
}

总结

本题的 $8$ 个测试点构造的程序都很短,难点在于构造不容易想到. 构造的关键在于发现不同算法的优劣之处,这样就能针对算法在某些特殊情况下的缺陷生成特定的数据使程序 TLE.

评论

r_64
测试点8可以$V=100,E=1501$啊,轻松二分图 可以打广告吗?http://r64.is-programmer.com/posts/190243.html
fhxb520630
自己搞半天写完了看到有这么个东西orz

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。