百度之星 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名,好怀念啊……不知道明年还有没有机会继续玩……

Javascript 学习心得

这几天做 Ajax,顺便研究了一下 Javascript,发现以前对 Javascript 是完全不了解=.=

总结如下(以下简称 Js):

1、Js 中没有 Class,只有 Function,一个 Function 可以看成一个类的构造函数,new Function 即 new Class。每个 Function 有一个对象prototype,new Function 的时候,自动把这个 Function 的 prototype 复制到新的对象中。

2、Function 中可以使用 this 关键字,指代的是包含这个 Function 的类,不过 this 是动态绑定的,比如

运行结果是 y。这种模式在 Lua 中见过,如果要让运行结果是 x,要对 x.a 做一个 Binder,显示指定 this 为 x,并调用 a.x.apply(obj, ...)。

3、Js 中没有继承,要实现继承的功能,有 N 种比较猥琐的方法。一种是在新的对象中放一个 base 指针,指向它的父类。还有一种是复制 prototype。不过看上去都很恶心。以前看过 Lua 中有一种继承的方法是做一个索引表,调用函数的时候查找它父类的函数,不过 Js 不支持运算符重载=.=

4、Js 中唯一的网络组件是 XMLHttpRequest,在 IE 7 和 Firefox 中可用,IE 6 要用 new ActiveXObject("Msxml2.XMLHTTP")。XMLHttpRequest 可以产生一个异步通讯的线程,是 Ajax 的主要工具之一。线程的管理依赖于浏览器,具体的说明可以看 Ray 的一篇文章

5、Js 中数值 0 等价于 false,也就是 if (0) {} 等价于 if (false) {},在写 Array.Contains 的时候总算明白了为什么 Lua 中 0 不等价于 false,因为 Array.Contains 可以返回 null 表示没有找到,而调用的时候可以写 If (obj.Contains(val)) {},而不用写 if (obj.Contains(val) != null){},但是 Js 中就只有写后一种了 =.=

6、Js 中有 delete 关键字,但不是用来进行垃圾回收的,只能用来在类中删除一个元素。垃圾回收是自动的。

7、Js 中有很多保留字(因为 ECMA 规范的缘故),比如 class,IE 7 会认为 var class = 0 是错误而停止执行。

8、Firefox 中的 String 重载了 [] 运算符,等价于 charAt,但这不是标准。

9、Js 和 Java 同宗,N 多相似的地方,比如 Date 中月份从 0 开始,0 表示一月;String 是不可变类;函数的命名和 Java 几乎完全相同。

10、Firefox 下不允许修改 Object.prototype,而 IE 下可以。

先写到这,以后再补……

Topcoder Open 2007 Algorithm Round 2

又是1点的比赛,真累=.=

上手第一题就卡了,蛮简单的一道题,枚举就可以了,结果想了半天才想到,交了之后只剩下半小时了。然后打开第二题发现是动规=.=,立即放弃,不过证明了贪心是错的之后,challenge的时候顺利cha掉一个,嘿嘿。但是最后总分只有166T_T,如果再能cha对一题就能晋级了,唉,75刀啊……

challenge结束的时候,有人跑到我的房间里说,去Room 27看看,第一题全被cha了,好奇地跑到Room 27,场面真壮观,100多个人,都在仰慕Egor大牛的challenge水平,这个房间除Egor之外所有人的第一题都被cha了,很多人在问Egor有什么特殊的数据,后来Egor说是一个非法的数据,但是通过了系统的检查,自然是能cha掉所有人了。

但后来Egor同学的命运发生了戏剧性的变化。challenge结束的时候,Egor同学成功地cha了15个人,拿了50*15分,总分爬到第二名,仅落后于Petr。然后admin发现了系统有问题,修正了bug之后,Egor同学的challenge自然是失败的,那也就是说他拿到的50*15分不算,还要倒扣25*15分。最有意思是,sys test之后,Egor同学的第一题还挂了,没进前300名,也就是不能出线=.=

不过再后来有很多人为Egor打抱不平,说这是系统问题,如果Egor第一次cha的时候,系统就说它失败,那他就不会cha之后的几次,所以后面几次的失分不能算在他头上。这个争论一直持续了7个多小时,admin总算接受了这个方案。不过我到现在都没收到不能进下一轮的通知信,说明admin那里还有很多事情没有搞定。

Topcoder Open 2007 Marathon Round 1 to 3

显然我还没有领悟marathon的真谛。

第一轮的题目大意是,有一座山,可以表示在101*101的方阵中,每一个方格要么为空,要么为山体。选手可在任意为空的两点作一次测量(从一点发射一束光到另一点),系统返回接收到的光束的强度。由于打穿了山体,所以光强有衰减。又由于测量仪器的问题,测出的值带有随机误差。经过有限次测量后,选手需返回第一小块山体中所含重金属的密度(这种重金属就是导致光线衰减的原因)。

根据题意简化之后,实际上就是求解一个方程组,其中每个方程形如:

