Google Code Jam 2009 (Practise)

去年做了做Google Code Jam的入围题,挺好玩的。今年早早的就收到了邮件,并且还附上了四道练习题。

1. [74%/80%] Alien Number:给定源语言以及目标语言,要求翻译一个数字。

这题按最自然的思路就行了。为方便起见,把源数字先转换成十进制,然后再用和十进制转二进制相同的辗转相除法,求得目标数字的表示。

2. [80%/84%] Always Turn Left:给定总是左转的规则及实际路线,要求实际的迷宫。

如果你身陷迷宫,“总是左转”的规则,或者说“手不离墙,摸着墙走”的规则,兴许能救你一命。

其实,这道题中,我们能得到的所有讯息,都在来回走的路径里面。所以只要跟着路径实际来回走一遍,并沿路,总结迷宫信息,最后得到的便是整个迷宫。

对于左右转及方向的表示,一堆if-else,时空都坏;归纳到一个表里面查表,空间效率也不高;其实就四个方向,如果NESW分别表示为0123的话,简单的加减取模,就能实现左右转了。至于walk through的坐标处理,选择一个简单的闭包最为理想。

另外,在处理路径的时候,维护一个x、y坐标的最大、最小值,以便于最后输出迷宫。

在输出迷宫的时候,不用先存储那张转换表,而直接把YES当成1,NO当成0,作为4位的二进制数,再表示为16进制,刚好就是那张表。

==== 从题目前括号里表示的人们的成功率上来看,前两题比较简单,后两题比较困难 ====

3. [68%/49%] Egg Drop:给定某个可解扔蛋问题的三个参量,在保持可解的情况下,求每个参量的极大值或极小值

这道题有很自然的思路,那便是Fmax的递推式:

设想现在在第 i 层扔蛋,那么第 i 层扔了,就能确定状态,因此本身算一层 ( 1 );
如果蛋没碎,往上验,最多还能验F( D – 1, B )层[ 因为第 i 层扔了一次,D减1;蛋没碎,B不变 ];
如果蛋碎了,往下验,最多还能验F( D – 1, B – 1 )层[ 因为第 i 层扔了一次,D减1;蛋碎了,B也减1 ]。

由于每次验证,蛋只能处于碎或不碎状态中的一种,所以二者并不互相影响。故:

F(D, B) = 1 + F( D – 1, B ) + F( D – 1, B – 1 )

接下来如何计算这个递推式,是个问题。如果这个问题解决了,那么要找到最小的D和B,直接查表既可。

容易看出,递推式中有大量重复的子问题,动态规划应该效果不错。不过,我们还是先来看看数据膨胀速度如何:

[B]
1 3 7 15
1 3 7 14
1 3 6 10
1 2 3 4   [D]

左上部分不用计算,就是对角线上的数字,因为能打碎的数量,如果超过总的实验次数,多出来的这部分就没意义了。故:

F( D, B ) = F( D, D ) if( B > D )

直接观察对角线上的数字,容易看出,对角线上的数字为 2^D – 1。

即使没有看出来,也可以推出来。只用由F(D, B)的递推式和上面B>D的性质,得出递推式 A(n)=2A(n-1)+1,并求解既可。

由此可见,这张表的数字膨胀速度相当快(2^n)。因此,我们得充分利用一个很不起眼的条件,那便是F有2^32的大小限制。

B再大,在应用上面B>D的性质后,也不会超过32。整张表的纵向高度就限制得很小了。

但整张表的横向高度依然可以很大,比如F( 2000000000, 1 ),这种情况即使动态规划会很吃苦头。

观察每一列,都是从 D ~ (2 ^ D – 1),之间的每个数的差值,刚好是杨辉三角。

1—————–0
1          1————-1
1          2       1———–2
1        3         3        1——-3
1        4         6        4        1—-4
0Cr4 1Cr4 2Cr4 3Cr4 4Cr4

15 – 1 = 14
14 – 4 = 10
10 – 6 = 4

