2015年9月17日 星期四

舉辦 Codeforces Round #320 的紀事始末

  會想要舉辦這場 Codeforces,要從我在準備 SRM653 說起。

  SRM 的出題制度是這樣的:你必須先出好 Div.1的 Med 或 Hard 的題目敘述,然後交由 rng_58 審合,如果 rng_58 覺得 OK,那麼那有可能(只是有可能唷)再未來的某一天讓你的題目成為某場 SRM 的題目,並在比賽前5~14天左右,叫你生出 Div.2的題目以及 Div.1 Easy的題目,因為生出 Div.1 Easy 等級以下的題目被認為是簡單的事情。而在 SRM653 比賽前一個禮拜,我以前出的某些題被 rng_58 問願不願意拿來當 SRM653 的題目,對此深感興趣的我當然說 OK囉,於是 rng_58 便請我順便幫忙生個 Div.1 Easy 及 Div.2 所有題目。

  在試著生剩下的題目時,我邊看動畫邊想著要出什麼題,然後看到了動畫的片尾曲裡某個女孩在沙灘上走路,我就想著,在沙灘上走路應該會留下腳印是吧?而腳印我們可能只能分出左右腳,而無法分出一個腳印是誰踩的,我就想要藉此為靈感生出題目如下:有一群人在沙灘上走過,並留下腳印,每個人一定是左右腳輪流踩,請問至少有幾個人經過?

  稍微想了一下就發現,這應該可以輕鬆用 greedy 解出,於是就想把這題當作 Div. 1 Easy,但由於敝人英文薄弱,每次在生題目都會苦思許久,也常常會為了能讓我的破英文能夠把意思表達出來而稍微變動一下題目故事,最後生出來的題目變為:有好多人走過一條路並留下腳印,請問這些人的倒退走的步數總和至少有幾步?大家應該有發現,題目變成這樣後,根本意思變的完全部一樣了吧 XD

  編完題目後在思考題意變成這樣,原本的做法是否還是能產生對的答案呢?大概想了幾十分鐘,才證出答案會是一樣的!這時就覺得挺開心,覺得這應該能不止當做 Easy 的題目。

  後來拿這題和 rng_58 討論,但他覺得這題太 greedy 了,很容易讓人亂猜也不會證,就拿到 AC,這是他不樂見的。他的說法我也同意,而且這題還很可能被很多人用假解得到 AC ? 但我還是覺得這題不出出來好可惜喔,於是就想著,不如,在辦一場 CF 吧?可是辦 CF好麻煩喔 >_< 必須一口氣就準備好七題而且還要配合的好剛好能成為一場 CF的題組耶 > _ < 我覺得我已經沒什麼能力在出夠難且有趣的題目了啦!那怎麼辦呢 ... 只好把朋友也拖下水了!一切都是為了生出更有趣的比賽!

  於是就在 2015 年 4 月 1 日 我就問了 shik 和 tmt514 有沒有意願一起辦比賽,並且有沒有現存的好題,他們都答應了,並且 tmt514 同時丟出了一道題 (這場比賽的 Div.1 pF),我想了幾個小時都不會做,覺得這題可以當 Div.1 250 , 這是我又亂生了幾題簡單題,但後來因為接到了幫台灣清大辦某個比賽的 case, 就把這件事先擱一邊了。

  直到 7月16 號,台灣清大那場比賽結束不久後,我終於有興致回來搞這場 Codeforces Round 的出題作業,shik 這時丟給我了一題 (Div.1 C),當時我想了一下,就想到了可以用類似凸包的方式去解它,同時也覺得 code 好像很難寫,就覺得這題可以當 pC 吧? 並把原本腳印那題當 pD,再擠出剩下的簡單題就行了,要出簡單題,最簡單的方法就是設定某個經典的東西為主題然後隨便編個題目,若幾分鐘內就發現這個題目能做,而且不覺得無聊,那或許就可以拿來當題目了,其中 Div. 2 pB 是我從參加 Codechef 上的 SnackDown 時就聯想到的題目, Div. 1 A 是設定好 polyline 為主題,隨便聯想到的題目, Div.1 B 是設定好 or 運算為主題聯想到的題目, Div.1 D 則是設定好 LCS 為主題聯想到的題目。另外 Div.2 A的題目是 drazil出的題目被我討價還價後最後的樣子。 大家也許會困惑,為什麼總共有八題呢?主因是我對這些題目的難意度有點沒信心,在我心裡面所有題目要不是 Div.1 A以下,要不就是 Div.1 C 甚至是 D 以上,所以就想說反正難度並不是我說的算,一切就交由 Codeforces 的題目負責人 Zlobober 決定吧!讓他從這八題中選七題。並在 7 月 20 日,把這些題目寄出去。

  第一次收到回信是 8 月 1 日,Zlobober 要求我寄每題的解答給他,但是八月上半部我超忙的,先是去北京參加百度之星決賽,緊接著又跑去西安參加計蒜之道決賽,之後隔幾天又要去美國參加 Google Distributed Code Jam 的決賽,所以就回信說,最近兩個禮拜我很忙,沒有空,大概要兩個禮拜之後才有可能寄給他,但是這些比賽參加完後,整個累癱了,而且 DCJ竟然是最後一名真傷心...,唔唔真的覺得好累喔,想說乾脆 Codeforces Round 乾脆就放棄好了 >_<,反正原本很期待的人也只有我吧 >_<,還是先把自己變得更強在說 > _ <,這之後,我似乎過了十天的從早到晚都在解題的生活... ? 邊解題邊想著兵單到底什麼時候才會來...

  直到 9 月 2 日 Zlobober 敲了我 google hangout,我問還有沒有繼續辦比賽的意思?結果我瞬間輸給誘惑了 ... 於是就把題解弄一弄,並在隔天寄出。

  在弄題解的過程有一個插曲,我拜託 shik 和 tmt514寫他們自己的題目的題解,結果 shik給出的題解給我嚇傻了 =口= ,原來他那題有可以二分搜或三分搜的性質 ... 那樣的做法超好寫的@@ 如果我在比賽中一想到凸包的做法並決定寫凸包, coding 時間絕對是寫二分搜獲三分搜的人的好幾倍 ...

  但之後又沒下文了 ... 我繼續過著每天解題的生活 (?) ,直到 9 月 12 日,終於等到 Zlobober 正式和我討論題目了,順帶一題我寄給的的題目順序和出現在比賽的順序並不一樣,原本的順序是 2A 2B 1B 1A 1D 1C 1E 1F,而它對這些題目的初步感想如下:(以下是可能夾帶大量由於我的英文能力有限加上個人偏見的胡亂解讀?)

