百度之星 2010 题目篇

今年的百度之星改进了许多,比如可以使用百度的 ID 注册,而不需要另外再注册一个 ID。可能已经受到高层关注了吧,因为之前的几次有传言说公司高层并不重视,组织比赛的人员只能在业余时间加班加点,比赛的质量也有所下降。不过今年依然没公开测试环境的具体参数,没公开复赛的具体成绩,虽然这些数据不重要,但我依然希望有“知情权”。另外中文数据还是用 GBK 编码,好像从第一届开始就这样,而不是用 Unicode,公司内部标准?

废话不多说了,直接说题目吧:

初赛是一个对战类的游戏,给定一张地图,双方各用 5 辆坦克来争夺资源,先抢到一定资源的一方获胜。坦克有 3 种类型,Sniper、Striker 和 Pioneer:Sniper 血少但射程长,比自身视野都要大 1,于是就产生了一种策略“盲狙”;Striker 攻击力强,射程一般,比较中庸;Pioneer 血硬射程短,适合快速突破对方防线。常规的思路是计算坦克与资源点之间的二分匹配,在最短时间内抢到尽可能多的资源点,并沿路攻击敌人。这种模式配合 Striker 的攻击力,加上一点点优化,可以达到比较优的抢资源速度,但这样就用不到 Sniper 的射程优势了。于是有人提出了预测的算法,简单来说,大家都用二分匹配(或者某种贪心算法)的话,坦克都是以最短路径去资源点的,一旦知道敌对坦克的坐标和时间差,就可以猜对敌对坦克的坐标,只要进入了 Sniper 的射程,无论看见与否,可以直接射击。于是为了反预测,就要在行进过程中加入一些随机扰动,或者在预测到下一步会被击中的时候停止移动,不过这样会进入僵持状态,在落后的情况下,这样是很致命的。

由于初赛是前 2000 名晋级,并且我没多少时间可以用来调试算法,就简单写了一个二分匹配交了,心想应该没 2000 个人能写出预测的,果然晋级了……

复赛是传统的百度之星模式,两场,每场 5 题 8 小时前 20 名晋级。题目在这里:/

复赛第一场:

  1. 蜗牛:简单的 DP,递推天数累加就行了,要注意的是结果有可能是大数。
  2. 午餐聚会:当时没想出来怎么做,随便猜了一个规律-_-
  3. 猜猜你在哪儿:一道交互题,随便搞了个带阈值的随机投点,效果一般。
  4. A+B 问题:在这题上消耗了起码三个小时,中文数字和阿拉伯数字互转实在太麻烦了,这题基本没难度,就是看细心程度。
  5. 并行修复:没想法,也没时间写了,直接交样例-_-

复赛第二场:

  1. 内存碎片:我的算法是把请求按长度排序之后,划分成 K 部分,使得总数最小。纯递推的复杂是 N*N*K,显然太大,观察了中间结果发现有单调性,可以化简成 N*logN*K,不过只拿了 25 分,不知道哪里错了-_-
  2. 购物搜索调研:具体的推理忘记了,好像是要找出一段子序列中的最小值,于是想到了 RMQ,不过只拿到 30 分-_-
  3. i-Doctor:据说是 Bayes 公式,概率学得不好,随便写的-_-
  4. URL 规范化:纯模拟题,考细节的,辛辛苦苦写了三个多小时,0 分>.<
  5. 玉树驰援:题目很长很复杂,就没怎么看,也没做……

复赛依然延续着我做 Astar 的规律,不管怎么做,第一场的分数总是比第二场好,下次不参加第二场了-_-

决赛是植物大战僵尸的简化版,题目在这里。时间 8 小时。我上手就选错了方法,尝试去写一下模拟器,然后通过遗传算法找最优解,事实证明时间完全不够,理解题目用了 1 小时左右,写模拟器用了 4 小时,而且模拟器 bug 很多,修完 bug 就差不多快结束了,真正的算法没来得及写>.<

最终就拿到一只熊,任务完成,咱也不奢望什么:P

百度之星 2008 初赛

好久没做比赛了……Topcoder时间太晚,POJ速度太慢,sigh......

百度之星蛮好,同一个时区,题目也没那么BT,很适合我,嘿嘿……

5月初就报好名了,但是一直没练习,到了30号,不练习不行了,只好爬到POJ上去做简单题,顺便调试一下机器环境,毕竟很久没用过了。一晚上做了5题,感觉还不错,然后群里就有了这么一段对话:

