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,顺利晋级^_^

Topcoder / CSDN Competition

这比赛还真恶心。第一题可以用3个for解决,第二题用1个while+2 个for解决。前两题瞬间搞定了,一看时间才过了15分钟。然后打开第三题,看了5分钟,愣是没看懂题意。结合sample看了很久才大致看明白。这种情况还是ICPC好,可以直接问Judge,Topcoder上只好猜了。假设了N个条件后,总算写完了,过了所有sample就交了,也懒得查,题意越看越模糊。

悠闲地等了30分钟,期间看到2个红色名字的人重新交了第一题和第三题,于是仔细想前两题可能的陷阱,未果,重新看了一下代码,没啥写错的地方,也就没改。Challenge的时候不知道网络出啥问题,fetch problem总是超时,只cha掉一份代码,赚了50分。与此同时我的第三题被cha掉,排名从第三跌到2X,前三是没希望了。

等Sys Test的时候在祈祷,排在我前面的人都错2题=.=,结果Sys Test结束,第三题没人过,瞬间排名升到第5,奇迹出现了=.=。不过这么简单的第三题没人过实在说不过去,Judge肯定有问题。后来rejudge了,我的排名最终定在了11名,主要归功于我的打字速度=.=。后来看了zhuzeyuan的代码,才发现我第三题错在哪里,不过题目也没明说,每个人理解不一样罢了。

然后就等T-shirt寄来了,btw,我的T-shirt多得快装不下了,下次能不能送点别的=.=

竞争带来的大麻烦

突然间发现自己有了OrkutFriendsterMyspaceWallop的帐号,麻烦也随之而来……

Friendster是我最早接触到的,由一个国外的网友邀请而注册,但是由于我一直都在用长宽,上国外的网站速度很慢,虽然注册了帐号,但也一直闲置着,直到换了ADSL之后才开始维护。

知道Orkut是因为Google,在搜索Google的服务的时候搜到了它,可惜Orkut也是要靠邀请才能注册的,一直想注册但又没有门路,直到它开放注册之后,才申请到帐号。有关Orkut的产生还有个趣闻,Google当时想在SNS方向发展,最初是想收购Friendster,但是被拒绝,于是才自己做了Orkut。

Wallop最早在别人的Blog中看到过,但一直不知道是什么东东,它好像一开始公测过一段时间,后来关了,删了所有帐号,然后又开了,很神秘的样子。直到看了介绍SNS的文章才了解。加入Wallop是由于很偶然的机会,某人在Blog上说可以提供邀请,于是留了言,然后就收到了邀请。不过加入之后至今没有维护过=.=

Myspace也是看了相关文章才知道的,好在它是开放注册的。

不知不觉中,4家主要的SNS网站都注册了。于是麻烦的事情也来了。

首先,Wallop会每周寄来一份digest,主要是其它人的Wallop更新之类的;Friendster也会定期寄来更新,并且某些特殊的事件还会寄来额外的邮件。

其它,有一些人会通过Myspace寄一些类似交友的邮件来,最初好奇,点进去看了,看上去像是搞色情服务的,页面做得很粗糙,就关了,后来Myspace寄来的邮件一律删除。

最重要的一点,除了Wallop之外,其它三个网站都要填写详细的诸如兴趣爱好身高体重信仰等等的信息,相当的繁琐。除Orkut之外,其它三个网站都提供了Blog服务,但是又不能把Blog的页面链接到我自己的Blog,难道要我一文四发?希望他们可以提供rss读取之类的服务,这样能方便拥有其它Blog服务的用户。

最后,需要邀请的同学可以留言(Wallop的邀请需要上传照片,我手头没好看的照片,所以也就没有邀请=.=),仅限认识的,留言中请留下线索。

WoW登录过程简介

登录过程采用SRP协议,具体版本细节不清楚,反正不是最新版。

相关记号:
    H ---- 单向Hash函数,WoW中用的是Sha1,Sha1生成的结果定长20字节
    N ---- 大素数,32字节
    g ---- N%(一个N的质因子),1字节
    C ---- 明文用户名
    P ---- 明文密码
    CP ---- C + ":" + P,+表示字符串连接
    s ---- 随机数
    x ---- 临时变量,x = H(s, H(CP))
    v ---- v = g ^ x
    a ---- 随机数,保存在客户端,不公开
    b ---- 随机数,保存在服务器,不公开
    A ---- A = g ^ a
    B ---- B = 3 * v + g ^ b
    u ---- u = H(A, B)
    S ---- 客户端:S = (B - 3 * g ^ x) ^ (a + u * x),服务器:S = (A * v ^ u) ^ b,都为32字节
    Key ---- 40字节,偶数字节为H(S的偶数字节),奇数字节为H(S的奇数字节),Key将用于以后的通讯加密
    M1 ---- M1 = H( H(N) xor H(g), H(C), s, A, B, Key )
    M2 ---- M2 = H( A, M1, Key)
    ^ ---- 幂运算
    xor ---- 异或运算
    % ---- 模运算
    所有运算结果都%N
   

