Google Code Jam 2011 (Qualification)

书接上篇

1. [84%/98%] Bob Trust: 两个机器人并行依次按钮

由于要依次按钮,所以并行能节省的时间,只有另外一个机器人移动的时间,而它按钮的那一秒钟是不能节省的。

2. [87%/82%] Magicka:依次合并或者清除元素

由于即使是大数据集,合并列表和冲突列表个数也不过36和28,所以最好直接把这两个列表反向来进行匹配,而不是在后面的匹配测试中去正反测试两遍。
另外注意先合并,后判冲突。

3. [90%/85%] Candy Splitting:加法改异或

按题目叙述,不难发现Patrick的错误加法真值表与异或XOR运算相同。由于没有进位,可以单独看每个二进制位。
如果某一个二进制位上,1的个数为奇数,则无论如何划分,都不可能使得最后异或结果相等。
如果1的个数为偶数,则可以任意划分,但需要保证可怜的Patrick至少分到一个糖果。
所以排序后取最小的数给Patrick,其他的全部留给Sean。

4. [58%/97%] GoroSort:概率排序

首先注意,下面这个Smallest的条件很容易被忽略掉:
The second line of each test case will contain a permutation of the N smallest positive integers.

然后由于每个数都已经知道最后需要所在的位置,所以排除掉已经在目标位置的情况,其他的每hit一次,有1/2的机会回到正常的位置,再加上,占据现有位置的那个数,以后会有1/2的机会回到它自己的位置,所以只需要每个不在目标位置的数上累计加一就能得出结果。

这题最挨打的,就是那个%.6lf。 我是用整数表示,然后后面加6个0。这个实在太误导了,让人以为会计算很复杂的概率。

PS 最后,这次的GCJ Command Line Tool还蛮好用的,呵呵~

GCJ 2011 Qualification Round Solution Download

Google Code Jam 2009 (Qualification)

书接上篇

1. [84%/84%] Alien Language:给定pattern,求辞典中满足pattern的词的个数。

这道题,题目吓一跳,以为是和practise一样的,结果是另外一道。

内容再次吓一跳,perl代码简单到爆。直接把'(‘、’)’换成'[‘、’]’,当作字符类编译成正则,然后挨个匹配计数就行了。

2. [88%/86%] Watersheds:给定地图和高度,求有几个水凼凼。

这道题遍历每个cell,判断水流,由链表确定等价类,最后从小到大标号既可。

3. [88%/56%] Welcome to Code Jam:给定目标,求子串。

这道题一看,大量操作单个字符,选c会比perl有优势,所以用c。

简单的动态规划即可,有大量重复子问题。当前text中包含target的数量,等于当前text中,所有的target[0]其后的子串,所包含的target[1~end]的数量之和。

由于结果只需要4位,所以用int表示结果已经足够,计数的时候,超过9999,则减去10000。

可惜这道题的大数据集,我还是超时了,因为小数据集我time了一下,只用了0.001s,所以偷懒了一下,没有加缓存,准备直接用机器硬抗大数据集,等了近5分钟,居然还没算出结果,这时再更改程序加缓存、编译、上传就来不及了。

加入4行代码的缓存之后,大数据集time结果如下:

real    0m0.031s
user   0m0.028s
sys    0m0.000s

不到0.1s,很难想像加入缓存会有如此大的区别,真是遇鬼了。

GCJ 2009 Qualification Solution Download

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