Akagi201
5/15/2014 - 4:22 PM
codeforces.md
介绍
这是一个俄国的算法竞赛网站,由来自萨拉托夫州立大学、由Mike Mirzayanov领导的一个团队创立和维护,是一个举办比赛、做题和交流的平台.举办比赛和做题就不说了,“交流”指的是自带blog功能,可以求助/发布题解之类.官方语言是俄语和英语,因此可能有些偏僻的题目的题解是用俄语写的,别慌,扔给Google Translate翻成英文,可读性还是很不错的.至于英语,cf上Russian English确实有,但并不严重,题目里偶尔会出现很奇怪的表达方式或者不常用的词汇,这时候就借助样例吧,找个人问问也是可以的.cf最大的特点是比赛,所以接下来主要的篇幅用于介绍cf传统比赛的规则. 在cf,所有的用户根据在以往比赛中的表现被赋予一个Rating并冠以不同的头衔,名字也会以不同的颜色显示,比如Expert是蓝色,Master是黄色,因此我们通常以颜色代指头衔.选手们按Rating以1700为界划分为Div.1和Div.2两类,相应地,cf上的比赛也会指明是Div.1还是Div.2,抑或同时进行.Div.1的比赛较难;如果同时进行,Div.2的CDE三题会和Div.1的ABC三题相同.每次比赛结束后Rating都会有相应的变动.对于没有参加过比赛的新用户,在比赛后重新计算Rating的时候,他的Rating会被视为1500. 在比赛中,选手有2个小时的时间去解决5道题,而解决某题得到的分数由该题当前的分数减去(不成功的提交次数)50,这里,某道题的分数是由比赛开始时的分数随时间线性减少得到的.同时,这里的“解决某道题”是指Pretest Passed,即,通过了一次仅含部分测试点的测评,而最终决定是否得到这道题的分数,要看比赛结束后的统一测评(System Test),如果在这时没有通过,就称FST(Failed System Test).在比赛中的提交可以看到在哪个测试点出了什么问题(例如,仅一行WA on pretest 3). 同一个Div的选手将被划分到若干个Room里,每个Room约20位选手;当某道题Pretest Passed之后,可以选择锁定(Lock)该题代码,之后就可以查看同一个Room内其他选手该题的代码(当然了,这也是已经通过pretest的),并试图找出其中的漏洞,自己出一个数据(可以手打,也可以提交数据生成器)让这个代码不能通过,这就是Hack,有时也称Challenge.一次成功的Hack可以得到100分,而如果没有成功,将会被扣50分,分别被称为(un)successful hacking attempt. 在比赛中,选手可以看到实时的排名(Standing),也可以选择只看加了好友的选手的排名.此外,还可以看到某题有多少人通过的信息,这在某些情况下很有用. 关于比赛的事情大概就是这么多.cf题库的所有题目都是在该平台上举办过的比赛的赛题,尽管WJMZBMR曾经表示由于出题人很杂cf的题目质量参差不齐,但我个人认为还是够可以的,两个小时五道题也确实很能让人得到锻炼.和Spoj形成鲜明对比的,cf的机子很快,所以很容易培养出STL依赖症等等不良代码习惯,应当引起足够的注意. 在cf上做题的过程当中如果遇到困难,首先可以看数据.数据从某种程度上来说是公开的,在提交记录页面可以看到所有你的程序运行过的数据,但是太大的数据也只会显示前几行,因此也不算完全公开.cf的测试数据笔数通常会让习惯了10个点的人大吃一惊,一道题动辄80个测试点,甚至有的有200多笔.通常来说,前面大概5组是比赛时的Pretest,尽可能的涵盖各种情况,也有放个大数据卡TLE的;其后的数据规模递增,但是最后几组又会很小——这是比赛时Hack的成果.Hack成功的数据会被追加到该题的测试数据当中. 如果数据不能解决问题,可以试图去找题解.题目页面的右下角会标出它所属的比赛的相关文档,通常会有Announcement(赛前和赛中的公告,其中赛中的公告通常是明确题意之类),有些则会有Tutorial,这就是题解,顺带一提cf上另外一个表示题解的词是Editorial.一次比赛的题解可能不是官方的,也可能不包含该词比赛全部的题目的,也有可能是用俄语写的(前面提到过了,翻译成英语就好),也有可能有好几篇(这会以Tutorial #1,#2的形式标识).近期的比赛多半都有官方题解,以前的就不好说了.这时候需要借助另外一个神器:神犇们的代码.cf上所有的代码都是公开的,并且支持按照提交先后(Judging Time),运行时间(Execution Time)和代码长度(Solution Length)进行排序.不仅仅是帮助做题,这个功能对于了解一道题的各种做法也是有好处的. 主要的东西就介绍完了.这里再补充一点一些零散的东西. 关于Rating的计算 : 这是一种类似Elo Rating的系统,可以在cf的FAQ或Wiki百科找到更详细的信息. 关于Contribution : 在用户信息页面会见到这个东西,它用来衡量一个用户对cf的贡献程度.这个数值取决于该用户所写的blog和他对其他的blog所作出的评论的“反响”.每个blog的下方和评论的旁边都会有一个往上和往下的箭头以及一个数字,表示你可以对他进行好或者不好的评价,而数字则显示当前已有的评价,而这就是前面说到的“反响”.点击了往下的箭头会让这个数值-1,点击了往上的箭头则会+1或+2,这里+2的条件是你本身的contribution不低于+25.如果你打算做评论,请谨慎,因为在贴吧里很正常的回复可能会被认为“没意义”或者别的原因而反响很差(比如一句正常的Congratulations!可以被-12),随而contribution也会很难看.由于这样的原因,你可以选择完全可以无视这个数值.另外关于Contribution....只要你混到前10或者IGM什么的.....就算扯淡或者就说个"I enjoy your problems :)"都能被脑残粉+30... 关于GYM : 在gym里举办的比赛基本上是ACM/ICPC规则的,可以单干,也可以组队(人数似乎没有限制).gym的题目并不会在Problemset里显示,提交之后也不能看到数据(和常规比赛时一样,仅能看到一行TLE on test 137之类),不过据说在名字变红[即(International) Grandmaster]之后可以看到数据.当然了,gym的代码也是不公开的. 两条补充: 关于Virtual Participant : 有时我们会在某条提交记录的ID右上方看到一个小小的#号或者显示一个时间,鼠标移上去会出现Virtual Participant的字样.正如其字面意思,这意味着这个用户正在“虚拟”参加一场比赛.如果你虚拟地参加一场比赛,系统会在接下来的2小时内(如果gym的话另当别论)为你模拟当时的情境——包括Standing等等. 关于奇葩的测评结果 : 这包括Compilation failed,Denial of Judgement和Judgement Failed.这通常不是提交者的问题而是系统出了点差错.Judgement Failed通常会呈现爆发的样子,一段时间内几页都是,当这种情况结束的时候就正常了;而Denial of Judgement仅会在某段时间内在特定的题目发生,可能要等上个一两天才能得到解决(也有可能在问题解决后被自动重新测评);Compilation failed我还没有见过...字面意思是编译器不干活? 如果在一次比赛中,多次将某题Pretest Passed,则System Test的时候以最后一次为准,其余的就会被跳过(Skipped). 不小心忘去掉system("pause");然后。。。Judgement Failed 如果数组开的实在太大了，不会MLE，会Denial of Judgement Denial of Judgement就是数组开的太大 （：MLE是中间超出限制,你开个1e51e5的数组就会直接Denial of Judgement
附 各个头衔的Rating范围和名字颜色: [2600, inf) International Grandmaster 红 [2200,2600) Grandmaster 红 [2050,2200) International Master 黄 [1900,2050) Master 黄 [1700,1900) Candidate Master 紫 [1500,1700) Expert 蓝 [1350,1500) Specialist 绿 [1200,1350) Pupil 绿 (-inf,1200) Newbie 灰
附 "ALL" CodeForces Rounds Tutorial By iman_MC codeforces.com/blog/entry/1492 有些Codeforces上有人发过的题解并没有被链接到对应的题目上(即,存在题解,但是题目页面右下方并没有Tutorial链接),有可能可以在这里找到. 当然这也并不是完全的,而且时不时会更新.具体里面有哪些我就不废话了,各位自己去看看吧.
规则
理解
- 5小时5道题, 题目由易到难, 分数由低到高.
- 比赛前会随机(有可能根据rating)分到不同房间, 每个房间大约20人.
每道题的得分 = 总分 - 分钟*每分钟损失 - 失败次数*每次失败的惩罚- 流程: submit -> pretest(2~10tests, 不包含边界值和特殊值) -> 得分 -> lock(不可修改了) or not(被hacked了可以修改, 重新提交的话也必须除了跑pretest也必须跑别人hack的样例) -> hacking others in the same room)