疯狂提交找错法

October 10, 2007 – 10:24 pm

做 ACM 的那些人应该也都知道传说中的“疯狂提交找错法”吧。就是如果你题目没有过的话,提交的罚时是不会在最后的分数里面扣掉的。当然是希望在尽量少的次数内过掉,但是情急之下,疯狂提交也是一个办法,不管怎么算它都是有好处的:

  • 如果最后题目 AC (Accept) 了,虽然罚时会让排名下降,但是不管罚时多少,多做出一道题的总比少做出一道题目的排名要靠前。
  • 如果题目没有 AC ,也并没有什么损失。

但是疯狂提交也必须要能“找错”,否则就没有什么意义了。今天我也非常疯狂地爽了一把,并且最后成功找到问题,把题目 AC 了。

其实我平时并不做 ACM ,因为我对存算法不太在行,而且我也特别讨厌 ACM 这种纯黑箱的形式,只告诉你正确或者错误,而得不到一点调试信息。但是仔细想想其实现实世界很多地方是这样的,比如许多商业软件,没有提供源代码,出错以后你也只能是茫然,再比如自己发布软件的时候,甚至连“对”或者“错”这样的单纯的结果都没有,你只能尽可能地去遇见和避免各种 Bug 和错误。所以其实做 ACM 的题目应当还是一个相当不错的锻炼吧。

但是数值分析这门课的几个作业是 ACM 形式的判题系统,所以还得去做。这次的题目并不难,就是代数方程求根,算法也在书上都讲过了。然而做出来的程序无论如何都是 Wrong Answer 。这四五天的空余时间几乎都在做这个题目,唉,做得郁闷到极点,怎么就能不对呢?我尝试了各种各样的方法,牛顿法、改进的牛顿法、二分法、Steffensen 方法,还把它们结合起来,修改各种优化参数……总之就是过不了。

最后我静下来仔细想了一下,如果测试数据里面的数据非常大的话,用 double 进行计算必定会溢出,那样肯定算不出结果来,但是我看到题目的状态显示有人确实通过了,所以测试数据应该不会特别大。不过令我郁闷的是我在使用二分法的时候竟然 TLE (Time Limit Exceeded) 了,那除非是一个很大的区间啊!

最后我决定用疯狂提交找错法了。我要探测测试数据!但是 OJ (Online Judger) 给出的结果种类非常少,包括 WA (Wrong Answer) 、TLE 和 Runtime Error SIGSEGV 等,根本不能从中得出测试数据,然而我们可以对测试数据(包括整个运行环境中的任何状态)进行一个 bool 测试并得到结果:结果就由 WA 和 SIGSEGV 两种状态来区分。于是我写了一个 helper 函数:

void fire_seg_fault()
{
	int *ip = 0;
	*ip = 0;
}

原理很简单,就是要产生一个运行时错误, abort 函数不允许调用,除以零似乎也被忽略掉了,不过对 NULL 指针解引用是绝对会造成运行时错误的。然后在代码里面就可以对测试数据进行探测了,比如:

if (n > 1000)
  fire_seg_fault();

提交,然后根据结果是 WA (或者 TLE) 还是 SIGSEGV 来判断 n 的范围。然后逐次缩小范围,对于整数来说总是可以在比较可观的次数之内得到一个准确的值。对于浮点数来说,其实计算机里面的浮点数也不会是无限位的,所以从理论上来说也可以通过逐步缩小范围得到“精确”的值(也就是它给定的值)。

经过我疯狂探测,得出了测试数据的规模:

  • 一共有 14 组测试数据。
  • 有 a > b 的情况。(真过分,ACM 就经常有这种情况啊,说“a and b are the two end-points of the given interval”,故意不说 a 比 b 小,然后又在示例测试中把所有的例子都写成 a 比 b 小,让你产生错觉,却又在测试数据里面来个 a 比 b 大,如果不小心误以为 a 一定比 b 小的就要郁闷了)
  • a 的取值范围为 -100 到 1 。
  • b 的取值范围为 -0.5? 到 3 。
  • eps 如题目中描述的一样,一直都是 0.00005 。

