月度归档： 2008 年 7 月

邮件提示通知，先前注册的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相关文件