“一晚上切了5题,状态恢复了……”
“你做的是A+B吧”
“估计是A*B。”

看来大家都很了解我么=.=

31号晚上,吃了晚饭过来看题。题目见内

第一题很简单,O(n)搞定,不过为了保险,我还是检查了N遍才交的……

第二题一看是中文题,马上扔掉。做完了3、4之后再回头看,GBK的编码还是比较简单的,而且重点不在这里。不过那个DP有点恶心,假设了一个条件,然后就写了……反正过一个test case就有分,能拿几分是几分,嘿嘿

第三题也没什么想法,随便写了个暴力的骗分。群里两个人在讨论线段树,我听得完全莫名,唉,老了……感觉LJ同学说的变异RMQ可能是对的……不过来不及写了……

第四题么,二分答案+随机投点,也就随便骗点分吧……贴吧里的几个数据,我都没过=.=貌似是有很牛的数学解法的,不过当时头有点晕,也就懒得想了……

其实我是把重点放在第二场的,因为按Topcoder的惯例,越往后晋级的可能性越大,嘿嘿。

然后1号早早地吃了中饭,安安心心地等比赛开始……(貌似没人贴题目出来)

第一题,上手就是中文题,比较郁闷,还好题目简单……

第二题,纯几何题,俺数学不好,先跳过……然后发现第三题更难,只好做完四再回来做二,郁闷地不行,好久没碰几何了,公式都快忘了……都最后也没过sample,丢脸了=.=

第三题,看上去貌似是最小费用流,没有模板,交了个骗分的代码了事……

第四题,又是BT题,没什么想法,只好暴力了,速度写完之后,就开始抉择二和三的事了=.=

貌似第二场还没第一场做得好,郁闷了,这次astar悬了……

不过话说回来,复赛的时候我正好在黄果树,有没有时间比还不确定……今年的免费旅游不乐观啊=.=

百度之星 2007 决赛

到达宾馆的当天晚上就有试机时间,坐定之后我赫然发现桌面上有CS1.6和CS1.5的图标=.=,然后就在我开始找有哪些IDE和可用资源的时候,主持人说:接下来我们开始分组打CS吧。巨寒……然后我们就按分组打CS了,我所在的1组由于实力非常牛,轻轻松松割掉了对面的2组。玩的时候有几个其它的客人在WTommy后面讨论:“你说他们这是在干什么那”,“游戏比赛嘛”,“不对,门口的牌子上面写的是‘程序设计比赛’”,“哦,他们在编程打CS”……由下文看来,这段话印证了一条古语:旁观者清,当事者迷。

第二天早上,比赛正式开始,题目上写着:实现一个CS1.5的Bot。于是大家都明白了,第一天的比赛是有原因的……然后下载了一个压缩包,包括MinGW的编译器、一个make程序、Half Life和Podbot的SDK,压缩包有27M,其中可以修改Podbot中的两个文件,每个文件包含5个函数,用于T和CT的买枪、枪械瞄准、手雷瞄准和一个基于A*的寻路算法(只允许改其中的g、h函数)。玩过CS的人都知道,这5个函数并不能实现CS的常规策略。对T而言,最简单的策略是全部冲向一个雷区,由于CT要分守两边,以多打少的胜率会相当大,实现这个策略需要对那个寻路算法和CS的路点机制非常了解,在比赛时间内做到这一点基本不可能;对CT而言,面对T的冲击,需要队员之间的通讯才能更好地防守,而CS的通讯机制我基本没看懂=.=

比赛中没有提供任何的API文档和说明,程序框架只能自己看代码,核心代码至少有几千行,我研究了2小时左右发现看懂框架不是5小时能完成的任务,于是放弃,只找有用的API。而且测试起来非常麻烦,一个完整的测试过程是:先把源代码make成dll,然后覆盖掉原来的文件,启动CS,开一个新游戏,加bot,观察bot行为,结束之后完全关闭CS。基本上主要的时间不是用在写代码上,而是在看bot打架和开关CS上。

