Google Code Jam 2008

邮件提示通知,先前注册的Google Code Jam开始了,于是登进去做做题。
Qualification Round总共三题。大致看了一下,最后一题—‘苍蝇拍’,没啥自然的思路,感觉算起来比较麻烦,于是就选了其他两题。这两题倒都还有比较明显的思路。

其实,从Google Code Jam设置的方式来看,Qualification Round的题都不难,但通过大、小输入数据集来考察程序员对于各个边界条件的处理。

第一题,’拯救宇宙’;
由于’Queries must be processed in the order they’re received.’,所以简单的标记,然后找大块就可以算出转换次数,如果需要,也可以得出其中一个可行的转换路径。时间复杂度O(N)。

需要注意的地方是:
1. Base case查询个数可能为0;

我在第一次试验Small Input的时候Fail掉,是由于忘了清空标记的时候,把缓存的标记计数也一并清0。
改正后,Small/Large Input结果均正确。

郁闷的是,这题Large Input在上传结果的时候,不知是Firefox缓存还是Google Code Jam系统的问题,Large Output依然为前一次上传的Small Output的文件。以后大家一定要注意检查一下上传结果。

第二题,’火车时刻表’;
A、B两边分别按时间排序后,各自顺序统计一遍,也很简单,时间复杂度依然为O(N)。

需要注意的地方是:
1. 如何组织录入数据。我采用的是以时间为key的两个哈希表。
2. 时间可能重叠。这是比较明显的一个问题。重叠的时间在key上通过+1、-1来相互抵消。这样在录入数据的时候,就把重叠时间的问题解决了。
3. 时间超过24小时的问题也很明显。但由于’All arrivals and departures occur on the same day.’,所以反而让我忽略了这个问题。但其实这个问题依然存在于类似’23:52’ + ’20 mins turn around time’的情况里。我后来加上了对这种情况的ignore的处理。

总之,如果有心情的话,做做Code Jam的题还蛮不错的。

下载Saving The Universe相关文件

下载Train Timetable相关文件