TLife (125) - Warsaw (World Final比賽手記)

真正比賽的一天,實際上比我想像中要來得冷靜。



##

一開始分題目,分給我的,看來都很難。印象中我收到的有F,C和I。很自然,先看F,比較易懂,看完,沒有想法,懷疑和Graph有關的題目,放在一旁。之後看C,題目有點複雜,算法也大概想到,但似乎有點麻煩,沒有想過要立即開始做。之後I也沒有怎樣看,只覺應該很難,便問有沒有其他題目。又看了E,很明顯的Graph,說給GG聽,似乎可以做到。

此時whh上了一條不知名的題目,我也沒有去管他,反正見到有人過了B,便拿來看看,很簡單的integration,而且不會出現precision error,但比較煩,便想叫whh做,但他又似乎不想做,唯有我去想。

在此之前,B,D和K都有人過了,看過一看D,沒有太大想法(雖然之前Topcoder有一條類似的,而我當時是想到做到的),唯有專心想B。以為whh會做3條其中一條,怎料是L,成為全場第一隊通過的,有人來拍照,我們也興奮了一陣子。我去上B,GG又上E,交替的上,不久過了B的sample,便知道應該會對,交了,成為第一個1AC。

E很快便做好,交上去,TLE,GG說了題目,我便第一時間想到IDS,但也是TLE。後來改了一改,WA,變做bitmask,TLE,很多很多的optimize都沒有用。我本來想幫他想想,但一時之間也沒有甚麼idea,又在想我的C,便沒有全力去幫他。

GG不久便想到D,見E稍為絕望,便去寫D,挺順利的,1AC,全因sample夠強,一開始也是錯了最後的一個case的。我繼續寫C,發現中間的DP有點問題,便問GG如何修正,此時whh想好了K,上了,但GG又要改E,我覺得過K的機會比opt到E的大,便叫GG先幫我。果然,不久之後,傳來好消息,又是1AC。

基本上我們都沒有怎樣研究我們的排名,只是看看那一題比較多人過。當GG寫好了那一段,才發現原來想的東西都一樣,結果只不過是我沒有去處理一個case。我再debug,再加上了那一個case,過了sample。交了一次,TLE,很快想到如何減時間,初時complexity竟是20C10 * 20^4,後來改做20C10 * 20^2,WA,發現一個index上的錯誤,再WA,再看一看code,很快便知道是一個小節上的問題,沒有達到題目要求,由<=改為==,AC。

此時whh已經全力幫GG,似乎想到好方法,但仍然有WA。GG則轉去想G,看到實則上為shortest path,問了剛做完題目的我,再補充了一下那個connected component的observation,便由GG去上機。之前GG也看過I,我說了一些observation,很明顯可以做到,只是細節處理比較麻煩,在只剩下不多的時間,基本上要放棄I。E的WA了數次以後,whh突然拋出一句,今次不可能WA,如果TLE,我就放棄了,否則便一定AC。果然,如他所料,AC了。這個是一個重要的強心針。

GG全力做G,我和whh便決定要開一條新題目。由於估計coding只剩下30-50分鐘,所以只可選一題少coding的題目。H和J不用考慮,沒有人過,且是極難的geom。A沒有人看過,但見有一隊過了,也是在考慮之列。我先看A,whh想F,很快便知道A不是容易,全力想F。

很快便有observation,只須試2^13的case,唯一問題是裏面如何計算答案。我從greedy的方向想,whh從flow的方向想。很快我們都想出來,只是聽起來whh的似乎較肯定,便用他的方法。G題TLE了一次,用暴力的optimization,竟然過了。GG立即上F,完全由我和whh去指示。後來寫好了,發現了一些case的問題,不斷的修改,終於compile到,但過不了sample,只剩5分鐘,極速加了connected component的改法,但原來再要分2個case,只剩1分鐘,決定放棄。

終於有機會看看scoreboard,數一數,交了7題的不多,似乎有機會拿奬牌。那時候,立志下來,稱讚了一會whh之後,scoreboard也開始judge了。就是要凝做那一種緊張的氣氛,見到Waterloo還有可能過我們的時候,也是有點緊張的。最後是出乎意料之外的銀牌!

喜出望外,卻也知道論實力我們怎樣也排不了第8,實在太多強隊了。可是,比賽就是有運氣成份,所以,立志也說得好,贏了不要太開心,輸了也不用太失望,能夠有機會測試自己的實力,已經是比賽最大的收獲了。

P.S. 原來D同 https://www.codeforces.com/contest/177/problem/G1 一模一樣,所以很多人都做到(後來Per說早應該看看是否有類似題目)
P.S.2 我所指果條Topcoder題目係 https://community.topcoder.com/stat?c=problem_statement&pm=11888&rd=14733
P.S.3 後來看F的solution,我們的做法是正確的,不過可能有corner case

##

回到酒店,第一時間,竟是去看看香港的人有甚麼反應,又給我們發現了一段「偷拍」放上Youtube的片段。之後便是去華沙大學的圖書館進行頒奬禮。

那圖書館也許是我見過最美的一個。被綠樹包圍,柱子又被綠色的藤蔓繞著,進去沒有所謂的書卷氣,反而是一種輕鬆的氣氛,這感覺實在很適合去讀書。正式進入會場,上了樓梯之後,便是四條很高很高的柱,每條柱的頂部都有一個銅像,雖然不知道是甚麼,卻叫人感到一股莊嚴。




燈光的佈置極漂亮,彷彿這些的籌備時間都用在這裏了,是國家級的招待。只見到處都已經坐滿了人,而台上也有一個管絃樂團的擺位,一定會是很大型的了。果然,由第一刻開始,便是華麗的舞蹈,與不同的頒奬儀式交替進行。

不得不提的是,我是極喜歡那民族舞的。很久沒有看過這一類的舞蹈,只見男男女女都穿上了波蘭的傳統服裝,然後便是大跳起來。除了那現場的音樂很好,以及本身的歌便是很有民族的特色,最令我另眼相看的,便是每一個跳舞的人,面上都帶著很甜的笑容,沒有以前看過某些強笑的感覺。當舞蹈完的一刻,他們的笑容,真的是發自內心,這一種對自己民族傳統藝術的自豪,恐怕很難在現今發達的國家找到。




當舞蹈完結,我已經用盡力去拍手,更令我驚訝的,是在比賽中優勝的那些隊伍,今次雖然得到奬,但更令我明白到他們背後的努力和付出,真的不是容易想像得到。他們無疑是大學生中最最最聰明的一撮人,卻仍然需要很多的努力才可以達到今天的成績,令我對他們又添上一層的敬佩。

頒奬禮很長很長,看一看時間,原來已經3小時,還沒有吃過晚餐,卻又期待著那神秘的活動。公佈了,原來是Hulakula,更是正正在圖書館的下面!這個集保齡球、桌球、遊戲機、酒吧於一身的大型娛樂場所,竟然就是在圖書館的正下方!


我們也沒有太多的玩,只是填飽了我們餓極的肚子,再玩了桌球和足球機,談了一會天,便已經很晚了。坐了最後一班12時半的車回去酒店,可是仍未覺累,想要再談一談,稍為消化今天不可思義的事實,加上那喜出望外的情緒。


5月17日,又是挪威的國慶,只可以說,這叫雙喜臨門。