所以,从D开始往上累加各个组合数,既可得出某一位的值。而这个累加过程,一旦大于2 ^ 32便可退出。

算出了Fmax,Bmin可以直接挨个找,因为表的纵向高度有限。而Dmin,则需要一个简单的折半查找,以应对F( 2000000000, 1 )类似的情况。

4. [64%/31%] Shopping Plan:给定商店、油费和要买的东西,求最低花费

31%的大数据集通过率,可见这道题的时间或者空间复杂度比较高。

这道题乍看之下,容易让人想起Dijkstra算法[王选貌似还谈论过Dijkstra这个人]。但我很难想到简单的一个数,来指征当前选择的优劣。因为要考虑的因素,实在很多,离家的远近、当前购买物的价格、路径、还有买了是否需要立刻回家等等。

另外,最优子结构的寻找,也颇为困难。因为容易理解,买abcd的最佳路径不一定包括买abc的最优路径。

在这种情况下,我们不得不增强条件。我们以a. 从某个商店出发,b. 买完某些商品,c. 并且当前是否需要回家为基准计算最小值。

这里面依然可以看出,有大量的重复子问题,可以动态规划。

我们遍历当前商店里能买到的并且当前需要购买的商品,买之,然后再遍历所有商店作为下一个商店,并且考虑当前买的商品是否需要立刻放回家。如果已经买完了,则立刻回家。

这里有一个想法很诱惑,那便是走过的商店便不需要再走。因为非perishable的商品始终能顺带带走,perishable的商品始终要立刻回家,也不需要第二次光顾来买。所以,如果以空间换时间,在过程中排除掉某些商店,效果应该不错。但再仔细想想就会发现,这里的空间开销很大,即使用bit set,也需要2 ^50。而所换来的时间并不多,因为我们依然得处理这个比特集。

这样实现的一个perl脚本的性能如下:

[小数据集 100 cases] – 工作很好

real  0m0.297s
user 0m0.260s
sys  0m0.040s

[大数据集 20 cases] – 严重超时

real   35m4.110s
user  34m20.661s
sys    0m42.387s

0.297s已经是对perl脚本做性能调校之后的结果,所以不更改算法或者更改编程语言,很难有所提高了。这里我选择了后面一种方式,用纯C实现了一个相同的算法:

由于perl处理文本始终还是方便很多,所以先用preprocess.pl脚本把input文本解析为利于C解析的格式。[这里是每行一个数字,并处理掉商品名称]

然后用纯C的程序读入处理后的文本,并输出,[ $gcc –O3 run.c –lm ]下面是一些性能数据:

[小数据集 100 cases]

real    0m0.223s
user   0m0.220s
sys    0m0.004s

完全没有缓存的版本,已然比perl的要好,接下来为算路费的函数添加缓存:

real    0m0.128s
user   0m0.124s
sys    0m0.004s

再为递归函数添加缓存:

real    0m0.004s
user   0m0.004s
sys    0m0.000s

这里就已经相当理想了,可以预见大数据集性能也不会差。

[大数据集 20 cases]

real    0m16.551s
user   0m16.501s
sys    0m0.048s

16s,算是很完美的性能了。同样的算法,动态脚本和纯C还是没法比啊,呵呵。即使在极限情况,50个商店,15个待购商品的case,也能在0m12.260s内解决。

GCJ 2009 Practise Solution Download

《Google Code Jam 2009 (Practise)》有6个想法

  1. F(D, B) = 1 + F( D – 1, B ) + F( D – 1, B – 1 )
    这个递推式怎么来的。。还是没懂

  2. 请教一下最后一个题目:设想共有两个商店 A,B;两个物品 m,n,都 non-perishable 。每个商店都有所有两件物品,但A中买m超级划算,买n超级贵;同时B中买n超级划算,n超级贵;并且A,B两商店距离很近,几乎可以忽略。所以可以想见最优解是A店买m,再B店买n,回家。但博主的算法似乎得不出这种结果?
    因为我们到一家店总是“遍历当前商店里能买到的并且当前需要购买的商品”

发表回复

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据