【打CF，學算法】關于codeforces的介紹

你應當知道的關于Codeforces的事情

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