登录过程(只包含正常的流程,错误检测忽略):
    0、服务器预先保存着N和g。
    1、客户端向服务器发送C。
    2、服务器根据C查找P。生成s、v、b、B,将B、g、N、s发送给客户端。
    3、客户端生成a、x、v、A、u、S、M1、M2,将A、M1发送给服务器。
    4、服务器生成S、Key、M1、M2,将M2发送给客户端。
    5、如果两边的M1和M2都一致,则登录成功。

[我的ACM之路] 走向成熟

又一年过去,ywy研三了,逐渐繁忙的毕业设计和就业压力使他关心集训队的时间减少,计划中的选拔赛一拖再拖,最终只好取消了,集训队来者不拒。这一年,zyy研二、wl和ywq毕业,不过lj考研成功,使集训队补充了强悍的新鲜血液。这一年Larva进入集训队,并且固执的他们要求一起组队参赛,ywy最终还是没有说服他们分开……

由于学工办不同意集训冲掉军训,于是集训被安排在了8月份。大家还是开心得做着题,讨论着算法。jackie为集训队供献了一个代码交流平台,不过由于时间关系,集训结束之前,这个平台的功能还仅限于统计各人的题量。由于Larva三人都是用Java的,所以集训题库选择了POJ的两卷。那时候我开始学着用C++,因为Java实在太恶心了,Collections Framework和STL没法比。

集训结束之前,ywy安排了4场个人赛,用于做分队的参考。前三场都是简单题,我的成绩基本和当年leojay一样的,第一场2个多小时切掉所有题,后面几场,因为ywy限制了提交次数,我用完了限制,虽然没做完,但仍然排在第一。最后一场比较挫,做到一半POJ挂掉了,我们只好把代码先交到ywy那里,等POJ恢复了验证。由连着比赛压力比较大,我最后一场发挥失常……

新的ICPC赛季,我、jackie和lj组队,参加成都和Coimbatore的比赛。前一年上海和韩国的比赛时间不理想,由于国内的题目难度普遍高于国外,所以选择国内的赛场做为热身是不错的选择,而上海的时间在韩国之后,失去了热身的效果。而成都的时间在Coimbatore之前,这个安排很合理,但是,人算不如天算……

10月份去成都,切掉两道题,貌似做出3道就能排前5,而我们反应比较慢,只落了一个铜牌……

接下来去印度,去之前我们充分总结了成都的经验,并且突击了一下,我在POJ的排名跃升到历史最高点——23位。本以为去印度的强队不多,可以拿个好成绩回来,却没想到主办方的表现实在差强人意。上手一道大数的题目,我在比赛开始之前就敲完了,然后提交,Judge一小时没有工作,一小时之后,判了一个RTE给我,百思不得其解,然后同样的代码再交一次,CE,顿时没有想法了,后来改了一下输入方法,AC了。事后想想,一开始的RTE,如果是输入方式造成的,那Judge的数据格式应该有问题,而CE则肯定是Judge不懂Java=.=。另一道题,在比赛开始后不久也敲完了,等了一个多小时之后,得到一个WA,改了之后AC了。Judge一小时不判题,造成了我们队巨大的时间劣势,最后只排名20位左右,非常地郁闷。

从印度回来之后,jackie退役了,lj研二,接下了ywy教练的位子。集训队里参加过比赛的,只剩下我和Larva三人,下一年的参赛形势瞬间变得严峻起来……

那一年的程序设计联赛,ywy把裁判的工作交给了我、jackie和lj,而联赛则变成了Larva分奖品的舞台。为联赛出题是一件很有意思的事情,要让题目难度有层次,所考察的算法覆盖面广,题意看上去能吸引人。按照ywy的说法,一套题目能成为好题目,那么在比赛中每个队伍都至少AC一题,并且至少有一道题没有队AC。如果在比赛中有一支队伍AC了全部的题目,那命题人就比较坍台了。找一道没有人做得出的题目很简单,比如复杂的模拟题,或者有很深背景的论文题,基本都可以拦住所有的队。然后找一道所有人都能做出的题就不是这么容易了。联赛到现在已经是第4届了,从来都没有一道题能被所有的人做出,而在大陆的所有ACM赛场上也没出现过有一道题被所有队做出的情况。估计按这个形势,A+B是趋势=.=

最终Larva的某人(忘了是谁)拿了联赛冠军,成功抢到了一个DVD刻录机,比我当年第一名的Combo好多了,唉,感叹时代的进步……