原始压缩包中的代码是可以通过编译并且正常运行的,只不过运行出来的bot比较傻,但是只要在代码上修改一个参数,就可以使bot在三枪之内杀死一个人(某些威力极小的枪除外),由于CS的对战原理,这样的bot在1v1的情况下,谁先开枪谁赢,而且根据CS对bot的控制,“谁先开枪”是随机的。另外,评测的三个地图中有两个是埋雷地图,由于CT近乎弱智的拆雷AI,导致了CT唯一的赢面是在T没埋雷之前把带雷包的T干掉,然后守雷包,而CT能不能和带雷包的T相遇,基本上也是随机的。综上,评测的结果带有很大的随机性,多运行几次测试结果就很有可能改变,换句话说,决赛是拼RP的比赛。

比赛过程中最不爽的一点是主持人在不停地讲解比赛规则和透露代码细节,使我不得不边写代码边竖起耳朵听,还不能去洗手间,生怕漏掉点什么。比赛规则显然是可以在赛前就公开的,没必要放在比赛过程中说,貌似比赛组织者认为比赛毫无秘密可言,各种细节可以被选手猜出来,从初赛开始,很多问题都无法在赛前获得定论,比如STL的使用问题。而在比赛过程中透露代码细节,更是莫名其妙,比赛一开始主持人就说:这次比赛,阅读代码的能力也是考察范围之一。但是之后又不断的透露关键代码内容,看上去潜台词就是“一定要按我的思路走”。

颁奖典礼被放在了第三天的晚上,冠军是来自SJTU的某同学,据说是复赛第50名=.=。颁奖典礼除了颁奖就没其它的了,连个决赛的录像都没,难道选择CS做为比赛平台不是为了演示?只是在典礼结束的时候应广大选手的要求重新模拟了几场比赛,而比赛的结果也证实了其不可预料性。

比赛之外的活动还是相当不错的,滑雪、高尔夫、游泳,虽然我一个都不会=.=。滑雪的教练不错,很详细地讲解了各种细节,基本上滑雪过程中没出什么大问题。高尔夫就比较挫了,电视里看别人打高尔夫是非常休闲的运动,我们一上去就变成了体力活,要么打空,要么打到地上,相当地累=.=。游泳就不提了,说是说XX海洋世界,本以为会像热带风暴那样,结果就是一个水池,玩的东西都没有=.=。

第三天的时候还去参观了百度公司,见到了老Boss李彦宏。我不常用百度的产品,也就没提出什么有新意的问题,不过百度在中国的人气是不言而喻的,Google在中国的市场一时半会还无法和百度抗衡,曾经听说有人上百度之前先要上Google搜百度的网址,然后再去用百度搜索。不过百度的外文搜索能力比较差,就我个人而言,经常要搜索一些英文资料,百度显然是不能胜任的,而且大多数专业都是英文文献比较多,所以百度要想占领高端市场的话,还是要加强外语的搜索能力。

总体而言,决赛的组织和安排工作做得很周全,看得出一些细节方面是经过研究的,只不过经常拖时间,有点印度的感觉=.=。明年争取继续进决赛,争取拿熊^_^

百度之星 2007 复赛

8小时的比赛,好BT……

第一题求一个交通系统中一点到另一点的最短路。先要求出任意两条线段的交点,然后求目标点到每条线段的最近点,然后用最短路算法求出答案。纯模板题,一共300行左右,自己写的大约只有40行不到,其它都是模板……

第二题求URL是否满足给定的规则。规则巨麻烦,题目中给出的说明不足以说明问题,于是管理员在贴吧上给出了更详细的说明,但还是不全面。跟着感觉做吧=.=

第三题给出N个人,每个人有一些属性,要求选出一些属性,使每个人的选出的属性值之和中最小值最大。咋看之下没啥想法,直接随机化解=.=

第四题求K个工程队修好N个公司的最小损失。有点像Topcoder Marathon LumberjackExam那场比赛的题目,不过时间不够了,而且给出的模拟器没有图形界面=.=,没有仔细优化,只有写了个可行解,拿几分算几分吧……

总体来说,第一题模板题、第二题英文阅读题、第三、四题marathon题,如果能保证前2题拿高分,进决赛应该没啥问题吧……希望能进,嘿嘿……

百度之星 2007 初赛

百度之星又来了,规则还是和以前一样恶心,中文题,只允许C和C++,不告之硬件环境和编译选项,不公布测试数据……最无语的是,热身练习的代码是不运行的,这样限制代码的运行时间就完全没有意义了,谁知道你的CPU是PII的还是双核的……

今天发现进了复赛,于是过来写报告,以免像去年那样,写完解题报告,发现没晋级=.=

