【打CF，學(xué)算法】關(guān)于codeforces的介紹

你應(yīng)當(dāng)知道的關(guān)于Codeforces的事情

關(guān)于codeforces的文字 Codeforces
簡(jiǎn)稱: cf(所以談?wù)揷f的時(shí)候經(jīng)常被誤會(huì)成TX的那款游戲).
　　這是一個(gè)俄國(guó)的算法競(jìng)賽網(wǎng)站,由來(lái)自薩拉托夫州立大學(xué)、由Mike Mirzayanov領(lǐng)導(dǎo)的一個(gè)團(tuán)隊(duì)創(chuàng)立和維護(hù),是一個(gè)舉辦比賽、做題和交流的平臺(tái).舉辦比賽和做題就不說(shuō)了,“交流”指的是自帶blog功能,可以求助/發(fā)布題解之類.官方語(yǔ)言是俄語(yǔ)和英語(yǔ),因此可能有些偏僻的題目的題解是用俄語(yǔ)寫的,別慌,扔給Google Translate翻成英文,可讀性還是很不錯(cuò)的.至于英語(yǔ),cf上Russian English確實(shí)有,但并不嚴(yán)重,題目里偶爾會(huì)出現(xiàn)很奇怪的表達(dá)方式或者不常用的詞匯,這時(shí)候就借助樣例吧,找個(gè)人問(wèn)問(wèn)也是可以的.cf最大的特點(diǎn)是比賽,所以接下來(lái)主要的篇幅用于介紹cf傳統(tǒng)比賽的規(guī)則.
在cf,所有的用戶根據(jù)在以往比賽中的表現(xiàn)被賦予一個(gè)Rating并冠以不同的頭銜,名字也會(huì)以不同的顏色顯示,比如Expert是藍(lán)色,Master是黃色,因此我們通常以顏色代指頭銜.選手們按Rating以1700為界劃分為Div.1和Div.2兩類,相應(yīng)地,cf上的比賽也會(huì)指明是Div.1還是Div.2,抑或同時(shí)進(jìn)行.Div.1的比賽較難;如果同時(shí)進(jìn)行,Div.1的ABC三題會(huì)和Div.2的CDE三題相同.每次比賽結(jié)束后Rating都會(huì)依據(jù)此前各個(gè)選手的Rating和公式重新計(jì)算.對(duì)于沒(méi)有參加過(guò)比賽的新用戶,在比賽后重新計(jì)算Rating的時(shí)候,他此前的Rating會(huì)被視為1500.
　　在比賽中,選手有2個(gè)小時(shí)的時(shí)間去解決5道題,而解決某題得到的分?jǐn)?shù)由該題當(dāng)前的分?jǐn)?shù)減去(不成功的提交次數(shù))*50,這里,某道題的分?jǐn)?shù)是由比賽開始時(shí)的分?jǐn)?shù)隨時(shí)間線性減少得到的.同時(shí),這里的“解決某道題”是指Pretest Passed,即,通過(guò)了一次僅含部分測(cè)試點(diǎn)的測(cè)評(píng),而最終決定是否得到這道題的分?jǐn)?shù),要看比賽結(jié)束后的統(tǒng)一測(cè)評(píng)(System Test),如果在這時(shí)沒(méi)有通過(guò),就稱FST(Failed System Test).在比賽中的提交可以看到在哪個(gè)測(cè)試點(diǎn)出了什么問(wèn)題(例如,僅一行WA on pretest 3).
　　同一個(gè)Div的選手將被劃分到若干個(gè)Room里,每個(gè)Room大概30位選手;當(dāng)某道題Pretest Passed之后,可以選擇鎖定(Lock)該題代碼,之后就可以查看同一個(gè)Room內(nèi)其他選手該題的代碼(當(dāng)然了,這也是已經(jīng)通過(guò)pretest的),并試圖找出其中的漏洞,自己出一個(gè)數(shù)據(jù)(可以手打,也可以提交數(shù)據(jù)生成器)讓這個(gè)代碼不能通過(guò),這就是Hack,有時(shí)也稱Challenge.一次成功的Hack可以得到100分,而如果沒(méi)有成功,將會(huì)被扣50分,分別被稱為(un)successful hacking attempt.
　　在比賽中,選手可以看到實(shí)時(shí)的排名(Standing),也可以選擇只看加了好友的選手的排名.此外,還可以看到某題有多少人通過(guò)的信息,這在某些情況下很有用.
關(guān)于比賽的事情大概就是這么多.cf題庫(kù)的所有題目都是在該平臺(tái)上舉辦過(guò)的比賽的賽題,盡管WJMZBMR曾經(jīng)表示由于出題人很雜cf的題目質(zhì)量參差不齊,但我個(gè)人認(rèn)為還是夠可以的,兩個(gè)小時(shí)五道題也確實(shí)很能讓人得到鍛煉.和Spoj形成鮮明對(duì)比的,cf的機(jī)子效率很不錯(cuò),所以很容易培養(yǎng)出STL依賴癥等等不良代碼習(xí)慣,應(yīng)當(dāng)引起足夠的注意.
　　在cf上做題的過(guò)程當(dāng)中如果遇到困難,首先可以看數(shù)據(jù).數(shù)據(jù)從某種程度上來(lái)說(shuō)是公開的,在提交記錄頁(yè)面可以看到所有你的程序運(yùn)行過(guò)的數(shù)據(jù),但是太大的數(shù)據(jù)也只會(huì)顯示前幾行,因此也不算完全公開.cf的測(cè)試數(shù)據(jù)筆數(shù)通常會(huì)讓習(xí)慣了10個(gè)點(diǎn)的人大吃一驚,一道題動(dòng)輒幾十個(gè)測(cè)試點(diǎn),甚至有的有200多筆.通常來(lái)說(shuō),前面大概5組是比賽時(shí)的Pretest,一般會(huì)盡可能的涵蓋各種情況,也有放個(gè)大數(shù)據(jù)卡TLE的;其后的數(shù)據(jù)規(guī)模遞增,但是最后幾組又不見(jiàn)得是極限數(shù)據(jù)——這是比賽時(shí)Hack的成果.Hack成功的數(shù)據(jù)會(huì)被追加到該題的測(cè)試數(shù)據(jù)當(dāng)中.
　　如果數(shù)據(jù)不能解決問(wèn)題,可以試圖去找題解.題目頁(yè)面的右下角會(huì)標(biāo)出它所屬的比賽的相關(guān)文檔,通常會(huì)有Announcement(賽前和賽中的公告,其中賽中的公告通常是明確題意之類),有些則會(huì)有Tutorial,這就是題解,順帶一提cf上另外一個(gè)表示題解的詞是Editorial.一次比賽的題解可能不是官方的,也可能不包含該次比賽全部的題目的,也有可能是用俄語(yǔ)寫的(前面提到過(guò)了,翻譯成英語(yǔ)就好),也有可能有好幾篇(這會(huì)以Tutorial #1,#2的形式標(biāo)識(shí)).
　　近期的比賽多半都有官方題解,以前的就不好說(shuō)了.這時(shí)候需要借助另外一個(gè)神器:神犇們的代碼.cf上普通題庫(kù)的所有的代碼都是公開的,并且支持按照提交先后(Judging Time),運(yùn)行時(shí)間(Execution Time)和代碼長(zhǎng)度(Solution Size)進(jìn)行排序.不僅僅是幫助做題,這個(gè)功能對(duì)于了解一道題的各種做法也是有好處的.
主要的東西就介紹完了.這里再補(bǔ)充一點(diǎn)一些零散的東西.
　　關(guān)于Rating的計(jì)算 : 這是一種類似Elo Rating的系統(tǒng),可以在cf的FAQ或Wiki百科找到更詳細(xì)的信息.
　　關(guān)于Contribution : 在用戶信息頁(yè)面會(huì)見(jiàn)到這個(gè)東西,它用來(lái)衡量一個(gè)用戶對(duì)cf的貢獻(xiàn)程度.這個(gè)數(shù)值取決于該用戶所寫的blog和他對(duì)其他的blog所作出的評(píng)論的“反響”.每個(gè)blog的下方和評(píng)論的旁邊都會(huì)有一個(gè)往上和往下的箭頭以及一個(gè)數(shù)字,表示你可以對(duì)他進(jìn)行好或者不好的評(píng)價(jià),而數(shù)字則顯示當(dāng)前已有的評(píng)價(jià),而這就是前面說(shuō)到的“反響”.點(diǎn)擊了往下的箭頭會(huì)讓這個(gè)數(shù)值-1,點(diǎn)擊了往上的箭頭則會(huì)+1或+2,這里+2的條件是你本身的contribution不低于+25.如果你打算做評(píng)論,請(qǐng)謹(jǐn)慎,因?yàn)樵谫N吧里很正常的回復(fù)可能會(huì)被認(rèn)為“沒(méi)意義”或者別的原因而反響很差(比如在比賽預(yù)告帖回復(fù)Good luck everyone之類的可以被-12),隨而contribution也會(huì)很難看.由于這樣的原因,你可以選擇完全可以無(wú)視這個(gè)數(shù)值.
　　關(guān)于GYM : 在gym里舉辦的比賽基本上是ACM/ICPC規(guī)則的,可以單干,也可以組隊(duì)(人數(shù)似乎沒(méi)有限制).gym的題目并不會(huì)在Problemset里顯示,提交之后也不能看到數(shù)據(jù)(和常規(guī)比賽時(shí)一樣,僅能看到一行TLE on test 137之類),不過(guò)在名字變紅[即(International) Grandmaster]之后選上Coach mode就可以看到數(shù)據(jù).gym里別人的代碼的公開性也服從前述規(guī)則.
關(guān)于Virtual Participant : 有時(shí)我們會(huì)在某條提交記錄的ID右上方看到一個(gè)小小的#號(hào)或者顯示一個(gè)時(shí)間,鼠標(biāo)移上去會(huì)出現(xiàn)Virtual Participant的字樣.正如其字面意思,這意味著這個(gè)用戶正在“虛擬”參加一場(chǎng)比賽.如果你虛擬地參加一場(chǎng)比賽,系統(tǒng)會(huì)在接下來(lái)的2小時(shí)內(nèi)(如果gym的話另當(dāng)別論)為你完全地模擬當(dāng)時(shí)的情境供你練習(xí)——包括Standing等等.
　　關(guān)于奇葩的測(cè)評(píng)結(jié)果 : 這包括Compilation failed,Denial of Judgement和Judgement Failed.在你確認(rèn)你的程序沒(méi)什么重大問(wèn)題之后,基本可以認(rèn)定這不是你的問(wèn)題而是系統(tǒng)出了點(diǎn)差錯(cuò).Judgement Failed通常會(huì)呈現(xiàn)爆發(fā)的樣子,一段時(shí)間內(nèi)幾頁(yè)都是,當(dāng)這種情況結(jié)束的時(shí)候就正常了;而Denial of Judgement僅會(huì)在某段時(shí)間內(nèi)在特定的題目發(fā)生,原因可能是數(shù)據(jù)損壞之類的,可能要等上個(gè)一兩天才能得到解決(也有可能在問(wèn)題解決后被自動(dòng)重新測(cè)評(píng));Compilation failed我還沒(méi)有見(jiàn)過(guò)...字面意思是編譯器不干活?
附 各個(gè)頭銜的Rating范圍和名字顏色:
[2600, inf) International Grandmaster 紅
[2200,2600) Grandmaster 紅
[2050,2200) International Master 黃
[1900,2050) Master 黃
[1700,1900) Candidate Master 紫
[1500,1700) Expert 藍(lán)
[1350,1500) Specialist 綠
[1200,1350) Pupil 綠
(-inf,1200) Newbie 灰