其中,ki为山体编号的非空子集,X为所求密度,ai为光束穿过该山体的路径长度,b为测量所得的值。

网上查了一下,这种类型的方程叫做非线性方程,貌似还没有通用解法。我的解法是对于左边只有一项的方程,直接求出解,然后把解出的X代入方程组消元,再找左边只有一项的方程,以此类推,解到无法继续为止。但是后来发现,由于b是不精确的,所以迭代的次数越多,解出的值反而越不精确。由于是第一轮,参加人数少,晋级名额多,所以迭代一层的分数,已经足以晋级了,就没有详细研究下去。

第二轮的题目叫“TwoCardDraw”,牌类游戏,貌似是"FiveCardDraw"的简化版。大致规则是选手和系统双人游戏,一轮分为三个环节。上手各拿到2张牌,并各下1注做为底注,在第一环节中选手和系统都可以raise(加注)、check(跟注)和fold(放弃),raise不能超过三次,达到三次必须check或fold;若在第一环节没有人fold,则进入第二环节,在第二环节中,选手和系统可以换牌,换0、1、2张牌都可以,然后进入第三环节;第三环节的规则和第一环节一样。第三环节结束后,就各自亮牌比大小。对子>散牌,同为对子则比牌的大小,一样则平局,注码平分;同为散牌则看最大牌的大小,若一样则看次大牌的大小,再一样就平局,注码平分。非平局胜者赢取所有注码。在第一第三环节时,每次raise的注码为定值,bet1和bet2,游戏开始前就约定了。选手一开始有10000注,系统有无限注=.=,进行10000轮游戏,然后计算得分。

我对牌类游戏一直不擅长,看了一下sample的系统设定,发现是基于枚举变量的随机变法,即当XXXX情况时,有A%的机率raise,B%的机率check,C%的机率fold。然后我就模仿这种做法,并且扩展了枚举,然后得到了近300个变量,寒=.=,维护这么多变量真是件不容易的事。试了很多策略都不尽如人意,最后排在191名,有惊无险得出线。

比赛结束之后看了前10名的代码,发现他们大部分都是用我的方法做的,只是变量更多,多到需要进行编码压缩的地步了=.=

第三轮的题目与第一轮类似,讲的是一个养护工人要维护一片n*m的树林,树木种在方格内,人可以在方格线上走,并且可以在交点处观察。每次只能观察东南西北四个方向,于是可以得到左右两排树的信息,最近的两棵树一定是精确的,要么有虫害,要么没有。越远的树越可能有误差(有虫害的看成没有,没有的看成有)。每次观察,最近的两棵树,如果有虫害,就会被自动标记上。最终得分和被标记的数量有密切关系。但是由于时间有限,养护工人不得不在天黑之前回家(X-File?),而走路和观察都消耗时间,所以策略很重要。

基于第二轮结束得到的经验,这一轮我写了个自动测试工具,并且生成了100组数据,这样就可以对新的策略进行实时的评测了。但是策略都不太理想,一、最容易想到的是对每一棵树打分,分数最高的就是最有可能有虫害的。二、根据题目中地图的生成规则,有虫害的树比较集中,于是打分的时候,有虫害的树对周围的树有加权。三、在小范围区域尝试几次都命中后,直接跳转到其它区域。四、若分数最高的树离自己比较远,就一点一点移过去,而不是一下子过去,防止工人在两块区域之前走来走去。五、在标记一棵树的时候,先对两个方向(一个棵可以从两个方向被标记)做评测,然后观察能获得更多数据的方向。主要就是这些策略,不过得分最高一次只有26分,最终晋级需要30分,太郁闷了=.=

于是TCO07 Marathon就止步于第三轮了……

Topcoder Open 2007 Algorithm Round 1A

本来以为凌晨的比赛中国和东欧的选手会少一点,没想到注册完发现Petr和ACRush都在,我的排名是倒数的,郁闷了,无奈只有硬着头皮上了。

第一题一开始以为是贪心,敲完之后发现连sample都过不了,然后才发现贪心是错的,于是想到了二分答案,这种策略没用过几次,每次都不能一下子反应过来,再加上写得不太熟,浪费了很多时间,交了之后只有174分。

第二题乍看之下觉得比较复杂,后来发现只要枚举就可以了,不过我对矩阵一直很头痛,调试了很久才过sample,拿了283分。

两题之后已经50分钟过去了,看了下排名189,觉得晋级应该没问题了,第三题也没仔细研究。题目读了很长时间,发现貌似可以用搜索做掉,写了半天发现写错了=.=,于是放弃,开始想test case。

challenge的时候我们房间异常安静,没有人被cha掉,由于第一题太简单,第二题代码太复杂,我都没想出很好的test case,于是就去看总排名了。Petr真牛X,coding结束的时候落后ACRush10分,challege瞬间超过了ACRush 100多分=.=,于是跑到他的房间瞻仰一下,看到他房间挤了4X个人,都在看他的代码=.=

system test结束,2道题都过了,最终排名122,顺利晋级^_^