出乎我的意料竟然测试数据的规模这么小的。可是竟然在二分法的时候会 TLE ,这就让我不解了。接着我继续用探针探测出 TLE 出在第三组测试数据上。第三组数据 n 是 5 ,并不大,所以我决定把第三组的参数全部探测出来,当然并不是特别轻松的活,我都想用脚本来写个“探测机”了。不过总算数据并不变态,最后还是被我探测出来了:

a == -4
b == 2
n == 5
c[5] == 1
c[4] == 4.6
c[3] == -1.94
c[2] == 0.296
c[1] == -0.0199
c[0] == 0.0005

这下为什么会 TLE 就明了了,画出函数图形如下所示:
graph.png
我在判断结束条件的时候用了如下语句:

if (fp == 0 || (GOOD_ENOUGH(b-a, eps) && GOOD_ENOUGH(fp, eps)))

其中 GOOD_ENOUGH 是一个用于判断绝对值的宏。总之就是函数值 fp 在给定的区间 (-4,2) 里面的函数值永远都达不到给定的精度 (eps) ,所以就在那里死循环了。去掉那个判断得出的结果会飞掉,因为我在这里犯了一个很严重的错误:左右两边函数值的符号是一样的,不能用二分法。

但是我是在牛顿法失败的情况下才会去用二分法。牛顿法为什么会失败呢?实际上,在给定的区间之内根本没有实根,只有 4 个虚根,唯一的实根是 -5 左右的那个,但是那个是在区间之外的,可是几乎所有的收敛序列都直接收敛到那里去了,但是是在给定的区间之外的,无疑要被丢弃。

可是这样的话题目不是有问题吗?题目中说过:

It is guaranteed that a unique real number r exists in the given interval such that p(r) = 0.

在给定的区间之内明明没有根嘛,不过单从图形上来看的话,还是很接近零的。最后我将牛顿法的初始值选取密度加大了,总算得到一个看上去像样点的解,算出来的函数值是 0.0045 ,唉,这和零相比应该还有很大的差距吧,可是我把程序提交上去之后竟然 AC 了!不过让我觉得好像是有些碰运气的感觉啊。

不过毕竟是郁闷了几天的题目了,总算是通过了。发现自己在做这样的题目的时候经常都是考虑得太过复杂了。但是如果数学功底再扎实一些,从理论上来仔细分析一下的话,也许不会出现这种类似于“侥幸”通过的尴尬情况了吧。 :)

  1. 9 Responses to “疯狂提交找错法”

  2. 那个函数图你用什么画出来的?

    By ln on Oct 11, 2007

  3. To ln:
    那个图形是用 Mathematica 画的。 :P

    By pluskid on Oct 11, 2007

  4. 在做NA的题目吧。。。
    那题cyjj信誓旦旦的说用二分过不了,但我就是过了,哈哈

    By zhouyuan on Oct 14, 2007

  5. to zhouyuan:
    cyjj 应该是说的书上的那种平凡二分法吧,肯定是你有修改过的或者人品爆发,要不然肯定过不了啊。

    By pluskid on Oct 14, 2007

  6. 就是针对性的加点trick嘛

    By zhouyuan on Oct 15, 2007

  7. 恩,算法也都是人想出来的而已,多交流一下真的发现每个人都有自己独特的想法!

    By pluskid on Oct 15, 2007

  8. cyjj 改测试数据了,这学期上NA,这道题一直AC不掉,现在也没有。快期末了,悲剧。
    问作者是怎么试出具体的值来的,有什么妙法吗?

    By Wei CHEN on Jun 7, 2009

  9. 咦?我不是在这里就写了我猜出测试数据的办法?

    By pluskid on Jun 7, 2009

  10. 关于这个例子
    a == -4
    b == 2
    n == 5
    c[5] == 1
    c[4] == 4.6
    c[3] == -1.94
    c[2] == 0.296
    c[1] == -0.0199
    c[0] == 0.0005
    这个方程在x=0.1的时候是有二重根的啊

    By Siyi Li on Sep 26, 2012

Post a Comment