Sunday, May 9, 2010

Google code jam: Qualification Round

又到了一年一度的code jam,过去从来没有参加过,因为从来不认为我天资聪颖到可以玩code jam。但是万事总有一个开头,今年我就参加了。获得名次的话,从来没想过,或者说in my dreams。
资格赛(Qualification Round):3个题目,给我的感觉是难度依次递增。其中最为阴险的是最后一题(我被秒杀了)。
第一题:Snapper Chain。简单题。小输入:9739/11496,大输入:8169/9676。N位2进制外加模(mod)运算。33分获得的相对轻松。
第二题:Fair Warning。小输入:3372/4419 ,大输入:2500/3042。整体难度最大(几乎没什么人做,相对而言),但是没有阴招(这点非常好)。感觉这题目在考验参赛者数学功力,并且顺带考察了参赛者对编程语言的了解程度。本题的第一个挑战在于数学,更细一点就是初等数论中关于最大公约数(Greatest Common Divisor,简称gcd,不要想歪了)的理解。我的解法就是最常用的递归欧几里德算法(Euclidean algorithm)(其实还有别的算法,更好更快,但是我自己没实现过,也就不用了)。第二个难点在于计算机对于数字的编码方式。几乎我所了解的所有强类型语言(Strongly typed programming language)对于一个10进制数的表达方式最多用两个机器字(Machine Word)。也就是说32位机器上最大的数字也就是用64位表示,再大就要溢出了(Overflow)。所以为了不自己写一个大数结构(自己写的话,加减乘数都太烦了),我就选择了Python(版本号2.5.4,GAE也就支持到2.5)。Python最大的好处就是不限制数的长短,只要内存够用就行了。这题目困扰了将近一天时间,解答出来已经是code jam时间23:13:14了。累计错了5次,很囧。我随便浏览解出这题的人的名单里面没有人超过4次的。
第三题,Theme Park。小输入:8274/8745,大输入:3108/7845。题目很简单,陷阱很可怕。这是一个计数问题,可怕的地方在于如果采用简单的循环方式解题的话,不可能处理那个大的输入文件,我就给这道题目秒杀了。
最后得分:76。和大牛们不能比,我也就享受这个解题过程中给我带来的困扰罢了。对,是困扰。我自知天资愚笨,所以只好勤加练习。和跑步一样,我羡慕那些天生就能跑得飞快,跑得时间超长并且不吃力的人,但是我自己一跑就知道自己慢并且非常吃力。我也知道自己再怎么努力也追不上那些天生体力好并且快的人。可是我知道这个世界不仅仅需要牛顿、爱因斯坦和比尔盖茨。