2A:就是個是合 Div2. 2A的不錯的題目 (其實他就只有說 it's nice. 而已 XD)

2B:若題目把過程在解釋得更清楚一點的話就OK。

1B:雖然我沒有想的太久,但我觧不出來,看來你給的解答還是不懂你的做法的正確性 @@

1A:OK,大概是個介於1A~1B的題目

1D:這題很危險,很容易誘惑人使用紙筆用分一些 case 的方式解它,而且它有很多 case,有點複雜,當然若像你的解達那樣去思考這題,將會變得很簡單很好 coding,可是要像你那樣來思考這題是需要經驗的。我覺得這題程度至少是 pC,甚至很偏難的 pC,但我也不想把它放在 pD,因為這並不是真的很複雜。

1C:對我來說這題還蠻簡單的,三分搜一下就解決了,而且coding時間很短。大概是 pB的程度。

1E:我可以用相當短的程式碼算出答案,但背後的邏輯卻是相當難的,我認為這題是所有題目理最難的。

1F:這題的題目還蠻有趣的,當我覺得這題沒有那麼難,比 1E 簡單,至少我在紙上畫一下就猜出答案了,雖然我沒有證出它的正確性。它用到了 kirchhoff's fomula,雖然我忘記了,但這只要 google 一下就能查到。

  由於我們是用 hangout 討論的,過程中我也有給些意見,例如說,我再次想辦法把 1B 的解答講給他聽懂。以及我告訴他 1C 我的直覺做法是凸包,若直覺想到的方法是這個方法的人,大概要寫好久?還有 1F實際上我想好幾個小時都沒想到 (也許是我沒有在紙上畫畫的關係...),以及我覺得 1E雖難證明可能有點難,但或許有不少人能用猜的猜到做法。過程中有些題目 Zlobober聽過我的說詞後也改口他對難度的判定...

  最後綜合了一些討論, Zlobober 對我說你的題目們再度讓我難以估計難度... 還是和上次一樣使用動態分數吧。並且八題可以都放上去,每個 Division個放六題,比賽時間設為兩個半小時。於是賽制就這麼定下來了。最後討論到舉辦比賽的時間問題,他問我,能在 15 號星期二前就把所有題目準備完嗎?我想了一下,距離現在還有三天,而且這幾天我的家人全部外出旅行完全沒有人有機會打擾到我,我就說 OK,於是比賽日期就決定辦在 15 號的隔天 16號星期三。

  說到這裡大家會發現,Codeforces 的在舉辦比賽的準備期其實蠻短的,而且出題者寫出解答和生出測資後, tester 只有一天的時間可以測,若出了什麼問題都要在一天內解決 ... 我上一場辦 CF round #292 時也是這樣 Orz

  12號當天我就先把 Div.2 A,B以及 Div1 A 的解答和測資都生完了,2A 時在沒啥好生的,我就放了做大的數和最小的數進去,再用手 random 幾個數字,以及一些二進為寫法長的比較漂亮的數如10101010... 之類的。 Div.2 B 測資也是令人覺得 random就夠強了,不過我還是生了一下二照某些做法,會需要花最久的iteration數的 case,這題我原本想要卡 O(n^3) 但是 Codeforces要求 Div.2 A~C必須讓 python code 也能過,於是就放棄了,並且乾脆讓 n只設為 400 (原本給的 proposal 是 500)。 Div.1 A倒是在生測資的時候發現...我的 code 和 Zlobober 的 code 都有 bug... (有些 case會除以 0),而且我原本給的 sample 不會測到這樣的 bug...,這下有趣了,要不要把個 bug 會錯的測資放進 pretest 裡呢~,這可是讓兩個人寫兩個人都錯一樣的地方的bug耶,不過我最後我覺得這畢竟是 Div.1 A,還是把它放進pretest裡好了?只可惜我沒有好心到把它放進 Sample 理 :P

  談到 Div.1 A 還有一件事:題解理說到 a-b的 case不會用到是在生測資的時候才發現的,我原本想說如果有人誤以為只要用到a-b或a+b的其中一種 case,一定要讓他 WA,結果卻發現... random生好幾組都生不出反例,這時覺得不對勁,稍為證一下就發現實際上只會有 a+b 的 case...

   13 號我生了  Div 1 B~E。B的測資我也不清楚要怎麼生,我大概預想了三個狀況,一個是他直接把 $x^k$ 乘再最大的數上,另一個是他使用O(n^2) 加 cut,也就是只拿最大的前 $5000$ 個數去乘 $x^k$,第三個是只考慮把 $x^k$ 乘再最高為是 $1$ 的那些數。最後,我只生了前兩個狀況會 fail的測資,第三個狀況我心想,會有人那麼機智嗎?畢竟有可能全部的數最高的 bit 都是 1啊?你何必多幾行 code 把他們 cut 掉呢?不過事後證實我錯了... 還是有人真的這樣做...(可參考此comment)。不過這些狀況,都是基於做法是在考慮直接把某個數乘以 $x^k$ 下可能會有的 bug或錯誤猜想。正式比賽後證實,我的思考還是有太大的侷限性了。

  Div.1 C 的測資我就考慮了一下,讓答案最大的 case 出現,以及把一些看起來比較漂亮的數列放進去 (如 0,1,0,1..震盪,或是等差數列),剩下的測資就 random。

  Div.1 D 更是直接 random,這題大概沒有什麼非 RE 的做法能過所有 random 測資但卻 WA在特殊測資上吧...?要特別記住的就是把字串長度等於 $1$ 的測資放進去而已,這題最終並沒有人 Fail System Test。

  Div.1 E 這題是寫 code投一次感到困難的題目,我原本以為很多個人的 case 很好處理 (最中的題目是所有腳印都是同一個人踩的,但原本的題目是有 $n$ 個人,每個人至少踩一個腳印,要求最少的 backward step,並構造出一種可能解),於是我就和 Zlobober 題一說把這題改成只有一個人,我並不希望我出的這場比賽裡有相較於整題思路比較不具思考難度的 dirty work。至於測資 ... 我實在不知道要怎麼生,就幾乎全部都亂生,以及加上一些長的比較漂亮的數列。由於想必這題會有很多人亂做,所以我也試著寫了一個亂猜的 greedy,然後發現這份 code 大概會 WA 兩成的測資,就覺得 random的測資應該還算夠強吧...?

  14 號 tmt514 寫了一份 pF 的 code,然後我就生了一些測資,這測資也是頗不知道怎麼生的,就想了三四種不同方式的 generator亂生,心裡想說這種題目重點只在於要生出答案不是 0的測資吧?

  生這題測資時也有一個差曲,有些測資我預期答案不是 $0$,但 tmt514 的 code 卻輸出 0,這讓我好困惑,我交叉看了我的 generator 以及 tmt514 的 code,花了好久時間才找到原因,做 Kirchhoff's theorem所需的矩陣大小,並不是直覺上的 201,而是 401,我覺得這也太tricky了,再寫這種難題的時候,這種小細節的思考很容易就會胡弄過去啊!可以想像,寫這題的人當中若使用陣列並認真估大小,大部分的人會估錯...

  在 15 號時,Zlobober看了我準備的所有東西並給了一些建議,而這些建議使得我接下來的四十幾個小時只睡了三個小時....

  乍看之下,我應該所有題目都弄得還 OK 了吧?是有什麼建議需要我花那麼多時間嗎?首先是,Div.1 pC ,對,就是賽後大家為浮點數炒得沸沸揚揚的那一題,我原本身的測資中忘記考慮一種極端測資,也就是答案是 $0$ 的 case,Zlobober 叫我生個這樣的測資,我生了幾組後發現,天啊... 我和Zlobober 的三分搜 code 在誤差限制 $1e^{-9}$ 下都不夠精確 (我們有用凸包解的 code 對照,這種方法精確度非常高),之後Zlobober把iteration 數提高,以及我把double改成long double後才 AC,也發現 binary search 的左右界設的不一樣會影響答案,這究竟是怎麼回事呢?到底要怎麼處理,經過了將近 10個小時和多人(Zlobober 以及tmt514,shik,drazil)討論,首先會發現,若誤差要求是 $1e^{-9}$ double的精確度本來就不構,因為我們是對 $x$ 做 binary search,但輸出的答案卻是把 x 代入某個 function 後的輸出,誤差又會在被放大好多倍。這是理論上 double 無法應付的精度,實際上之後我們又試著生了一些極端測資,使不同的五個人寫出的用 double 的 binary search 或 ternary search 的 code都 WA 掉了,因此可相信不管怎樣的code,只要我們放大量的極端測資都testcase裡幾乎會 fail system test。也就是說此題不存在使用 double 做二分或三分搜在誤差 $1e{-9}$ 的限制下能 AC 的方法。

  這時我們在兩個選項中做選擇:(1) 誤差設為 $1e^{-6}$ (2) 誤差設為 $1e^{-9}$。

  Zlobober原本對兩個選項都可以接受。而我們出題群大部分人傾向用 $1e^{-9}$,認為浮點數精度問題本來就是大家在思考時應該考慮的。就算double 沒有 AC 方法,那麼使用long double,再甚者使用 __float128 一定能AC (我是在這次討論裡才注意到 __float128這個東西 Orz),所以只要想好好考慮精度的人應該就會決定使用__float128。但我個人覺得,若真使用 $1e^{-9}$ 比賽時會發生什麼狀況呢?如果我們有把一些極端測資放在 pretest 裡,但我們在測試時就知道,根據你的寫法以及一些參數設定,並不是所有極端測資都會 WA 的平均來講大概只會 WA 五分之一的測資。如果我們只放一兩組測資在 pretest 裡,那我們頂多就只是造福了 2 至 4 成的人。我並不希望有一個運氣成分,況且因此 fail system test的人也不一定知道問題出在精度,或是知道要怎麼解決精度問題。若完全不放這樣的測資進 pretest 裡,那又會怎樣呢?測試者每個人看完題目都使用 double,可相信這樣將會使得最終 AC 的人只有不到 $5$ 趴吧?那這整場比賽會是如何呢?說不定會變成最終題分是 250-250-3000-2000-3000-3000 的比賽。總之,反正 code都是我在寫,測資都是我在生,最後我決定要用 $1e^{-6}$也沒有人有意見。但我知道,用 $1e^{-6}$ 絕對還是怨聲載道的,畢竟我測過大家寫的 code,雖然在 $1e^{-6}$ 下會 AC,但若設成 $1e^{-7}$大家都會WA掉的,可見這樣的精度依舊設的很緊,大家若用 double 但沒有使用足夠多的 iteration 數或沒好好思考經度問題都還是會WA掉, (有幾種大家常犯的毛病如:我們並不是要求 $x$ 的精度在 $1e^{-6}$,而是 Weakness 的精度,這會讓很多人估錯。或沒有好好估三分搜的 iterations 數 )。於是賽後我完全不想理那些討論精度的 comment ...,因為那是我們在出題目時就有想過的問題。希望大家經過這次比賽後能夠更仔細的思考輸出的精度是否足夠。

  這個問題解決後,Zlobober 拜託我在寫一份 pF 的 code,畢竟目前只有一份 AC code,於是我就開始寫了,我編寫邊回想 tmt514 的 code,寫到記算行列式值時,突然心有一陣涼意,因為我在寫交換兩個矩陣的 row 要把行列式結果乘上 $-1$,想起我沒印象在 tmt514 的 code 裡看到這樣的敘述,我寫完後趕緊測那測資互測兩份程式碼,結果我 random 生了幾十萬組測資結果都一樣,到底要怎麼辦 (註:在比賽開始兩個小時前,Input 並沒有要讀入 mod 的 $p$ 值,而是固定 $p = 1e^9 + 7$ )...我覺得這個 bug很大,而且會犯的人應該不少,應該要有測資能 catch 到這個 bug,而且就算我 random 出了一組測資能讓 tmt514 的 code WA 掉,並不代表所有寫錯這部份的人都能 WA 掉,因為可想見這題大家建出的矩陣很大的機率長的不一樣。我和大家討論一小段時間後,最終決定把題目改成把答案 mod 一個給定的質數 p,因為給定的 mod 數愈小,會讓這個 bug 影響到答案的機率提升 (大家可以思考看看為什麼)。做這個決定其實還蠻危險的,因為已經離比賽剩不到 90 分鐘 ...。最後我在比賽原訂的時間 12 分鐘前左右弄完。比賽時間會延期,很大的原因就是這件事,對不起我太懶惰了 >_< 沒有在更早之前就寫第二份預期能 AC 的 code,就沒有提早發現這件事了  > _ <,不過話說起來,都是我記憶力太好才有辦法三十幾個小時後還能憑空從記憶裡發現這個 Bug...,要不然反正給定的測資結果都是對的,賽中也沒有人 challenge,根本不會發生任合影響比賽結果的問題 (就結果論來說是這樣),我沒發現的話最中這將只是歷史上眾多不影響結果的錯誤之一而已。想反的我這樣的矩動還造成了一場悲劇...嗯,等等再說。

  比賽開始。一如預期 Div. 2 A瞬間就一堆人 AC 了。實際上 Codeforces 的 admin可以看到所有人的 code 是否通過原本就有的所有測資,這就是所謂的上帝視角?至於為什麼 System test 還是會那麼慢呢?大概就只是因為所有測資都會重測吧?至於為什麼要這麼做,我就不知道了 0.0,順帶一提,對於大家 hack 成功的測資,並不會自動加入,而是由 admin 看過後再決定要不要加入的。

  過了十幾分鐘,我們就可以看到 Div.1 A,B都有不少人 AC 了,同時也看到有不少人 WA,果真有不少人犯了我原本預想的 Bug,看到時難免會會心一笑。接著Div.1 pC 最早 AC 的是我們台大的學弟,我沒絕對沒有串通好唷 >_<,到了很久之後 Div.1 pD才開始有人 AC

  接著發現了一個驚人的事,我們看到有人用同一組測資 challenge 了五個人的 Div.1 pB,而且這五個人都會過 System Test,這絕對不是普通的在寫正解時寫出 bug 那麼簡單,一定是完全錯誤的做法造成的,這在比賽開始前對我們來說事難以想像的,雖然說 Zlobober 說他沒能在短時間想出解法,但我們其他人這題都是極短時間內就知道正確解法,完全沒有料到在賽中會有三分之一左右的人寫出同樣的方法...,這也說明大家都習慣把常見的演算法或 dp 模式,在不清楚正確性的情況下就值接套入寫 code 了,我相信很多人其實也無法說清楚為什麼把其中某個數乘以 $x^k$ 就能找到正確答案吧?畢竟這可是 Zlobober 沒有馬上想懂的東西呢。

  一個小時過去後,陸陸續續都有人上傳 pD 和 pE 了,pD 有過 pretest的人都有 AC,pE 則是有 1/5 左右的人是 WA的,但你仔細去看大家 code 就會發現,實際上正確的 code可能只有 1/10而已@@ 實際上 pE 的測資不夠強,最終也沒有改善,這是這場比賽最大的敗筆吧...

  在比賽剩不到五分鐘時終於有人傳 pF 了,他的 code 一看就很像對的,我們 Judge 們看到時都很興奮,畢竟我們在出題時還是都會希望所有題目都有人解出來。但很可惜,最後他WA在倒數幾筆測資,那是我更動題目後才新增的測資,並且他那個 bug只有在讀入的 P 很小的時候才真的是 Bug,也就是說若比賽前 90 分鐘我若沒更動 pF的題目,他就會 AC,他就會是這場比賽的第一名了!真是對不起他了....

  以後我還會再 Codeforces上出題嗎?未來的是真的是說不清啊... 希望我在當兵時可以每天想出一題 Codeforces 2000分以上難度的題目 XD 不過在 Codeforces上出題的 cost 真的好高喔... 薪水又少要做的事情又多,時程又很趕,Zlobober 是相信我所以每次都在比賽前一天才開始test嗎...還是每場比賽都是這樣?我覺得這很不健康啊?從我的出題經驗裡,往往在第三者 test 後都會冒出一堆問題啊... 當題目愈難愈不尋常的時候更是如此。

  下一次出題是...幫台大某校內賽出題嗎...?希望我的腦袋還有辦法擠出新的題目 >_<

P.S. 補記一件事:賽後發現有人說 Div.1 D 的題目和過去SRM的題目極其類似,一問之下,原來是 SRM 619 Hard,確實很相似呢... 可以不要每次都那麼打極我的信心嗎 >_<,為什麼那麼多次想出有意思些的比較難的題目都是有人出過的題目啊....

P.S.S.補記第二件事:賽後 Endagorion (就是我文中說的差點第一名的人) 分享了他 Div.1 pF 的 Bug,我發現我自己的 solution code也有同樣的 bug.... 只是沒有被現有的測資 catch 而已,所以現在的用來評測的 main solution是錯的 >_< (不過 tmt514 的 code 是對的 所以測資真的有誤的話我們在賽前會發現,但能不能在即時發現 bug就不知道了...)

P.S.S.S 突然想到,我只要把pE改乘每組測資有多組 query,總字串長度和不超過 $200000$之類的,測資就會足夠強了,賽前還是想的不夠多啊...