我做的是第一场,第二场没时间做……

第一题暴力并查集,蛮简单的,数据规模也小,不过郁闷的是逻辑写错了一点,会把一部分“Yes”判成"No",还好只错了3个Case。

第二题数学题,看完题目没有想法,然后发现Case有简单和困难之分,于是目标变成过前5个Case。然后发现只过了1个Case,回去看了一下代码,规则2的枚举里把一个"10"写成了"9",郁闷=.=

第三题看上去像二分匹配,当时时间不够没有细想,时间快到的时候发现输出都是0和1,于是交了一个随机输出0和1和代码,果然一个Case都没过=.=

第四题是个分析SQL查询的题,不过由于WHERE子句里只有=和AND,所以只要找出所有的WHERE子句,然后联立即得查询条件。交了代码之后发现,由于写得匆忙,前半段用了scanf,后半段读整行用了istream,晕……最后只过了2个Case。

最终得分22分,不算高但还是进了复赛……

关注了几天的贴吧,发现部分参赛选手是初学者,类似ACM/ICPC的输入已经算是比较麻烦的了,还加入了中文,据说gets也不能用,输入的难度就一下子上去了……建议百度可以借鉴ICPC或者Topcoder的模式,赛前多给选手一些条件测试系统,题目里降低一些算法无关的复杂度,赛后公布一下数据或者至少说一下未通过的原因吧……

IPSC 2007

昨天从学校里回来之后,看到群里有人说IPSC是“今天下午”,顿时寒,完全忘记了这事,还好群里有提醒。然后去IPSC的网站看了一下,报名还没截止。本来想叫Ray和flyingdog一起做,但发现他们两个都不在线,于是注册了一个单人的帐号。顺便看了一下历史成绩,发现中国的高中生们真牛,从99年到06年,8次比赛拿了5次高中组冠军,不过总排名上还没有中国人拿冠军,悲哀=.=赛后ACRush说他是第4年第二了,汗……

比赛是8点开始,7点吃好饭发现Ray和flyingdog都在,于是把他们拉上一起比赛,还把队名改成了CSPI=.=。

一共12道题,由于题目名称事先公布了,看到F是关于Sudoku的,于是很感兴趣(因为我有Sudoku模板=.=)。比赛开始之后,我先看了F,flyingdog看B,Ray看L。F的确是求解Sudoku,但是三个Sudoku的联合求解,就是每个Sudoku之间有一些格子的值是一定要相等的,我一开始没法估计时间复杂度,就先放弃这道题,而且后来也一直没去做这题(赛后看了题解之后发现,easy input可以对每个Sudoku依次独立求解,真郁闷=.=)。Ray看了L之后发现是概率题,直接放弃。flyingdog看了B之后发现在英语阅读题,也放弃,汗……然后发现A和E已经有人过了,然后我看A,flyindog看E,Ray看了B。A是简单题,几分钟就写完过了,然后转向I。flyingdog看了E之后发现easy input可以手工做掉,而hard input需要图像识别……Ray发现B的easy input有规律,也可以做。flyingdog把E1过了之后失踪了一会,回来之后和我们说接到Google的面试通知,时间是今天早上9点,于是放弃了比赛,BS之=.=。然后没过多久,Ray也收到了面试通知,不过还好时间是下午的,还能继续比赛,Ray把B1过了之后就在研究B2,经过很长时间之后也过了。这时候我I已经基本搞定了,题意比较复杂,但是简化之后实际上是两次floyd_warshall,实现起来蛮简单的,而且没精度问题。然后把所有的题目扫了一遍,发现G1可以做,就做掉了,其它的题目都没什么想法。花了点时间看排名,发现排在第一的队叫“Moscow SU X13”,后面还跟了“(with coach)”,非常寒,巨牛的队啊……还有个队名叫“SnapDragon Fan Club”=.=,还看到“Save the cheerleader, save the world”=.=,都是很强的队。

之后的时间基本是垃圾时间了,很久没有连着几个小时做题了,有点不太习惯了。而且IPSC的赛制和ACM有一点点不一样。easy input有时候可以用暴力解掉,所以还要分析数据,不像ACM看完题就知道能不能做。

最后一共拿了11分,排在99名。05年的时候我做过一次IPSC,拿了4分排到2XX名,好怀念啊……不知道明年还有没有机会继续玩……