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$之類的,測資就會足夠強了,賽前還是想的不夠多啊...

2015年6月19日 星期五

2015 Distributed Code Jam Online Round 參賽紀錄

對不起又是流水帳(感覺似乎有人在抱怨... ?),不喜歡的話就不要看嘛 >_<

  Distributed Code Jam 是 Google 今年第一次舉辦,原本我都沒有特別注意這項比賽,甚至到了我進入 Round 3 以後,我才知道原來要進入 Round 3 才有資格參加,更甚者,直到剩不到一周的 Practice Round 我才知道 DCJ 的比賽內容是什麼 @@ 看來是在比我在大學時修的平行程式的東西啊... 嘛...就我當初修課的印象,程式因為平行而增加的效率也挺有限的,最基礎的平行方式就是把問題拆成可以分開計算的好幾個子問題,讓每個 Node 去各別處理這些子問題,除此之外也沒其它招了吧?

  姑且還是練了一下 Practice Round 的一些題目,Practice Round 題目還真多? pB 就只是普通的分塊,我試著寫了一下,唔... 要寫之前得先下載它提供的 tool 嘛... 我現在習慣使用的作業系統是 windows 7,並沒有裝 Python 等工具,唔唔唔好麻煩喔 >_< 我最討厭研究怎麼安裝東西了...  最後決定使用 pietty 連線到學校的工作站,並且使用 FileZilla 在 local 端以及工作站間傳送檔案... ,對不起我這種作業方式一點都不像是資工系出身的人 >_< 但是我真的不想為了不過三個小時的比賽認真花時間去研究要怎麼比才會比較有效率...

  在學校的工作站上作業起來就簡單多了,程式寫完就只要輸入官網上提供的指令救可以執行了,唉不對...還得改一下權限才行 @@ 總之 pB 並沒有太花時間的救完成了。

  接著看 Practice Round 的 pC,題目如下:給 $n$ 個數,請問是否存在某個數出現次數過半?

  這如果在一般的演算法競賽理出現這就是個簡單題,開個 map 紀錄救行了,但是啊,在這題你光是讀 input 時間就超過了!(題目有清楚告訴你讀完所有 input 需要花多久時間)所以 input 一定得由所有 node 分別讀進來,唔...讀進來然後要在把所有訊息合併嘛?可是每個 Node 可使用的記憶體諒也有限制,也不可能把所有 input 都 send 到同一個 node 裡,於是在稍微想一下後發現,若存在一個出現次數過半的數字,那它一定在至少一個 Node 理面出現次數也過半,所以我們只要去檢驗每個 Node 出現最多次的數是否維答案即可。於是我就把這題的 code 也寫了。但後來發現,每個 Node 呼叫 send 這個 function的次數不能太多次,但我在寫 code 時沒注意到這件事,於是大測資 Judge 後就炸了...

  之後在看了 Practice Round pD 的題目:數字 $1 \sim N$ 以某種順序維成一圈,給你兩個 function call 分別能得知某個數字的左邊是哪個數字,以及右邊是哪個數字,請根據這兩個 function來決定 1 和 0 的相對位置。

   這題我想了些許時間都不之到要怎麼作,總覺得... 只能 random 選 和 Node 數量一樣的數字們然後交給每個 Node 去跑,但真的是這樣嘛@@最後我就喇塞只用一個 Node 去處理整個問題,然後 pass 了小測資,大測資也隨手傳了上去, Judge 後理所當然獲得了 TLE。事後看了一下別人的 code,似乎真的是使用 random 的方式解這題@@

  寫完這三題,還剩下最後一題,但我覺得我對 api 已經熟悉的差不多了,所以就懶得在做下去了...最後一題至今都還不知道題目是什麼 :P

  來到正式 Online Round 的當天,也就是證常的 GCJ Round 3 的隔天,嗚嗚嗚 GCJ 昨天比的好慘,開場看的第一題就掛蛋了,今天比得怎樣都無所謂了啦,反正這個 DCJ 本來就只是個類似於興節目/表演賽之類的東西吧?決賽入取人數只有 10 人,第一名獎金只有 GCJ 的五分之一,規模小了好多,我把 DCJ 說成這樣那為什麼我還要比呢?我就是喜歡參加比賽不行嘛 >_<

  比賽開始。有四題,題分分別是 8、22、32、38,小測資的題目則分別只有1、2、2、1,比賽時間有三個小時是吧... 第一題應該是真的相當簡單吧?前十名的門檻會在哪呢?最簡單的 pB 肯定是得 AC的吧 ( 題號是從 pB 開始 @@)? 扣除這一題後,認兩題的題分總合都高於任一題的題分,所以要先猜門檻會是幾題大測資,應該不可能門檻是滿分吧 XD 那門檻會是兩題嗎?若門檻是兩題,我想我是一定沒機會的,在時間內我大概只能處理完一題?就算門檻是兩題好了,那應該也會是前兩題吧?以一個第一次半的比賽來說,應該會確保最後一提足夠難。所以若要寫兩題,應該要挑 pC 和 pD,但若門檻是一題呢?挑 pC 應該沒望吧?pE 對我來說可能太難了也不足以考慮,所以說,若目標仍放在進決賽的話,無論如何我都得做出 pD,來不如開場就先看 pD 吧!

  pD 題目如下:有 $N$ 張卡片,任兩張卡片都有固定的勝負關係,請把這 $N$ 張卡片分成非空的兩組 A和 B,使得 A 組的任一張卡片全輸給 B 組的任一張卡片,並且 B 組的卡片張數要盡量多。

  由於我擁有 flow 腦,所以我第一個思考方向就飄往 min-cut 了... 但是我想不到什麼好做法,甚至連是否真的存在 min-cut 的方式解這題都不知道,想了將近 20 分鐘左右以經有些許人 AC 了 pB,所以我就決定先回來把 pB 刷一下。 pB題目是:已知一個數列每個數原本的位置和自己已排序好的位置相差不超過 $D$ ($D \leq 10^6$)請輸出此數列排序後的 hash 值。這題我讀完題就知道怎麼做了,若有 K個 Node,就把序列切成 $K$ 段,第 $i$ 個 Node 就把第 $i-1, i, i +1$三段的數一起排序之類的。總之這題我沒有花太久時間救處理完了。 submit 後比賽還剩下 2時 23分。

  寫完 pB 後我決定還是先看一下 pC的題目,和 Deadlock 有關啊...我和系程最不熟了我可以直接跳過這題嗎 >_< 然後我回答自己:就跳過吧。

  於是按照原本的策略繼續想 pD,先把 flow min-cut 什麼的先從腦海裡撇掉,都想了那麼久了還是沒想到什麼,那應該不是 flow 題吧@@ 改從簡單的 case 想:如果已知 A 組有某些數,那會發生什麼事呢?如果 A組已經有第 $x$ 張卡,那麼所有 $x$ 會贏的卡片也得在 A 組!於是每新加入一些卡片時就可以再根據新加入的卡片決定哪些卡片還得加入!直到沒有必要再加入卡片時,這些 A 組的卡片就是再包含 x 卡片下的最小集合!所以枚舉一剛開始 A 組至少有哪張卡片,就可以搜出 B 組的最大 size,這樣的話複雜度是 $O(N^3)$,要平行的話也很好平行,A組不同的出始卡片交給不同的 Node 去執行就好了。但是這個做法並無法 AC 大測資,因為此做法每個 Node還是得讀入所有 input,但大測資光讀入就 TLE 啦!但我還是決定先快速的把小測資 AC一下。

  小測資 AC 後,比賽剛好勝兩個小時,我依然繼續思考 pD 的大測資要怎麼解決,過了幾十分鐘,我終於意識到這題根本就是 SCC 問題 = =,當下覺得好蠢啊.. 在一般的演算法比賽我不會花那麼久時間才注意到它只是 SCC 吧?把它變成 SCC 問題後,平行前的複雜度就降到 O(N^2) 了,但 SCC 要怎麼平行呢@@又卡住了 Orz

  不對,光是 SCC 還不足以展現這題的所有 feature,並沒有用到競賽圖的性質,一個競賽圖的 SCC會長怎樣呢?SCC縮點後會長成一個 path!我們只要找出此SCC的最前端的強聯通元件的 size,就能解出這題了!也就是說... 我們要找出dfs 離開所有點的順序?若能找到一條通過所有點的 path 的話事情就好辦了... 但這樣的 path 有那麼好找嗎?或者是說,這樣的 path 一定存在嗎? (此時完全忘記以前根本就有看過找出競賽圖上通過所有點的 path 的演算法....) 不不不要再深入的想下去,認真說起來,就算找到path還是得讀入很多邊,很麻煩的,有沒有什麼可以不每個Node都只讀完某些點的所有連出去的邊的方法呢?只讀完連出去的所有邊我們能獲得什麼資訊?我們能知道每個點的 out degree!out degree 在這個問題有什麼作用?B組的所有點都會連到 A組,所以B組的所有點的 degree嚴格大於 A 組所有的點的 degree!

  總覺得我快要接進答案了 >_< 在繼續絞盡腦汁吧 >_< 也就是說若把所有點按照 outdegree 排序,A、B組的分法一定會恰巧把此序列切兩半?所以如果我們已知 A 組有某個degree為 $v$ 的點,那所有其它 degree 小於 $v$ 的點也一定在 A 組?如果一個點 $x$ 在 A 組,它所有憐到的點也會在 A 組,但我們就只要關注 $x$ 連到的點中 degree最大的那個點就好了!?如此一來若點 $x$ 在 A 組,$x$ 連到的點 degree 最大的是 $v_x$,那麼所有degree小於 $v_x$的也必須在 A 組!於是我只要知道每個點的 degree,和每個點所連到的點中最大的 degree,就可以解這題了!

  接著是思考要怎麼平行,其實也沒有什麼好思考的啦,就每個 node 各字計算完自己所分配到的點的 out degree,在把這些資訊互相傳給所有 node,每個 node 再計算所有點連到的點中最大的 out degree,然後再把這些資訊都傳給最後一個 node,剩下的事情就交給最後一個 node 做。

  我在比賽開始後 2 時 19 分左右寫完大測資,測了一下 Sample 並修了一些 bug 後 AC  sample 了,於是我就把它 submit上去,同時我也順手把新的 code 傳上小測資,保險一下確認是否能 AC 小測資,但是,兩分鐘過去 judge的結果傳回來了,我竟然 WA 掉了!?WHY !!!

  我在認真重測一次我的 code,然後發現....我的 code 每次執行結果可能不一樣 = = 這世在搞什麼@@ nodes 間傳遞訊息出了問題?我對 google 提供的 api 還理解有誤?於是我又花了將近 20 分鐘把 code 改成我比較肯定的寫法,多測幾次每次結果都一樣後才 submit,也順手再傳一次小測資,這次兩分鐘後得到的結果是 AC,那大測資應該也沒問題了吧@@。

  比賽只剩下 23 分鐘,我的名次好後面... 六十幾名的樣子?看來進前十是沒望了吧?勝下這點時間我還能做什麼嗎?寫 pE小測資?還是寫 pC 小測資? pE小測資分數比較低,而且我連題目都還沒看,所以還是寫 pC 小測資得得分期望值比較高?但... pC 小測資要怎麼做呢@@

  雖然之前已經讀了題目,但還沒認真想過,乍看之下覺得有點難耶?但仔細想過後發現就只是個 dp 而已 0.0,於是我就很拼命的寫 code,在剩下五分鐘的時候把 code 寫完,但我並沒有那麼神的一次就把Sample AC。

  剩下的時間我就邊 printf 中間過程邊修正一些邊界加減一的 code,在剩下一分鐘時總算把 Sample 1 AC了。此時我另外兩個 Sample 都還沒下載下來傳到工作站上 (在強調一次,我是使用我的筆電,作業系統是 windows,使用pietty 連工作站用 vim 寫 code,檔案是用 FileZilla 互傳) ,在測完剩下兩個Sample可能就來不及 submit了 @@但更重要的是:若我真的測出 bug ,我幾乎沒有時間修正 bug後測試在上傳吧...?所以我就直接 submit 上去了 >_< submit 時間是比賽結束前 42 秒。

  在比賽結束過後一分鐘左右我得到 judge結果,我竟然  AC 了!!! 好感動喔 >_<,雖然 AC了,但我的排名仍就是 49 名這種怎麼看到沒機會 Judge 後前進到前十名的名次,呵呵呵,但我已經盡力了吧 >__< 在最後 1 分鐘內 AC題目耶 >_< 雖然只是小測資而已 >_< 這時系統發出公告說:大概兩三個小時後才會公佈 judge 結果。

  我就在電腦前枯等了兩個小時(?) 看了移下大家在 Codeforces 上的討論,原來 pD 只需要每個點的 out degree 資訊就得到答案啊... 所以我求出每個點連到的所有點的最大 out degree 只是多此一舉嘛 OAQ 修練還不夠啊 >_<

  這兩個小時左右我大概每幾分鐘就去 score board 按 F5一次,某次按的時候看到分數出來了!馬上瞄郭去前幾名,咦咦咦第一名竟然沒有出破台!?哇 shik 第三名耶!那我呢...於是我把頁面拉到最下面(因為 code jam若該使用者沒有出現在該頁,就會把該使用者放在最前面或最後面),咦?為什麼沒看到我?我在仔細看移下前三十名的頁面...咦咦咦咦咦咦咦咦咦咦咦咦咦咦咦咦咦咦!???????????????????騙人的吧我第十名?咦咦咦咦咦咦???四十九名 judeg 後變成第十名究竟是發生了什麼事 >_< 嗚嗚我腦袋當機了 >_<這是整人計畫吧,過一個禮拜後我就會收到:對不起我們不小心把你的 code judge 錯誤了的通知吧 >_<啊哈哈哈哈 ....

  四天過後 Final 的邀請信正式寄到了,看來這是真的 0.0 嗚嗚嗚獲得參加 DCJ 的 final資格一點也不會開心啦 >_< 我真正想參加的是普通的 Algorithm Round 的 final 啊 >_< 嗚嗚嗚嗚

2015年6月18日 星期四

2015 Google Code Jam Round 3 參賽紀錄

  這已經是我第七年參加 Code Jam了,並且是連續第五年進入 Round 3,雖然乍看之下我可以很穩定的進入 Round 3,但離進入 Onsite Round 還是差好遠啊... 好似已到達了自己的極限,難道沒有辦法有哪一年來正正常常的去一次 GCJ 或 TCO 的 Onsite Final 嗎 >_< 像去年那樣因為出很多SRM題而被邀去現場的機會沒有也沒差啦 >_< 一直以來的夢想都是身為參賽者好好的去現場比賽,而不是只是去觀戰啦 >_< 好啦碎碎念到此... R3 就要開始了。

  看了一下今年題數和每題題分,今年總共有五題!?以前從來沒有那麼多題過吧!(事後證實這是我開始參加GCJ以來頭一次,以前都只有四題) 題分總和依序是 12、13、23、25、27。這是有兩題水題,讓基本分提高的意思嗎?看來前兩題是一定要得分了,於是我從第一題開始看。

  第一題是給一個 Rooted Tree,每個 Node 都有一個值,我們要找出盡量多的與 Root 連通的 Node,使得這些 Node上的值最大與最小的差不超過 D。數據是使用 Random Seed 產生的,小測資 $N \leq 1000$、大測資 $N \leq 10^6$ ,大測資 $N$ 那麼大啊... ,看來若要使用 dfs 要小心了 (有記得之前 Facebook Hacker Cup 的教訓)。

  小測資讀完題就知道怎麼做了,枚舉所有被選的 Node 的可能區間,從 root 去 dfs 看看最深能到哪,並把走過的點都選起來。大測資的話.... 嗯... 動態樹可以解決吧...? 可是我不會動態樹,並且也沒有動態樹模板 OAQ 但我還蠻相信這題有很簡單的作法的,於是繼續想下去,是說 ... 這真的事最簡單的一題嗎 >_< 這也太難了吧!!!以前的 GCJ 每個 Round 的最簡單一題我幾乎都能看到就知道怎麼做吧 @@

  十分鐘過去,終於有第一個人傳了 pA 大小測資,是 在 IOI 勝過 tourist 的昔日最強中國高中生 WJMZBMR m(_ _)m,唔唔唔,看來至少這題在 coding 速度而言在想下去投資報酬率是 OK 的吧?想到了應該能很快寫完。

  嗯... 這題八成還是要枚舉過所有可能區間,重點就是當枚舉某個區間時,匯有某些 subtree 的點會全不排除在外,也就是要知道每個點在什麼時候會被當成 subtree 的 root,一個點要被當成 subtree 的 root,代表他的所有祖先都有被選到,也就代表該點的值,要不是筆所有祖先的值都還小,就是比所有祖先的值都還大!嗯!這樣子再下去就能做出來的感覺!於是我決定值接開始寫 code了,邊寫邊想,並且先順手寫了一個 $O(N^2)$ 的 code 來作樸素對拍。

  大概三十多方鐘時我把能處理大測資的 code 也寫完了,但是對了一下小測資的答案和 $O(N^2)$ 的方法不一樣 OAQ Why OAQ 於是我開始漫長的 debug,時間消耗的很快,比賽已經經過了一個小時,我仍不知道我的 code 錯在哪。

  唔唔不行啦 OAQ 比賽只剩下一個半小時,而我就只為了這僅僅的 9pt 卡在這,這不是明擺著沒救了嗎?於是我捨棄了想找出 Bug 的心情,決定先搶搶其它題小測資的分數,順勢看看有否可以有所作為的題目。看了一下 score board, pD 的小測資應該是其它所有題目最簡單的吧?

  讀題...讀題...讀題... (卡住的狀態)。可惡啊,是因為前一個小時比不好太焦慮了嗎?為什麼 pD 最後關於符合條件的答案時要選擇哪組答案輸出的條件我怎麼反覆看幾次都還是看不懂 @@ 這題不過就是那個有n個數,給任兩個數得和的 set,還原這 n 個數的變型吧?感覺作法就應該會差不多嘛。看了一下小測資的條件:所有數都非負。在這個條件下肯定是唯一解,所以那個多組符合的答案要優先輸出什麼就不必管了 >_<,所以就快速把小測資 AC 掉。

  已過 1 小時 17 分。AC 掉 pD 的小測資後,由於還是不懂多組答案要優先輸出什麼,所以就決定先捨棄大測資,去看 pB。讀懂並想了一下後 ... 唔...感覺上小測資沒有比較簡單的方法啊?雖然我想到了一個作法,可是這個做法應該並不簡單耶...? 唉唉唉不對啦,這個作法連大測資都可以在時間內跑完啊 = =,於是這題就直接寫大測資了,邊界加減一的地方稍微卡了一下,但還算蠻順利的就 AC 了小測資,這題小測資過了感覺上沒道理不過大測資,就直接傳了。

  已過 1 小時 40 分。若有心還想進 final 的話... 我現在應該要...唔怎麼想都覺得沒救啦 >_< 從 score board 看來,A、B、D三題都 AC的人將會滿街都是,而在我 pA 沒有大測資的分數情況下,一定得靠 C 或 E來追分吧?稍微看了一下 C,感覺題目好常似乎會不好懂 0.0,於是反回看 pC。

       pC一臉就 O(N^3) dp 樣吧?可是...可是...他的順需要怎麼排?想必不能值接按照最初的座標順序排呀,那按照速度關係排呢?唔...感覺上不好想 or 要想清楚不簡單耶 ...,那就還是先把小測資水一下吧。

  小測資 $N \leq 25$,第一個閃過去的作法就是 O(N^2 * 2^N) dp,但 N 高達25耶 ...,我沒把握四分鐘跑的完,於是再多想一下,嗯...枚舉每追到一個寵物後,下一步要往左追還是往右追,這樣的話就是 O(N * C(N,N/2)),這個複雜度就很 OK 了!之後順利的把 AC 小測資 AC了。
  比賽經過 2小時 4 分鐘,還剩下 26 分鐘, C 和 D 的大測資感覺上都不太能在剩下的時間處理,而下就算處理完得分也不夠高,不足以逆轉結果。最後能拼的就是在剩下時間把 pE 小測資連同大測資一併解出了吧 OAQ。

  又經過了十分鐘,我還是沒有把 pE 題目看懂 OAQ 看來這場已經註定沒救了啦 OAQ 就算大家大測資都 fail,我小測資也沒有寫的比別人快啊!剩下 15 分鐘我還能做什麼呢?

  雖然心以死,但是我還是盡可能的利用剩下時間吧,回去 de pA 的 bug。在比賽剩五分鐘的時候發現我哪裡想錯了,而且只是發現哪裡"想錯",並還沒想到要怎麼改才是"對的",五分鐘覺對不夠用了啦!

  比賽結束,小月(Kirino)排在第 123名 (其實我覺的沒進 final 的話第幾名都不是很重要,因為我只要使用快速讀完所有題目並把所有看得懂題目的小測資都先做,名次一定不低啊?),結束了今年度的所有賽事(雖然 TCO 今年只取 12 個...我覺得值接認命去當兵吧 0.0),今年也是一事無成啊 OAQ

        恭喜皮皮 (peter50216) 總算是進到 GCJ 的 final,過去好多年雖然皮皮都在 Round 2表現超好,可是他在 Round 3都非常可惜 >_< 也恭喜新竹實驗中學的 betaveros ,在高中就進到 top 25超厲害的 >_<,還有凱琪也排在第三十名,之前有候補到 30 名以後,今年前 25 名也有好多無法去 final 的未滿 18 歲的人,說不定有機會候補上>_<

唔唔後年再加油吧 >_<

2015年6月2日 星期二

BeverageCup2ChallengeProblems



原始題目連結

好讀gitbook版

E - Kirino in Google Code Jam

中文題目

桐乃最喜歡哥哥了!現在她的哥哥為了專心準備大學聯考而搬出去一個人住,桐乃為了慰勞哥哥所以每天幫哥哥做早餐!今天 (2015/4/8) 桐乃和哥哥約好早上十點要送早餐過去,可是一早醒來卻發現早上 9:00 ~ 11:30 是 Google Code Jam 的 Round 1A,好在這個 Round 的題目對桐乃來說並不太難,她在三十分鐘左右就完成了所有題目。但要上傳答案前卻發現有一些測試資料能讓她的程式碼 WA 掉,但桐乃一時間不知道該如何解決這個 Bug,桐乃心想:「啊啊啊算了啦,就放它去吧,哥哥比較重要!我就直接上傳並趕緊幫哥哥做早餐!」於是桐乃如期送早餐去給哥哥了。
送完早餐回到家後,比賽已經結束了,桐乃發現她所有上傳的答案都被評為正確!?這時她傻笑的說:「嘿嘿嘿~這一定是我對哥哥的愛所賜的祝福吧 :D」

從這個故事我們可以注意到,要生測資實屬不易,實際上能讓桐乃 WA 掉的測資,可以讓不少人的 code 都 WA 掉,若比賽的正式測資存在這樣的測資的話,比賽結將會大大的不同吧?
現在問題來了,你能夠生出讓桐乃該題 WA 掉的測資嗎?
要看該題題目敘述請點這 ( Problem C Logging )
要找到桐乃(Kirino)的程式碼請點這

簡化題意

請找到一組能讓 2015 年 Google Code Jam Round 1A 第三名第三題的 Code WA 的測資。

原題解答

在解這題之前請先了解原題的做法,可參考 官方題解jo4 的 BlogMorris 的 Blog
P.S. 我出這題的靈感如下:某天我看到 jo4 的 Blog 題到我的 Code,我就感到非常慌張,因為我不確定我的 code 中 EPS 值是否恰當,深怕其他人看到我的 code 會誤以為只要為 就夠了,仔細研究一下就發現我 EPS 真的設太大了…

題解

要生出讓該 code WA 掉的測資,首先,你要知道 Bug 在哪。但這份程式碼若只考慮它的邏輯正確性,大概是找不出任何 Bug 吧?若非邏輯錯誤,Bug 會是在哪呢?答案是浮點數的精確度不足。該份 code 的浮點數誤差(EPS)使用的數值為 ,但在本題的數據範圍下,這樣的數值並不夠小,有機會產生誤判。
以下為導致 WA 的程式碼區塊:
for(int j=0;j<vn*2;j++){ // 原code這個for迴圈是使用Macro
    while(v[ll]+PI+1e-12<v[j])ll++;
    if(j>=vn)ma=max(ma,j-ll+1);
}
在 while 迴圈裡想要判斷是否 v[ll] + PI < v[j],因為浮點數的運算有機會產生非常小的誤差,使得運算的結果比真實數值還小,於是通常我們會額外加一個稍為比電腦的計算誤差大一點的數值 來避免誤判,但 若設太大,就會有機會使得原本不等式會成立卻變成不成立了。而我們要讓這份程式碼 WA 掉,至少要先找出什麼時候會不等式本該成立卻變成不成立。這這個問題可根據 v[ll]v[j] 產生的方法追本溯源變為尋找平面上夾角介於 之間的三個整數座標點
現在把此問題轉為數學式:請找出兩個整數座標的向量 ,使得這兩個向量夾角 滿足
很接近 的夾角對大家來說可能比較難想像,那我們把向量 反向,於是所求也可想像成 的夾角必須小於
現在我們就來想想,平面上給定座標範圍最接近的兩個夾角可以多小?這個問題在 Codefoces 的 Blog 上有某人給了解答。但我用我自己的方法來解釋,因為兩向量夾角 很小時,擁有公式 ,其中分子 由於座標都是整數又非零,所以最小的可能值為 ,而分母最大的可能情形為在限制範圍內最遠的兩個點座標距離平方,也就是 ,於是我們就能估出任兩個不同方向的最小夾角至少為 。哇!!!原來有辦法估出那麼精準的下界!有沒有很驚訝呢?(小月自己發現這件事時是非常驚訝啦!因為類似題目見了超多次,我都是隨便使用一個 EPS 值,從沒好好估過,經過這次經驗以後就知道要怎麼估了。)
但只是估出下界還不足以解出這題,現在我們不是要解出原題,而是要構造一組極限的測試資料。這時我們就要利用一個簡單的恆等式: 而構造出三個座標點 用電腦算一下這三個點最小的夾角是 ,和我們估出來的下界非常接近吧!但實際上,我們要找的是接近 的角度而不是接近 的角度,這樣的話用類似方法構造出來的三個點應該會是 其夾角和 的差距約為 ,仍舊比 Kirino 所設的 EPS 還小。
找出很接近 的角後我們還差一步,雖然我們已經讓 while 迴圈判斷錯誤,但若只有三個頂點, Kirino 的 Code 無論如何都還是能跑出正確答案,你至少要再加一個頂點才能讓此 Bug 產生對答案的副作用,而這最後這一步就留給大家自由發揮吧~
順帶一題,小月在測試的時候是生了一個 的答案,而至今為止 AC 的四個人有三個人八成也是用類似方法構造出了 的答案,而還有另一個參賽者採取完全不同的策略解這題:隨機生出大量的點來尋找夾角超小的頂點們,在想辦法用他們找到一組能使 Kirino WA 掉的測試資料,詳情請參考該參賽者(Morris)的 Blog

F - No challenge No life

題解

這題我想是沒啥特別的地方,我只是想藉由這題告訴大家,不要太相信網路上所看見的題解或 code,據我經驗,網路上的題解及 code 有誤或複雜度來亂的情況非常多,高達一成以上吧?(亂估 XD) 也請不要太相信小月寫的題解們,請務必好好自己想過 >_<
想要真正的題解,請參考 Morris 的 Blog

題目由來

原本這個quota是要出另外一題計算幾合的,但那題正解太難了,我不會做,之後的某天… Morris大大敲了小月…
conversation

2015年5月31日 星期日

2015 Google Code Jam Round 2 參賽紀錄

  這是我打 Code Jam 的第七年了,至從參加的第三年打進 Round 3 以後,已經連續四年都有打進 Round 3,但也都在 Round 3 止步。而今年,我差點以為我在 Round 2 就要結束了。

  這場我按照順序開題,先看了第一題,題目有點長,嗯...其實向來 Code Jam 題目都很長,所以這題算短的吧 Orz,理解題意後瞬間理解這題的解法,只要 check 每個 arrow 的四個方向是否至少有一個方向也有 arrow 就行了。馬上寫完了 code, 沒有 bug Sample 一次 AC,我要不要仔細重新檢查一次 code 呢?但是 Round 2 開始 若不是拼全部小測資,penalty 並不重要,所以我就直接下載 small 的測資了。 small 的測資 correct 以後,幾乎可以相信我的 code 沒有 bug ( 除非我耍蠢陣列開太小...?) 於是我就直接下在大測資了。寫完第一題時我排第 29 名,台灣比我快上傳的只有皮皮 (peter50216) 和 shik。

  接著看 pB,乍看之下就只是個特殊的線性規劃題,這時我心裡想:這題該不會去抄個 simplex 的 codebook 就能 AC了吧... ? 但我還是乖乖走正道好了,出題者應該不希望我們使用普通的線性規劃 tool (賽後證實有人是使用 simplex AC 的)。這次我學乖了馬上在紙上列出式子,線性規劃題往往可以轉成網路流問題或是計算幾何問題,但這題的式子看起來比較向計算幾何,直覺的想法是:先使用 binary search,然後再判斷某些係數在時數區間的二維向量的線性組合是否可以組成特定向量。似乎就只是個經點問題,但我對解法沒有印象。我先想想兩個向量的 case,感覺上挺簡單的啊,若有向量和目標向量方向一樣,就直接使用該向量組成目標,否則可以決定出兩個向量使用的係數比,也不難算出至少需要多少係數。甚至連 binary search 都不用。

  之後我在想想 $n > 2$ 的 case,就是再這裡我想歪了 Orz,我想成至多只需要使用兩個向量就行了...(再次強調,這個結論是錯的)。當比賽當時我並不覺得我有想歪,於是就直接 coding,並 WA 在最後一筆 Sample,當時我這樣想:可能只是 $n > 2$ 的某些 case 我 code 有 bug,於是決定還是先傳傳看小測資。但小測資竟然 WA 掉了 @@

  之後我左看右看,都不覺得我 code 哪裡有錯,就算我 $n > 2$ 的版本有錯, $n = 2$ 的應該沒道理錯吧!!!過程中我也把 code 改成純粹的 $n = 2$ 的版本,自己測了不少測資,也還是不知道哪裡出了問題,這時心裡好焦躁。

  debug了一個小時左右,眼看比賽一個小時,我看了一下 score board,我已經落到 1500 名外了... 看起來就算我 現在去 AC 了 pC 和 pD 的小測資,也不可能進 Round 3,如果放棄 pB的話,就要在剩下的一個小時完整解決 pC 或 pD 其中一題,但看了一下目前上傳人數,似乎後面兩題都不簡單耶...,要繼續在 pB 掙扎嗎?還是要換題呢?

  我現在可是處 pB 在連小測資都過不了的狀態,但以經有 $1/3$ 以上的人都 AC 小測資了。以前幾乎不會在個人賽那麼多人 AC的題目上,毫無一點進展那麼久...,但是任何時候都沒有最蠢,只有更蠢吧?所以這時候大概放棄會比較好,於是我開始閱讀 pC。

  讀完題就覺得 flow 感很重,只有兩種語言,許多 flow 問題都是建立在只有兩種區隔上。可是我沒辦法立刻感受到它的模型建出來長怎樣。想了一分鐘以上後還是感受不出來...,嗚 QQ 我可是 ioicamp曾經的 flow講師啊 OAQ 怎麼可以敗在 flow 題上 OAQ,自從我當 flow 講師以後幾乎所有 flow 題都可以分殺 (秒殺有點太超過,所以使用分殺這個詞) 啊!好吧,重新想想我當時是怎麼教 flow 的,如果我自己教的東西都無法幫助我解題,那我算什麼講師啊!!!!

  從頭來!首先,通常題目中都會有看起來就像是可以當做網路中的點的物件,這題可以當做點的有:句子、單字。其次,列出所有限制條件,再跟據限制條件建出網路的弧,有時會為了使限制能表現出來而增加點(ex:點容量) (粗體字是當初我在上課投影片上出現的文字),這題的限制有:同一個句子是同一個語言、前兩個句子已知是兩種不同語言、若一個字被當成兩種語言會有 1 的 cost。由於 cost是在點上,所以可以相信我們建出來的 flow 模型,有必要把每個 word 拆成兩個點:入點和出點。

  接著想想 min-cut 問題的模型代表意義。「我挑完後,剩下的給你」。聽起來好蠢 = =,可是這就是我當初講義上所列的子標題,真實意義為:「min-cut 所分成的兩個點集 ,包含源點的點集是所有原點所能流到的點,而那些點所代表的東西會被歸為一類,剩下的東西會被歸為另一類」。所以我必須建出一個模型,使得除了被 cut 掉的點外,是英文的單字都會被source 連到。由於同一個 sentence 裡都是同一國語言,於是我就把有出現在相同 sentece 的 word pairs 也在當中建一條 cost 無限大的邊。

  於是我最後建出的模型由以下兩個 model 組成:


   比較特別的地方是我把建了 source -> sentence -> sink 這樣的關係,如此建邊可以確保這兩個弧恰有一個在cut裡。除此之外,第一個 sentence 我沒有把它連到 sink,同時我也沒有把 source 連到第二個句子。這樣建出來的模型,min cut 值減去 INF*(句子數-2)就是答案了。可以檢驗看看,求出來的 min cut 的確能把屬於英文的單字和句子都和 source 相連。

  這是憑我的直覺建出來的圖,實際上似乎可以不存在代表 sentence的點,取而代之的是直接把 source 連到第一個句子出現的 words,以及把第二個句子出現的 words 都連到 sink。

  submit 完這題後排名就衝進了前 500 名,我的做法正確的話那麼 Round 3 就穩住了,可是還剩下一些時間,還是繼續回來幫 pB debug 吧 Orz。再重新想想只有兩個向量的 case ... 啊!!!若兩個向量都和目標向量相同,可以兩個向量都使用哇,這麼說來... 三個向量以上的 case 我完全想錯了啦!!!再仔細想一下,發現我原本的 code 可以很容易改成讓小測資 AC,所以在最後的一些時間順手改了一下並 submit。呼 ... AC 了。看來當同一個 bug 卡太久的時候還是讓頭腦先去做點別的事後再來 debug 才會比較有效果 @@,比賽比了那麼多年還是學不了這個教訓@@
  
  比賽 ending 了,我傳的兩題大測資都有確實 AC,有真的進了 Round 3,真是好險...,差點以為我的人生要倒退走了@@

2015年5月25日 星期一

Problem Zero --- 出題是種態度

出題是種態度

出題是種態度

Description

「過去的小月是個常常寫假解 AC 後還暗自竊喜的小廢物,直到小月和球球相遇,小月才知道何謂 演算法的正義 」– 小月

大家好,我是小月,正在辛苦的出題中唷!大家可能會想「出一個 debug 的比賽不是很簡單嘛?」去 Codeforces 或一些競賽網站上找一些簡單題,看看有哪些人在短時間內從 WA 變成 AC,把那些程式碼抓下來,再複製一下測試資料,最後把題目翻譯成中文,就完成了!

這樣子就輕鬆出完一場比賽不是?過去的小月或許會這麼做,但直到了小月與球球相遇。

記得小月和球球第一次相遇是在國中二年級的暑假。那時小月匆匆忙忙地上了火車,準備遠赴台北這個大都市參加一個學術活動。 火車的門關上後不久卻又重新打開,只見一個全身散發出霸氣的人走了進來,大家都因為他帥氣的身影吸走了目光。這次是小月第一次體會到,英雄總是在最後一刻登場的涵義。

相信認識球球的人一定都心有戚戚焉,小月很高興那時有鼓起勇氣去和球球交談,在那之後也從球球身上學到許多東西。 時隔好多年的今日,和球球分開已久,但小月相信球球一定還是在世界某個角落發光發熱。

球球有一個座右銘:「演算法即正義」這同時也是球球的生活態度,小月想要把他的態度,傳達給在座的每一位。請大家原諒小月,在出題過程塞了那麼多話在題目敘述裡,小月只是希望大家能想想看球球說過的話有什麼涵義。請大家在思考題目的同時也看看小月與球球的故事吧!

在故事開始前,先給大家看看球球給小月的第一個教訓:「若平常習慣靠些偷吃步 AC,在關鍵時刻遇到擁有演算法的正義的出題者時,一定會後悔莫及。」例如小月以前在寫最遠點對的問題時,都會先使用凸包模版刷掉一些不須要考慮的點,之後直接枚舉所有點對計算距離。因為小月在還未與球球相遇前,總是相信大多數出題者測資大概都隨便亂生吧。球球在知道這件事後,立刻給小月一個當頭棒喝,生出了一個讓小月 TLE 的測資。

請大家重現球球當初對小月做的事吧!

Original Description

給 $N$ 個平面座標上的點,請求出當中相距最遠的兩個點的距離。為了方便起見,請輸出距離的平方。

Original Input Format

測試資料共有 $N + 1$ 行。第一行有一個正整數 $N$,代表平面上點的個數。 接下來的 $N$ 行,每行有兩個整數 $x_i$, $y_i$,代表第 $i$ 個點的座標是 $(x_i, y_i)$。

  • $2 \le N \le 1,000,000$
  • $−10^9 \le x_i,y_i \le 10^9$

Original Output Format

 對於每組測資輸出一行答案,最遠點距離的平方。

Sample Input

範例 1

2 
0 0 
10 0

範例 2

4
-1000000000 -1000000000 
-1000000000 1000000000
1000000000 -1000000000
1000000000 1000000000

Sample Output

範例 1

100

範例 2

8000000000000000000

Hacked Program

//bcw0x1bd2 {{{
#include<bits/stdc++.h>
using namespace std;
#define FZ(n) memset((n),0,sizeof(n))
#define FMO(n) memset((n),-1,sizeof(n))
#define MC(n,m) memcpy((n),(m),sizeof(n))
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define FOR(x,y) for(__typeof(y.begin())x=y.begin();x!=y.end();x++)
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
// Let's Fight! }}}

const int MXN = 1000005;

struct Point{
  typedef long long T;
  T x, y;

  Point() : x(0), y(0) {}
  Point(T _x, T _y) : x(_x), y(_y) {}

  bool operator < (const Point &b) const{
    return tie(x,y) < tie(b.x,b.y);
  }
  bool operator == (const Point &b) const{
    return tie(x,y) == tie(b.x,b.y);
  }
  Point operator + (const Point &b) const{
    return Point(x+b.x, y+b.y);
  }
  Point operator - (const Point &b) const{
    return Point(x-b.x, y-b.y);
  }
  T operator * (const Point &b) const{
    return x*b.x + y*b.y;
  }
  T operator % (const Point &b) const{
    return x*b.y - y*b.x;
  }
  Point operator * (const T &b) const{
    return Point(x*b, y*b);
  }
  double abs(){
    return sqrt(abs2());
  }
  T abs2(){
    return x*x + y*y;
  }
};

long long cross(Point o, Point a, Point b){
  return (a-o) % (b-o);
}
vector<Point> convex_hull(vector<Point> pt){
  sort(pt.begin(),pt.end());
  int top=0;
  vector<Point> stk(2*pt.size());
  for (int i=0; i<(int)pt.size(); i++){
    while (top >= 2 && cross(stk[top-2],stk[top-1],pt[i]) <= 0)
      top--;
    stk[top++] = pt[i];
  }
  for (int i=pt.size()-2, t=top+1; i>=0; i--){
    while (top >= t && cross(stk[top-2],stk[top-1],pt[i]) <= 0)
      top--;
    stk[top++] = pt[i];
  }
  stk.resize(top-1);
  return stk;
}

int main(){
    int N;
    while (~scanf("%d", &N) && N){
        vector<Point> ip, ret;
        for (int i=0,x,y; i<N; i++){
            scanf("%d%d", &x, &y);
            ip.PB(Point(x,y));
        }
        ret = convex_hull(ip);
        long long ans = 0;
        for (auto p1 : ret)
            for (auto p2: ret)
                ans = max(ans, (p1-p2).abs2());
        printf("%lld\n", ans);
    }
    return 0;
}

Judge Method

請構造出一組測試資料,使得使用上述程式碼凸包後,點數仍至少有 $1,000,000$ 個點。

Sample Program

以下程式碼能產生本題合法但不一定 AC 的測試資料

#include<cstdio>
#include<cstdlib>
#define LL long long
const int MAX = 1000000000;
LL myrand(){
    LL res = ((LL)rand()<<48)^((LL)rand()<<32)^((LL)rand()<<16)^rand();
    if(res<0)res=-(res+1);
    return res;
}
int main(){
    int N = 1000000;
    printf("%d\n",N);
    for(int i=0;i<N;i++){
        printf("%d %d\n",(int)(myrand()%(2*MAX+1)-MAX),(int)(myrand()%(2*MAX+1)-MAX));
    }
    return 0;
}

2015年5月14日 星期四

Kirino in Google Code Jam

最近有種一直在測試各種比賽題目的感覺。而就在今天,我幫忙了一個學長辦一場私人比賽,也就是只前某篇 BLOG 裡提到的飲料盃

在飲料盃裡,我幫忙提供了其中兩個題目,這兩題和一般的競賽題目不同,是屬於 challenge 類型的,也就是題目裡會告訴你某個題目以及給你該題目的 code,你要想辦法生出一組該 code 會 fail 的測資。這很類似在比 Codeforces 和 SRM 時,使用generator 升測資 hack/challenge 別人。

在這裡我放上兩題中的一題,要 challenge 的 code 是我今年 code jam AC 了大小測資的 code。

題目連結

這裡說說這題目出現的來由:

今年 code jam 1A 結束不久後,我在別人的網誌上看到對方閱讀了我的 code 覺得不錯,對此我感到驚恐,因為我有些地方並沒有寫的很確定,深怕別人看了我的 code 後會有所誤會。在仔細思考後,確認了我的 code 確實有誤,於是決定把他出成題目,警惕大家不要看著 id 就隨隨便便相信其他人的 code,也不要太輕易的相信在別人 BLOG 裡看到的解法,請務必自己認真想過一遍 >_<

網路上的資源實在是太多了,但究竟有多少東西是可以相信的呢?我從今從網路看過很多人把自己的在某 Judge 或某比賽的 AC code 貼出來,發現其實錯誤率還蠻高的,真心覺得這件事很恐怖 @@

現在這場比賽還在進行中,等比賽結束我在聊聊這題的解答吧 XD

2015年5月7日 星期四

Codeforces Round #302 參賽紀錄

這場的配分比較奇怪:500-1000-1750-1750-2500
看來這場的難度配置不單純 0.0

  開場先看了 pA,把他列成式子會是一個多元一次不等式的整數解個數的問題,這類的問題一般來說都是使用 dp 做,於是就很直覺的寫了一個 dp。寫到一半發現不對,照感覺寫下去會是 $O(n^4)$,稍微多想了幾秒後,發現他是個另類前綴和類型的 dp,所以複雜度可以少一個 $n$。唔... 這樣的題目在 Div. 1 A 裡面算難吧... ?

  接下來看了 pB,題目包裝的有點隱晦,題目說到要破壞盡量多的路...,立即閃過去的概念是 min-cut 問題,可是明顯不對 = =。馬上把他反過來想,破壞盡量多的路 = 保留盡量少的路,保留盡量少的路...其實就是求兩組點對的最短度?不對不對他們可能會有共用的路,所以要分兩個 case:兩組點對的最短路沒有相交,以及兩組點對的最短路交纏在一起。交纏在一起的話... 根本就是四個點的 steiner tree 問題吧...,三個點或四個點的 steiner tree 問題我看過好幾次了,所以這題和那些題目的差別就只在於多了點對間的路徑還有不能超過某個長度的限制,但這個條件還挺好判掉的。 這題的 code 感覺上有點長唉 ...,思考了幾秒要不要先看其他題,但最後還是決定先把這題寫完。

  寫完 pB,我 lock 了 pA,大略的看了一下大家的 code,感覺都很正常,本來還以為說不定有人會寫 O(n^4)的做法 0.0 看來 pretest 大概有擋調。

  接著看到 pD submit 的人比較多,所以我就先看了 pD。pD 題目很好理解,而且他看起來就很像常見的 dfs 兩次的 tree dp 問題(第一次只 dp 出每個 node 的 subtree 的某些性質,第二次在 dp初以每個點當 root的題目要求的性質),我就靠直覺寫下去了。

  寫完 pD 後, pC 還是只有少量的人 submit,難道說他不簡單嗎>_<,於是我先 lock了一下 pB,先 cha 一下看看,因為這題一副就很容易寫錯的樣子。開了幾份 code 後看到有人漏了一個 case (很容易看出來,因為他 code 比別人少了一部分),賺了 100 分!

  讀了 pC,第一個想到的是,每個字串一定可以靠著改變任一字母來達到題目要求,但,之後呢?這是 min-cost 類 flow 題嗎?感覺不像,要不然 $n、m$ 要更大才對?先想一下還有什麼 case 會讓某些字串滿足條件。若有某個位置,有 $k$ 個字串在該位置有相同字元,那我們就可以改變當中 cost 最小的 $k-1$ 個字元,使得這 $k$ 個字元都變的不一樣!於是,我們可以掃過 input 後得到好多 $1 \sim n$ 的 subset 以及對應的 cost,代表我要讓這個 subset 編號的字串們都滿足條件至少要多少 cost。到這裡,以經可以確信這題是位元 dp 問題了,但實際上究竟要怎麼 dp?好為難喔...,回憶眾多記憶中的位元 dp 方式都不對,如果對於每個 set 子集,都還要枚舉該子集的子集,複雜度太高了。但沒必要枚舉到子集的子集吧?只要枚舉一些重要的子集就好了。這部份我想的有點久 ... 最後總算注意到,所有的 (子集, cost ) 的對數至多才 400 對!$400 * 2^{20}$ 約為 $4*10^8$,常數小小的,以 Codeforces 的主機來說應該輕鬆 AC 吧 XD 許久以前也看過類似的題目,不過記憶模糊了 0.0。

  在寫 pC 快寫完的時候, pD 竟然被 cha 掉了!?為什麼?我哪裡忘記 mod 了嘛?但後來看到 scoreboard 上大家被 cha成一片,可以相信這不是 mod 的問題,我暫時先把 pC 擱著,想了一陣子 pD 到底發生了什麼事。最後注意到,我 dfs 第二次時,有用到模逆的操作,難道說被構造了運算中會有 0 的模逆而造成不可預期的事態?唔...想到這裡,就決定暫時放棄解決這個 bug,先把 pC 寫完。

  submit 完 pC 後,在認真回來想想 pD,先試著想想要構造出能 hack 這樣的 bug 的測資是否很困難,但腦袋有點鈍鈍的,無法清楚思考要怎麼構造。不管啦,先回來看看我要怎麼修掉這個 bug,然後才發現我原本的 dp寫法並不太好 ...,超難修 bug的啊!後來就把整個 dp 的部分重寫了 ... 由於要修的部分太多,所以我沒有在時限內修正完成  OAQ

   賽後問了一下學弟,pD cha 了那麼多份 code 確實是依靠我賽中想到的那個 bug cha 的,賽後我大概又花了約五分鐘把這個 bug 修補完成並 AC。最後 rank 37,以目前我的 rating rank,這樣的名次還是足以讓 rating 增加 84,若能維持這樣的 rating 增加率,要回到至高點還需要三場!

2015年4月28日 星期二

UVa12907-12915

緩慢更新中...感謝 morris821028 幫忙寫 code 驗證我理解是否有誤 m(_ _)m

12907 Toby the adventurer 

題意:有一塊大陸,有 $N$ 個城市,以及 $M$ 條單向道路,每條道路有對應的通行費,有一個人要在這塊大路上冒險,最初他在邊號 $R$ 的城市,他可以付一條路所對應的費用,延著該條路的方向,到一個新的城市,此外,他可以不用付任何費用就回到任何一個他已去過的城市,請問他至少要花多少錢才能逛完所有城市?並輸出旅行的方案。若無解則輸出 impossible。

數據範圍: $測資組數 \leq 100, 3 < N \leq 10000,3 < M \leq N,0 \leq R < N$。

tag:[ 圖論 ]

  乍看之下這題就只是個 DMST (Directed Minimum Spanning Tree) 問題 (一般情況可使用 Edmond's algorithm 解之),且是一個要輸出解的 DMST。但大家應該有發現他有一個超怪的條件: $M \leq N$ !事一定有蹊蹺!?

  首先有件很理所當然的事: $N$ 個點的 DMST 恰有 $N-1$ 條邊。所以我們可以藉此聯想到一個 $O(N^2)$ 的演算法:考慮 $N=M$ 的 case,我們可以枚舉要刪除哪條邊,並 $O(N)$ check 剩下的邊是否為一個合法的 DMST。若 $M<N$ ,答案應該蠻顯然的。

  接下來可以想想看,我們真的要枚舉那麼多種可能性嗎?首先注意到,合法的 DMST 中,每個點的 in degree 幾乎都是 $1$,但 $n$ 條邊 in degree 的總合只有 $n$ 的 ,實際上,除起點外,若有哪個非起點的點在原圖中的 in degree 是 $0$,就沒有解;若 in degree 是 $1$ 則非得選不可。所以可選可不選的邊至多只有兩條!找出那兩條,然後枚舉哪兩種可能看看哪個比較好,就解決這題了。

  若真的遇到 DMST 找解的問題,可是非常痛苦的 ...,我比賽中在解 DMST 問題時,總是直接從 codebook 複製貼上。但是現今大部分的人所使用的 codebook 都沒有包含構造出一組 DMST 解這件事,所以就必須好好重新想想 Edmond's algorithm。實際上,2013-2014 NEERC 就有一題要構造出解的 DMST 問題: UVa 1681 Dictionary,大家可以試著去挑戰他 XD 挑戰完把他加進 codebook XD

  若有在 UVa 找最經典的 DMST 問題:則請看 UVa 11183 - Teen Girl Squad

12908 The book thief

題意:有一個小偷把一本書的所有頁數數字加起來,但漏加了一個數字,告訴你小偷算出的總和的值,請求出該本書有幾頁以及漏加的是哪個數字。

tag:[ 數學 ]

嗯...可以 O(1) 快速得知至少需要幾頁 (1加至總頁數必須大於 input 值),再 check 是否能減掉某個數字就得到 input。實際上你總是能得到一個合法的漏掉的頁數唷!

12909 Numeric Center

題意:給定 $n$,請問 ${1}$, ${1,2}$,${1,2,3}$, ... , ${1,2, \dots , n}$ 的集合中,有多少個集合,能在集合中恰找到一個數 $x$ ,使得集合中小於 $x$ 的數的總和和大於 $x$ 的數的總和相等。例如說,集合 ${1,2,3,4,5,6,7,8}$ 可選 $6$ 為 $x$,使得 $1+2+ \dots + 5 = 7+8$。

tag:[ 數學 ]
關鍵字: Pell's Eaquation

  據說這題只要把最小的幾個數搜出來再拿去 google 就能 google 到數學公式了。

  若要自己解,可以先列出關係式,據說化簡後會得到 $8*x^2 + 1$ 必須是完全平方數,也就是說 $x$ 式所有 $y^2-8*x^2 = 1$的整數解。這東西叫做 佩爾方程,可以 google 到很多關於這東西的資訊,他可以使你用手算一算後很快的得到所有 $x$ 的解的遞推公式。

12910 Snakes and Ladders

題意:蛇梯棋遊戲,使用公平的六面骰,問結束遊戲時的步數期望值。
tag:[ 數學 ]
關鍵字:高斯消去

  就...一臉高斯消去樣,把期望值的關係式列出來後解聯立方程式。

12911 Subset sum

題意:給 $N$ 個數的集合,請問有多少非空子集的集合內數字總合等於給定的值 $T$。
數據範圍:$1\leq N \leq 40$。
tag:[ 小品 ]
關鍵字:分兩半

  通常看到 $N = 40$ 附近的問題... 就會值接兩響到把數據切成兩半的做法。這題的類題不勝枚舉,把集合拆成兩半,每半部的集合都枚舉所有 $2^{N/2}$ 種subset,枚舉其中一半部時 hash 每個總合的值出現多少次,而枚舉另外一半部時,就可以根據hash值得知他有多少種和前一半部的組合加總可以湊成 $T$。

12912 Josephus lottery

題意:有 $N$ 個人圍一圈,由順時針分別從 $1$ 號編號到 $N$ 號,由 $1$ 號開始數,第一輪順時針數 $K$ 個人,並把被數到 $K$ 的人移除,下一輪從被移除的下一個人開始數,但這次是逆時針數 $K$ 個人,一樣把第 $K$ 個人移除,如此反覆順時針逆時針交互的數,直到只剩下一個人,請問剩下的人編號是多少?
數據範圍:$1 \leq \leq K \leq N \leq 10^6$。

  就約瑟夫問題變形。雖然 $N$ 很大,但 $O(N log N)$ 做法就可以 AC 了。與一般的約瑟夫問題一樣,可以倒著用 $O(n)$的時間複雜度 dp 回來。

12913 Grounded

題意:給定 $N$、$K$,$S$ 為包含 $0 \sim 2^N - 1$ 間所有整數的集合,請問 $S$ 有多少子集合滿足集合內所有數的 xor 結果,轉乘二進位後恰有 $K$ 個 bit 是 1。

數據範圍:$1 \leq K \leq N \leq 10^6$
tag:[ 數學 ]
關鍵字:集合

和 Hackerrank 上的 Ad Infinitum 10 - Math Programming Contest Number of zero-xor subsets 概念一模一樣,差別只在於 Hackerrank 那題只問 $K = 0$ 的 case,所以去參考Hackerrank 上的 Editorial 理解後應該也能做出這題。

我來用我自己的方法解釋 $K = 0$ 的 case。 $K = 0$ 意即該集合所有數的 xor 結果為 $0$。先隨便亂抓一個集合,例如說 $N = 3$ 時,我們任取一個集合:{2,3,5,6},這四個數 xor 結果為 $2$,並不是 $0$,現在我們想要把這個集合稍做修改,讓他變成 $0$,要怎麼做呢?應該會很直覺的把集合內的 $2$ 去掉吧?那若現在取的集合是 {4,6} 呢? 此集合 xor 後的結果也是 $2$,那我們就可以把 $2$ 加進這個集合裡,能使集合的 xor 值也變成 $0$。

於是我們可以發現,任取一個 $S$ 的子集,我們都有辦法恰對集合新增或移除一個數,讓集合內所有數 xor 結果為 $0$ (注意我們新增或移除的數可能是 $0$),且方法恰只有一種。所以說,總共有 $2^{2^N}$ 種子集合,我們就能變出 $2^{2^N}$ 個 xor 值為 0 的集合嗎!?當然不可能啦 XD 實際上,會有好多個集合改變後會對應到同一個集合,那麼一個 xor 值為 $0$ 的集合,會被幾個集合對應到呢?例如 $N = 2$ 時,{1,2,3} 集合內所有數 xor 值為 $0$,而會對應到他的集合有 {0,1,2,3}、{2,3}、{1,3}、{1,2} 共四種。到這裡應該能看出點頭緒了吧?對於每一種集合內所有數 xor 值為 $0$ 的集合,都恰有 $2^N$ 個集合能經過加減一個元素的操作對應到它。所以全部 $S$ 的子集合,每 $2^N$ 個集合會對應到一個 xor 值為 $0$ 的集合,故全部共有 $(2^{2^N})/(2^N)$ 個 xor 值為 $0$ 的集合!這也就是 hackerrank 那提的答案。

至於 $K$ 不為 $0$ 要怎麼辦呢?剛才我們解的是 xor 值為 $0$ 的集合數,那 xor 值為 $1$ 呢? xor 值為 $2$ 呢?能如法炮製嗎?

12914 Sum of all permutation


12915 TripleCorn


正常的 dp 優化題?

2015年4月27日 星期一

Codeforces Round #300 參賽記錄

比賽連結
Editorial 連結

  這場比賽我除了解題順序不認真以外,其他部分我可是非常認真的!在賽中完全沒有想過要去 challenge 別人!有人在賽中敲我 g+ 我也沒回應!但是名次好慘呵,我花了一個小時左右寫完了 C、D、F 後,直接打開 G,剩下的一個半小時都栽在上面了,賽中剩下 20 分鐘才想到解法,賽後一個小時左右才 AC。最後 rank 371,連抽 T-shirt 的機會都沒有。還有人問我是否想要再一次變成藍色,聽到別人這樣問我我好傷心喔 XDDD,我這幾場都有好好的比耶 XDDD 只是最近的比賽不小心把我的實力揭露出來讓我連掉五場 rating XDDD 最近的幾場比賽大都是比較大型的比賽諸如 VK cup、ZeptoLab Code Rush 之類的,每次遇到大型比賽我的名次就會變糟糕 ... 這是心理壓力的關係嗎?

  最近總是直接寫題目的解答,這篇來回覆一下我以前在 BBS 使用的方式紀錄比賽,把比賽過程中我在思考什麼,在哪些地方卡住等資訊近可能的保留下來。

  這場比賽,我想要犧牲一些解簡單題的時間,來換取更高的賽中 AC 難題的可能性,所以開場就直接從 pC 看起,看完後我就立刻連想到了 CF534 B - Covered Path,都是類似的概念,相鄰兩個時間點直不能超過給定值的題目。可是我的思緒很混亂,寫出了比較複雜的做法,明明就寫一個 for 迴圈就能解決,我卻寫了兩個,順的跑一次逆的也跑一次,還出了點 bug,結果13分鐘才 AC,這時候已經有不少人前三題都寫完了 =口= 結果我先寫 C也沒省到多少時間嘛 = =

  接著我直接看 pD 也是個還算直覺但要把他寫成 code 無法立刻想到好寫的做法,但我還是憑直覺寫下去了。總之就是先簡查哪些向量若可以選就一定要選他,在檢查看看使用這些所有選的向量是否能攻擊到所有得被攻擊到的位置。是說這題 Sample Output很心機,硬是要和大家直覺寫出來的 Output長的不一樣...。我原本漏考慮了有可能會攻擊到盤面外部的 case,使得 Output 總是輸出 NO,我大概花了兩三分鐘才 de 出這個問題,後來修正後 output 還是和 Sample Output不一樣 = =,check 了一下才確定我的 output 確實也是正確的。

  我寫完兩題後已經有人寫了五題了!挫敗感很高耶,我決定跳過 pE,直接看也有人在短時間 AC 的 pF。pF看完我立刻往複雜度 $O(n \sqrt{n})$ 的方向去想,因為讀完題目後立刻從我腦海裡浮現的知識是:每個 node 當 $k$ 的值從 $1 \sim n-1$,在改變時,他的父節點可能只會改變 $O(\sqrt{n})$ 次,這就和 $n$ 固定,$k$ 會改變時 $\lfloor n/k \rfloor$ 的可能值至多只有 $O(\sqrt{n})$ 很像,因為父節點的編號實際上就是 $\lfloor (x-2)/k \rfloor + 1$,所以要解這題,我們只需要把每個節點的的可能的父節點都各別求出來,以及會對應到該父節點的 $k$ 值個數也求出來就行了。於是讀完題想不到一分鐘我就立刻開始寫 code,但是寫到剩最後一部分 --- 記算父節點的編號以及有多少 $k$ 值會對應到該編號,我卻卡住了,我腦袋轉不過來 ... 每次我在認真比賽的時候,都不太能進行這類比較複雜的計算 ... 團體賽的時候我還可以秤隊友還在 coding 時,在旁邊深呼吸,想辦法靜下心然後在開始動筆計算,可是在個人賽的時候我幾乎無法靜下心做這件事,啊啊啊該怎麼辦 >_<

  這時我想法亂成一團,在思考要不要靜下心好好動筆算的時候,有想到了令一種思考此題的方式 --- 上段所述的方法是固定子節點,思考父節點的變化。但我們可以從另外一個角度:考慮每個父節點,看看他有哪些子節點,我們可以發現,當 $k$ 愈大的時候擁有子節點的節點數量為 $O(n/k)$ ,所以若先把所有父節點所擁有的子節點區間都離線存下來,就可以 $O(n \log^2{n})$  (因為總共有 $O(n \log{n})$ 個區間) 配合 BIT 掃過求出每個父節點有多少子節點的值比自己大。原本我有點擔心這樣會不會花太多記憶體儲存,但你若有仔細看這題的記憶體限制,會發現這題的限制是 $512$ MB,比預設的 $256$ MB 還大,就會發現 author 預設的解法大概就是這個做法吧?要不然上一段的做法根本不需要什麼記憶體 XD 這個做法想清楚後,我就把原本寫的 code 果斷砍掉了 ... 重寫新的做法,寫完 Sample 對了之後我還自己生了最大的測資測了我的 code 的速度,看來是沒什麼問題後才 submit。我寫完三題時,已經有不少人把前六題都寫完啦!!!

  隨便點了幾份 pF 的 code,兩種做法都有了寫,第一種做法的程式碼可以參考 rng_58 的 code,寫的非常精簡,而賽中14分鐘就 AC 的人則是使用第二種方法,他沒有離線預處理,而是使有了比較複雜的資料結構 (WaveletTree?這什麼東西@@) 使得可以 online 快速知道一個區間內有多少數小於給定值。

  上傳 pF 後,我鐵了心直接挑戰 pG。 pG 題目非常簡短如下:

有一個長度為 $l$ 由 ULRD 所組成的上下左右的移動指令,你並不知道指令的 pattern 長怎樣。有一個機器人起點在 (0,0),每一單位時間依序按照這串指令直性移步並移動一單位距離,若這串指令都執行過,會再從頭開始用同樣的 pattern 繼續移動。告訴你這個機起人某些時間點的位置,請找出一種可能的 pattern 或輸出無解。

   這題感覺起來有點數學,又有點差分約數的感覺?我覺得我一定能解出來!但是想了許久就是沒什麼想到什麼明確的起手步,是因為有一點點精神不濟想睡覺的關係嗎?先把題目化簡移下好了,這題是二維的,如果變成一維的話我要怎麼做?想到這裡,我就發現,若會做一維,也就是說只有LR兩種指令的版本那麼我們就可以解二維的了!因為我們可以把U, R以及 L,D 分別是為同意種指令,若是 U,R 的指令那麼機器人所在的座標 $(x,y)$ 中 $x+y$ 的值就會加 $1$,若是 L,D 則會減 $1$。固解出一維的 case,我們就能月定pattern的每個指令會是L,D兩者之一或是 U,R 兩者之一。接著我們在改成把 L,U 和 D,R 個別綁在一起,做出來後就能就能得所有指令了!

  轉換成一維(只有 L,R 兩種指令) 後我仍舊卡了很久,要按照時間序考慮問題嗎?還是按照時間 mod $l$ 的值由小到大考慮問題呢?如果有出現兩個時間 mod $l$ 的值相同又會怎樣?我們就可以得到整串指令移動完的為移會是多少,知道這件事後又怎樣?知道這件事後我們就可以按照時間 mod $l$ 的值由小到大考慮所有已知機器人的位置,做一些運算後,得知很多諸如 (前 $i$ 個指令移動完位移將是 $d_i$ ) 的資訊,如果 $d_i < 0$ 或 $d_i > i$ 或 $d_i$ 和 $i$ 的奇偶性不同就不合法,否則就可以貪心的填入 $(d_i + i)/2$ 個 R 進去之類的。所以若有兩個已知機器人位置的時間點 mod $l$ 結果相同,我們就可以得到正確的 pattern!所以我解決的其中一種 special case!但這要怎麼推廣?完全想不到啊 >_<

  這種 special case 我們能確定 pattern 的主因是我們知道了整個指令群移動完的位移的值(令其為 $ds$),所以我們若能確定該值,就解決了吧? $ds$ 的值的可能性有 $0 \sim l$ 那麼多種,有辦法縮小其範圍嗎?有沒有可能同一組測資擁有不同的 $ds$ 值的合法解呢?這麼說來剛剛我們確定了 $ds$ 就能知道每個區間內有多少個 R 指令,所以說我們若把每個區間內的 R 指令個數當成變數,稱其為 $r_i$ 之類的,那就可以把 $ds$ 和 $r_i$ 列出線性等式吧?而且我們擁有 $ds$ 和所有 $r_i$ 的上下界( $ds$ 的上下界是 $0$ 和 $l$, $r_i$的上下界是 $0$ 和 該區間大小),那是否存在某種快速枚舉這些變數的值的並判定有無合法解的演算法呢?嗯... 若枚舉了任何一個變數的值那麼就可以 $O(n)$ 判斷是否有合法解了,若枚舉 $ds$ 的 $O(l)$ 種可能值,那複雜度最高就是 $O(ln)$ 有點大耶?嗯... 某種程度上這些區間是型成環狀的... 環狀?枚舉!?這件是好像有印象!那不就是 CF526 E 的其中一種算法嗎?因為有 $n$ 個區間,所以至少有一個區間 size $\leq l/n$,所以就會至少存在有某個變數要枚舉的可能性 $\leq l/n$ 於是找出該變數並枚舉的複雜度會是 $O(l)$!於是我就解出來啦!想到這裡的時候,比賽已經剩不到 $30$ 分鐘了 0.0

  最後寫 code 時發現使用這種做法還有好多好多 special case 要處理 ...  那些 $ds$ 在等式中係數可能是 $0$ 之類的問題,或是所有時間點剛好 mod $l$ 都是 $0$ 的問題(我覺得這個 bug 思考時不會漏掉的一定都是怪人!)。

  AC 候我就在想,我使用了一個那麼奇怪的技巧來 AC 這題,想必不是 author 所用的解吧?而且這個技巧不久前才出現過耶?後來看了其他所有 AC 的 code,果然只有我使用這個方法 ...,我忽略了一件很重要的事:所有聯立等式中 $r_i$ 的細數都是 $1$ !所以對於每個 $q+i * ds + r_i = v_i$ 的等式,我們可以根據 $r_i$ 的上下界來更新 $ds$ 的上下界,若全部等式更新完後 $ds$仍有整數解,那麼代入任一個 $ds$ 的整數解給所有式子後一定能得到在合法範圍裡的 $r_i$ 的整數解。於是 $code$ 應該能變成更簡單一些,根本不必枚舉某個變數的所有可能值啊!若...我在看到這題時,碼上就把所有該列的變數該列的等式列出來在紙上,是否能快一點想到呢?但我相信拿麼做的話就不會產生我這種奇葩的解法了 0.0

  呵呵在最後一步採用了有點多餘且非常獵奇的方法,我該為此感到自豪還哀傷呢?

  賽後看了剩下的題目, pA直接暴力枚舉即可。pB 就是一個很直覺的 greedy。 pE 就普通的 tree dp,記算可能要小心一點。 pH,嗯... 感覺起來不太難,要歸類為 greedy 吧?想了一下細節,覺得應該就是那樣了。不過 pH 目前 最短的AC code 值得研究研究,他的解題步驟和我的思考順序並不一樣,我還不知道怎麼證他的做法的正確性 ... 證出來並覺得很有意思的話再分享吧?

  如果我這篇相較於過去的解題報告,寫的讓大家完全看不懂,想必是很正常的一件事...

2015年4月26日 星期日

TLX Open Contest Beta Round #1

昨天心血來潮就寫了一下這個據說是APIO熱身賽的東西 (Invitation from Codeforces)

題目感覺上都蠻普通的,APIO 應該會比這些題目難很多吧?題目品質也有點問題,pB、pC都有嚴重的 issue ,賽中才被更正。

是說 SRM656 的解題報告寫了一半覺得好難寫,先跑來寫這個簡單的東西 wwwwww

題目連結(必須登入)

Problem --- Social Inequality

題意:給 $N$ 個點,問有多少任兩個點所圍出的矩形的面積總合。

數據範圍:$1 \leq N \leq 10^5$,所有點座標介於 $0 \sim 10^4$

關鍵字:[ D&C ]

tag:分治法
= = = = = = = = = = = = = = =
這題正好可以看出我在解題時會怎樣去聯想以做過的題目。它給了平面上好多點,又問了關於所有矩形的某些資訊,於是我就聯想到了  ZeptoLab Code Rush 2015 pF,是我過去寫過題解的東西!(我每次列的關鍵字終於用到了 XD 輕鬆搜到這題 ),於是我就開始思考要怎樣用Divide and Conquer 來解這題。

使用的 D&C 來解這題的話,大制概念就是每次把點群都分兩半,把兩對角恰在兩半各一個的矩行面積總和先算出來,再遞回下去。

這題時限只有 0.3 秒,看來一定得用 $O(n log n)$ 的解法才能 AC,所以在每次解一個 subproblem 時,只能用 O(n) 去解決 (這裡的 $n$ 是該 subproblem 的點數)。

仔細描述一下我們要解的 subproblem:
  平面上有很多點,以及一條水平線,請把所有水平線上及水平線下各曲一點的所有組合,每個組合所圍成的矩行面積總合計算出來。

不防假設我們已經把所有點由左到右排序好了。接著我們由左到右一個點一個點依序加入,每加入一個點時,我們希望能以 $O(1)$ 的時間,把該點與所有在另外一半的已加入點所圍成的矩形面積總合算出來。

如下圖所示,假設現在加入的是在下半部的藍點,而在上半部已存在的點是三個紅點。要一次行算出所有的面積似乎有點困難,但我們若再把每個舉行細分為上半部和下半部,就會發現要一次把所有矩行的下半部面積總合算出來(或是上半部),都沒有很困難。

例如說我要算下半部的部分,我們可以發現所有下半部的矩形高都一樣,在新增藍點時才會決定(令其為 $h$)。所以我們若能知道所有矩行寬的總和($\sum w_i$),就可以算出所有下半部的矩形面積總合($\sum{w_i*h}$),以下圖為例,令藍點 $x$ 座標為 $x_b$,紅點座標為 $x_1, x_2, x_3$,則 $\sum{w_i} = \sum{(x_b - x_i)} = 3*x_b - \sum{x_i}$。所以實際上我們只要記錄每一半部已經加入多少點,加進去的點的 $x$ 座標和,就可以快速算出加入的點所在的那半部矩形面積總合。

而另外一半部也能使用某些累加的概念去算出面積總和,詳情請參考我所付的程式碼 >_<

若要認真考慮 Divide and Conquer 中的 Conquer 到底有沒有在這個解法起作用...其實我覺得並沒有 ... 所以還是稱它為分治法好了 Orz



我的程式碼如下:

Problem --- Jump!

題意:有無窮多的個石頭,並把它們用正整數編號。每個石頭都有個對應的值 $a_i$。有多個詢問。詢問過程中要維護一個數 $N$。第一種詢問:給定 $N$ 的新的值。第二種詢問:更新給定編號的石頭的值。第三種詢問:你可以選擇一個數 $P$ ($2 \leq P \leq N-2$ 或 $P = 0$),最初會先把石頭 $1$ 標記,接著會把石頭 $(P$ mod $N) + 1$,  $(P*2$ mod $N) + 1$, $\dots $ 也標記,直到再遇到石頭 $1$ 為止,請問選哪個 $P$ 值,能使得被標記的石頭所對應到的值總和最大($P$ 若選 $0$ 代表指標記邊號 $1$ 的石頭)?請輸出最大的總和值。

數據範圍:$1 \leq N \leq 2000$,詢問數 $\leq 50,000$。

關鍵字:[ 資料結構 ]

= = = = = = = = = = = = = = =
這題題目敘述很複雜... 而且一剛開始 $P$ 的範圍還給錯使我 WA 了好多次。

首先要注意到雖然我們選的 $P$ 值可能不同,但若 $gcd (P, N)$ 相同的話,標記到的石頭們會是同一群,也就是所有邊號為 $gcd(P, N)$ 的倍數加 $1$ 的石頭。方便起見,值接把所有石頭邊號減一會比較好寫 code。

注意到這件事後,我們就知道對於每個第二種詢問,只需要考慮是 $N$ 的因數的 $P$ 值 (當 $N \leq 6$ 時,有可能不存在合法的 $P$ 使得 $gcd(P,N) = 1$,要特別處理)。並且在枚舉這些值時,可以用一些資料結構如樹狀數組(Binary Index Tree, BIT)去算加總。

詳情參考我的程式碼:


Problem --- Fowl Scupltures

題意:平面上有好多個點,以及一條通過原點的直線,這些點是兩兩成對的,也就是說所有點對於該直線的隊稱位置也會有一個點。但現在某些點消失了,並且我們也不知道直線在哪(只知道它通過原點),問至少消失幾個點,以及直線可能的位置(若有多種可能位置請選取最離 $x$ 軸政像逆時針角度最大的位置)

數據範圍:點數 $\leq 2000$,所有座標絕對值 $\leq 10^9$。

關鍵字:[ 計算幾何 ] [ 枚舉 ]

= = = = = = = = = = = = = = =
這題其實有個很大的癥結點:題目沒說明點若恰好在那條直線上會發生什麼事,若造測資條件所述:"No two or more sculptures are located on the same coordinate." 那麼點應該不能出現在直線上,可是沒有判這件事也會 AC (判了說不定會變成 WA?),總之先無視這個問題...

要使得消失的點最少,也就是要使得配對到的點對最多。並且每個點對若能配對,也都會有個配對時會對應到的角度。於是我們枚舉任兩點能夠配對時的角度,只留下角度的資訊,可哪個角度出現最多次,那個角度就是答案了。至於對稱軸的角度,在這題裡可以使用向量取代,於是不會有浮點數誤差。細節請看程式碼註解。

我的程式碼:

2015年4月20日 星期一

論台灣的數學競賽對資訊競賽的直接影響

我在問卷裡面收到了非常非常多各式各樣的問題,諸如問某些參考書推不推薦,codebook 如何準備等,有些問題我還在想要怎麼回答,或到底要不要回答 ... 但有一個問題是這樣的:

  玩資訊競賽的人,有不少人是由練習數奧的人轉進來(似乎是越來越多,不知是否為錯覺),感覺能力都很強,能否談談先練數奧的人有哪些優缺點,還是根本差不多。

這問題一直以來我都很感興趣,畢竟我自己就是個從數奧轉進來的例子,所以想談談我的看法。

先列一下我所知道的一些資料。

         數學        資訊

95級

蔡政江            多年數奧金牌     高中時期或更以前就有接觸,大學時代表台大去                     World Final 兩次

96級

tmt514             2007數奧候補國手2          資奧金牌,ACM ICPC World Final 金牌
gloompisces    2006年數奧二階選訓營     參加多年台大培訓班97級
kelvin              國中有玩不少數學競賽  資奧金牌,ACM ICPC World Final 金牌
takaramono     2008數奧金牌                      ACM ICPC World Final 金牌
johnathan79717    2008數奧銀牌                      大學畢業後時常玩 online competition
dreamoon              2008數奧候補國手2           大學時代表台大去 World Final 一次

98級
peter50216            2008數奧銀牌                      資奧金牌,ACM ICPC World Final 金牌

99級
shik            2010亞太數學榮譽獎(台灣 top10) 資奧金牌,ACM ICPC World Final 金牌
surwdkgo              2008數奧金牌                       資奧金牌
demipenguin         2009數奧銀牌                       有參加台大培訓班 (在隊伍中角色定位似乎是幫忙                                                                               想題目,比較少 coding)
b92paul                 2010數奧銀牌                       有 World Final 資格




離2008數奧愈遠的我就愈不熟了,似乎還有不少在玩資訊的人也都有盡過數奧選訓營?而再更年輕的人我就完全不知道了 0.0

並且,在早期 Codeforces Red Coder 還不到一百多人的時候,台灣的 Red Coder 根本就全都是有玩過數學的人!當中大概只有 shik 的數學和資訊程度是同時並進,其他人最初數學的程度都遠遠超過資訊的程度。

以上是數據資料,接下來是我個人的感想:

1. 實際上 ... 有很多人根本就每一科都很強嘛!去玩物理或化學也都能拿到金牌。但為什麼數       學轉資訊的人特別多呢?我覺得這是因為喜歡數學的人容易喜歡玩資訊,這兩科給人的感       覺比較像吧。

2. 在資訊競賽上,所需要的很多能力,都是強化數學能力過的人都具有的,甚至有些資訊競       賽的題目和數學競賽的題目有重疊。

3. 高中以前由於學校根本沒有資訊相關科目。電腦課不就只是個讓大家打電動的課嘛?甚至連不少資訊科系相關大學生也都視資料結構與演算法只是天才在讀的東西,普通的人不知道大概也能活的好好的。於是演算法的教育資源相對少,教育資源少,直接資訊競賽起家就變的不如從數學競賽起家。建立好完整的邏輯數學能力後在接觸資訊,反而變的直接從資訊入手還容易(?這只是我的猜想,因為實際上學數學的人其實也都花了大量的時間耶,沒有數學基礎而從國高中才接觸資訊怎麼可能和從國小就培養好數學能力的人比呀?)

甚至我覺得,數學和演算法真能分開嘛?或許把眼算法教育的部分內容直接納入數學教育也是不錯?


最後說說自己為什麼數學轉資訊。

實際上...,我不只玩資訊,我高中也玩物理也玩化學,但由於我並沒有像某些人那麼強能夠把奧林匹亞玩過一輪,所以我高中以前把心力幾乎放在數學上,其他科目大概就是打打小比賽吧?資訊我有打 NPSC,物理我也去參加過兩岸力學競賽,化學去玩玩清華盃化學競賽也是有得到銀牌接近金牌的成績。我就只是個很愛玩理科的學術比賽的人罷了 Orz (我也要嘗試接觸生物,但是覺得太過需要大量記憶,相關比賽也很少,就放棄了... ) 所以,真要說為什麼我從數學轉資訊,答案大概是:大學以後還有很多比賽可以繼續玩 ...。另外一個理由或許是因為覺得參加資訊競賽的有趣程度遠高於其他科目競賽,但我有確切的這種感覺也已經是上大學之後的事了。

想認真參與資訊競賽的小朋友們啊~你們真的覺得數學不好能放著不管嘛~由其是離散數學的部分包括排列組合可是非常重要哪。

2015年4月17日 星期五

小月的出題之路

開始寫這樣的文章,就好像我不再打算出題的感覺 XD
啊啊啊但最近覺得我生出來的題目都落入俗套好不開心喔。乾脆退休好了 OAQ

以下正文 ( 含有某些題目的提示,請小心服用 )


前言

關於我的出題的相關訪談, Topcoder 曾經簡單的訪問過我 (連結在此)。但現在我改成使用中文,可以聊的更多 :P

  演算法競賽非常有趣的一點就是:任何人都可以輕易出題,題目俯拾皆是,生活上遇到的大大小小問題,都可以經過一些化簡或聯想就變出一道題目,只不過大多數變出來且你自己會解的題目大都很簡單就是了。舉例來說,我現在要拿衛生紙來當題目好了 (剛好看到桌上擺著一包衛生紙 XD),現在臨場想一題,我會怎麼想呢?首先,我會先想想有什麼和衛生紙有關的事件,於是我想到了:有時候我們在抽衛生紙,會不小心一抽起來就是兩三張。那麼我就根據這樣的事件隨便亂編一個題目如下:
  
  我有一包全新的衛生紙,共有 $n$ 張,每次抽的時候可能會抽到 $1 \sim 3$ 張,若把整包衛生只每次抽的張數記錄下來,直到整包抽完,請問記錄下來的序列有多少不同的可能?

  這樣儼然就生出了一道題目,雖然這題其實就只是非常普通的矩陣冪的題目而已 XD

  所以我會說,出題是一種藝術,當你聯想能力愈高,就愈能變出樣貌豐富的題目。但大部分的人應該並不希望只能生出一蘿筐的簡單題。

   但直至今日,我從來不覺得我能生出困難的題目,畢竟所有我生出來的題目都是我自己在短時間 (只想了一天也會被我歸為短時間) 內就解的出來的題目,而且至今我出的題目,除了程式碼或邏輯過複雜的題目外,都有人能夠在僅僅幾個小時的比賽內就解出來,所以客觀的來看都不算太難。以上當然是由我自己的標準來評判的,或許對很多人來說還是覺得我有出了不少難題。所以我有種感覺:當我本身的程度到哪,我能出的題目難度就到哪。

當上培訓班助教與出題

我大量出題是從大學四年級時當了台大培訓班的助教開始,那時我的程度和現在相比差多了,那年我出的題目相較最近出的題目都簡單上許多,甚至當時有些題目我只是想了題目敘述 (idea),但我自己並不會做,解法則是由另外一位助教 kelvin 和我討論幫我解法的。

  此時我就已時常使用我前言所述的方式出題目。例如,那時我很愛玩 Facebook 的 Tetris,我就用 Tetris 的方塊出了一個 bfs 題。又例如,我一直對台大 7-Eleven 九折折扣方式是五捨六入感到興趣,就以這個當作主題出了另一道題。那時出了很多題目的感覺真的很開心。

  我和 kelvin 是學校住宿同房間的室友,我們時常在宿舍房間內一起討論出題,你說一句,我補充一句如此這般地把一些題目建構起來。我們也會有思緒不周或卡住的時候,這時會由另一個人來補足。所以我覺得,在出題時和別人討論是很有幫助的。

  除了用聯想的方式出題外,我也會設定某個演算法主題來出題,例如說:我為了要出一個二分圖配對類形的 flow 題,就聯想到了學校排課表,已知每個老師有空的時間和需要上課的時數,請給出一種排課表方法。不過此時我用此方法生出來的題目都很裸。

解題與出題的連鎖效應

  有時出了較難的題目是因為我在解題時,讀錯題目意思。例如:Codeforces 516D。若歸納我以前至今出過的題目就會發現,這題的解法結構有些複雜、題目敘述有點硬拗,其原因就是這題是我三年前左右看錯題目而生出來的題目,可惜原題以不可考。

  有時出的新題目是運用其他題目來當成起點做聯想而成的。例如:Codeforces 515C。這題就是我為了生這場 Codeforces Round,於是大量刷 UVa 水題尋找出題靈感,並看到了 UVa12765 後生出了該題。這樣的變化應該不會有人稱之為抄襲吧?

玩遊戲中的腦力激盪

  在我生的題目當中,一些讓我最覺得得意的題目幾乎都是在玩遊戲的過程中生出來的。我在玩遊戲時常常會自己設定一些遊戲目標,或追求遊戲效率,而這些東西常常可以變成競賽題目。例如說 SRM 628 Div1 Hard ,這是我在玩 Candy Crush,想要達成每關都拿到三顆星的目標時聯想道的題目。再例如 SRM 639 Div1 Hard,這是我在玩 Criminal case 時,從遊戲中的餵小狗環節而聯想到的題目 (話說我第一次自發性寫非競賽解題類的程式就是用按鍵精靈寫餵寵物的功能...雖然我懷疑這種程度的東西能否稱為程式就是了 XD)。

  其他令我連想到題目的遊戲還有猴子射氣球 (Bloons TD5)、神魔之塔等,而且我常常玩遊戲會玩到我把它們出成題目後才把該遊戲戒掉 Orz (當初在玩神魔之塔的時候我完全瘋掉了 Orz 曾以為我就會這樣永遠停不下來。但就在某天我把神魔之塔變成題目後,以那天為分界點,我從一天玩好幾個小時轉變成完全沒在玩 )

  我以上舉的兩個 SRM 的題目都不算簡單,但為什麼我能生出它們呢?講白一點就是我本身的解題能力有到達這樣的程度吧,並且我也覺得大四以前的我解不出這些題目,所以若在大四時就有這些題目的 idea 或許也無法出成題目。但當自己程度也許不夠時,事情也許沒那麼糟糕,就如同前面所說,我大四剛開始出題時,有些題目我只有 idea,但解法是 kelvin 幫忙想到的。所以多找別人討論,或許能合力想出好題目。

出題的滾雪球效應

  有在參加 Topcoder SRM 的人也許有發現,Div 1 和 Div 2 的題目常常長得很像,但其實問的是兩回事,這就好像,你在編故事時,讓它產生兩種不同路線。我也常在 SRM 上出題,我在產生那些題目時,幾乎都是先有了 Div.1 的題目,然後再把它改編成 Div.2。但也有少數時候,是先有 Div.2,再變成 Div. 1。要把題目改簡單或改難都是很有可能的。若想要看看世界上的大家都是怎麼改編題目的,可以從 Topcoder SRM 的考古題得到大量參考資料。

如何出好題或難題?

  有人問我該如何出好題或難題?並覺得若先思考要考什麼演算法,而再去出題目,時常會被一眼就看穿題目是在考什麼。這該怎麼改進?

  我談一下這個問題讓我想到什麼。(讀者回饋第一彈 XD )

  大家可以先想想看,究竟是怎樣的題目會讓你一看到就知道在考什麼?這個問題大概很難歸納出所以然吧 XD 所以我們從反方向的角度思考看看,怎樣的題目會讓我們很難聯想到他在考什麼?

Dijkstra 三部曲

我拿 Dijkstra 這個最短路演算法來作舉例,大部分的 Dijkstra 問題就是題目告訴你一些點和一些邊,直接要你計算最短路,在多一點變化就是點的狀態避不是單純的一個點,邊也不是題目就給你一個邊的權重,你要好好的求出來,但大部分這類的題目你還是一看就知道是最短路問題,只是要好好的思考點和邊怎麼定。

  首先我們來看一題:有至多 $n$ 個 $1 \sim 9$ 的整數,請問他們的乘積 mod $m$ 的可能值有多少?其中 $n,m \leq 10^5$。(source: TCO14 pickup match 某一題750,確切題目我忘記了,我找不到原題)

  這題我第一眼以為它是數論題,可是再多想幾分鐘,發現它其時只是個 bfs。把每個數字都當成一個點,並把所有 $x$ 至 $kx$ 連一條邊 ($1 \leq k \leq 9$),BFS n 步以內就行了。(若覺得困惑標題為何標題是 Dijkstra,做法卻是 bfs?請把這股疑問藏在心裡就好... )

  再看看第二題:SRM 615 Div.1 Level 2。給一個圖,至多 $50$ 個點,每條邊的 cost 介於 $1 \sim 10^4$,問點 $0$ 至點 $1$ 有沒有長度恰為 $T$ ($\leq 10^18$) 的 path (可以非 simple)。

  這題我想了幾乎整場 round,以為它是某種矩陣冪的題目,結果它竟然是 dijkstra !

  最後看第三題:NPSC 2014 高中組決賽 pH。有 $n$ 種不同的錢幣,告訴你每種錢幣的幣值,現在有 $q$ 個問題,問你有沒有辦法剛好用這些錢幣附價值為 $K$ 商品? ($n \leq 50$,所有錢幣的幣值不超過$10^6$,商品價值不超過 $10^9$)

  這題我想了十幾分鐘吧?想了十幾分鐘後突然就連想到第二題那題 SRM 的題目,之後我就會做了。所以這題也是個 dijkstra!難以置信吧!

  大家覺得,這些題目是因為想要考 bfs 或 dijkstra,才生出了這些題目,還是因為先有題面,才剛好想到可以用 dijkstra 做呢?我不是出題者所以我無法回答,但我會猜答案是後者。我個人預設演算法才出的所有題目精巧度大概都比不上這些題,所以我覺得,先想好要考什麼,再出題目,要出的非常好可能有點困難...,但你們大可以反駁我我舉的例子太極端了 XD

  但我們可以觀察一下這些例子有什麼特性: 1. 看到題目的第一眼,會誤會成是在考其他種類的算法。2. 一般最短路的問題形式被拿掉了,例如說:一般最短路是問 xxx 最小是多少?可是第二第三題都是在問:有沒有剛剛好湊成 xxx 的方法。

  於是我覺得,要根據一個演算法出一個好問題,就要打破一般我們對該演算法的常見問題的既定印象,至少要把他改到你自己都不覺得自己看完題目能立刻想到該演算法,或是在該演算法上再疊加一些其他演算法來混淆視聽。

  我覺得人腦在解題就是一個類似 machine learning 的過程,大部分的人腦構造應該差不多吧?如果你自己都覺得你看到這樣的題目敘述能直接聯想到演算法,那大部分的人應該也會有這樣的感覺吧?所以出題要出的好,要盡量把題目變成你會覺得過了幾天你再重看這題可能就無法立刻想到做法了。

對不起我也是個抄襲別人 idea 的人...

其實我沒要道歉的意思(誤)。接下來我要以自己出的題目舉例,當我想考某個演算法或其他題目的 idea,我是怎麼對題目加工來讓別人感覺不出我在抄襲。

  首先請看 NWERC 2011 Piece it together。當初我解這題是使用 2-SAT 解的 (這題也有其他做法),且我覺得這題的 2-SAT 的運用方式非常好,於是想把它變成擷取精華變成其他題,於是就生出了這題:2014 TCO Algorithm Celebrity Match, Level Three。把它加入平面座標,以及 binary search 等元素。應該很難和我 idea 的來源題目聯想在一起吧 ...?

  再另外一個例子是 Codeforces 515 E。這題實際上我是從 IOI 2008 Islands 改編的,但它整個模樣都被我破壞掉了,從一個徹底的圖論題變成一個徹底的資料結構題,大家能找到這兩題的相似之處嘛 XD

  再回到有人問我的問題:如何針對一個演算法,創造出一個難題或好題?

  由我自己的例子來當做答案,那答案就是:去尋找該演算法你所認為的好題,然後去進行大規模的改造。

出題的傷心事

  出題還是會預到很多挫折的,例如說自己覺得題目出的很好很難,可是在別人眼裡看來卻是相當直覺相當簡單,或是被認為和某些已存在的題目太像。有一場 SRM 我出的 Div.1 Hard,比賽結束後,有人在 Codeforces 說他以前在其他地方出過一模一樣的題目。我看到後整個崩潰。現今全球性和地方性的比賽加總起來,我相信一年全世界的題目產出量應該有幾萬題吧?若真的有相同的題目由不同的人想出,也是很有可能的。

  出題出太多時也容易自我感覺良好,可能會讓自己對題目的難度失焦,這個時候或許就要多和其他人討論,多問問看其他人的意見,來平衡一下自己的感覺。最近我就覺得我對題目的直覺與否的感覺完全跑掉了 Orz

前人種樹,後人乘涼

  為什麼我卸下培訓班助教後還是一直出題呢?我覺得我是受黃上恩 (卡恩, aka tmt514) 學長的影響吧,當初我在當助教時,學長就主動的幫我們出了好多題目,而且好多題目都超難的!就覺得學長能出這麼多難題好厲害。並且學長也私底下辦了飲料盃比賽,還自掏腰包買獎品,雖然參賽人數有點少,可是相信有參加的人都玩的很盡興。有人這麼做,而且成功了,那我何不也來玩玩看呢?

第二屆飲料盃要來囉~

  這篇就以宣傳 tmt514 下個月要辦的飲料盃做結吧~請參考 FB活動,沒有 NTUJ 帳號的人也可以向 tmt514 聯絡取得臨時帳號~一起來共襄盛舉吧!

2015年4月15日 星期三

Codeforces Round #299 (Div. 1)

這場官方 Editorial 賽後馬上就公佈了,而且寫非常仔細。

點我連到官方 Editorial

比完這場我有一個關於閱讀題目的小感想:當題目敘述裡面出現我沒見過的名字時(如:Tavas、Karafs),會使我讀題目讀得很不順,每看到那些名字就會卡一下...

Problem A --- Tavas and Karafs

題意:有一個無限長的等差數列,首項為 $A$,公差為 $B$。共有 $n$ 組詢問,每組詢問包含三個正整數 $l, t, m$ 。對於每個詢問,請找出最大的 $r$,使得我們能執行至多 $t$ 次中括號內操作 --- [ 在數列裡把至多 $m$ 個相異數減 $1$ ],使得數列第 $l$ 至第 $r$ 個數都不超過 $0$。

數據範圍:$1 \leq A, B \leq 10^6$ , $1 \leq n \leq 10^5$

tag:[ 貪心 ] [數學]

關鍵字:度序列
= = = = = = = = = = = = = = =
引理:無論是否為等差序列,一個序列 $h_1, h_2, ... , h_n$ 能滿足題目的條件的衝要條件為:$\max (h_1, h_2, ... , h_n) \leq t$ 以及 $\sum{h_i} \leq  m * t$。

由於對於任意詢問,若把 index $x$ 選為右界能滿足題目條件,則對於所有 index $i$ 滿足 $l \leq i \leq x$,也一定能滿足條件。所以就可以使用 binary search 了。
數據範圍有特別設計,讓你 binary search 時的運算不會超過 long long,不過你還是得小心一點,binary search 時的右界不能設太大。

關於這個引理的證明,可以使用數學歸納法,請直接參考 tutorial 吧。

我覺得這題的概念和簡單二分圗的度序列判別很像,證明也很像。我們可以把引理的問題想像成這樣:
  有一個二分圗,已知二分圗其中一邊有 $t$ 個點,每個點的度數 (degree) 都是 $m$;令一邊則有 $n + m*t - \sum{h_i}$ 個點,當中的 $n$ 個點度數分別是 $h_1 \sim h_n$ ,剩下的點度數都是 $1$。而這樣的圗會是簡單圗的充要條件就是 $\max (h_1, h_2, ... , h_n) \leq t$。

給定二分圗或一般圗的度序列問是否否存在一個簡單圗滿足這樣的度序列,是可以很有效率解決的問題,有興趣的話可以 google 看看可參考 wiki:degree sequenceHavel - Hakimi algorithm

二分圗度序列判定的題目:CEOI 2010 Bodyguards

Problem B --- Tavas and Malekas

題意:有兩個字串 $s$ 和 $p$ ,已知 $s$ 字串的 index $y_1$ , $y_2$ , ... , $y_m$ 開始長度和 $p$ 字串一樣長的 substring 和 $p$ 一樣 (有可能還有其他一樣的位置,不一定全列給你),問 $s$ 有多少種可能?

數據範圍:字串長度皆不超過 $10^6$。

tag: [ 字串比對 ]

= = = = = = = = = = = = = = =
這題就只是個字串比對的練習題,我覺得沒有比較特別的地方。

除了某些位置的字母題目已給定,其他位置都可以'a' ~ 'z' 隨便填,答案會是 $26^K$,$K$ 是無法從題目得知字元是什麼的位置數。

所以這題的解題分成兩部分: 1. 快速的填入所有已知的位置 (要填下一個子字串時,直接忽略已經填過字母的位置) 2. 重新驗證所有 $y_i$ 開始的子字串是否和 $p$  一樣,這部分可以用任意字串比對的方法做到。

Problem C --- Tavas and Pashmaks

題意:有一個競賽包含游泳 $x$ 距離和跑步 $y$ 距離,有 $n$ 位參賽者,給定這 $n$ 位參賽者的泳速和跑步速度,請問在我們不知道 $x$ 和 $y$ 的實際值的狀況下,有哪些人可能第一名 (和其他人同時到達算是並列第一),輸出請按照所有人的邊號輸出。

數據範圍: $1 \leq n \leq 10^5$,所有速度為不大於 $10^4$ 的正整數。

tag:[ 計算幾合 ]

關鍵字:三項鐵人
= = = = = = = = = = = = = = =
這題...我以前見過更複雜的版本(POJ 1755 Triathlon,有三項運動,可以輕鬆搜到一堆題解),兩項運動的也有見過其他類題但找不到了。我想這題題解講的非常仔細我就不說了。

是說賽中我想都沒想,只憑記憶覺得似乎和凸包有關,就亂猜了一個做法結果 WA 了 OAQ。

Problem D --- Tavas in Kansas

題意:有一個無向圗,每個點有一個整數權重, Tavas 和 Nafas 用這個圖玩一個遊戲。Tavas位於 $s$ , Nafas 位於 $v$。遊戲如下:兩人輪流, Tavas 先,輪到的人要選一個值 $x$,並標記所有與自己的點距離不超過 $x$ 且尚未標記的點,並獲得所標記的所有點的權重和當做分數,至少要標記一個點。直到所有點都被標記後遊戲結束。在所有人採最佳策略下,誰會嬴(或平手)。

數據範圍:圖的點數不超過 $2000$,邊數不超過 $10^5$,圖是連通的。點的權重絕對值不超過 $10^9$。

tag: [ 最短路 ] [ dp ]

= = = = = = = = = = = = = = =
這題的圖啊根本是多餘資訊,我們只要保留每個點的到 $s$ 、 $t$ 的最短路距離的值就夠了,把這些距離離散化後,就可以開二為記憶體來 dp 。最直覺得 dp 是 O(n^3),當可以改進成 O(n^2),細節請參考官方 Editorial 吧,還蠻詳細的。

我有一個建議:當不知道要怎麼改進複雜度時,把 dp 時的轉移式寫下來用眼睛觀察可能就嘿知道要怎麼改進了。(雖然說這題我讀完題就知道怎麼改進複雜度了,但最後有些地方要開 long long但我只用 int 就爆炸了 OAQ。)

Problem E --- Tavas on the Path

題意:給一個樹,每個邊都有個值。定義一個 fuction $T$,input 為一個 01 字串 $s$,$s$ 有 $m$ 個連續的 $1$ 的區塊,第 $i$ 個區塊有 $e_i$ 個 $1$,則 T 的 output 為 $\sum_i{f_{e_i}}$ ($f_i$ 是給定的值)。現在有 $q$ 個 query,每個 query包含三個樹 $v, u, l$,請回答兩端點為 $v, u$ 的路徑上,若邊的值 $\geq l$ 則視為 '1',否則視為 '0',把這些字元按照路徑上的順序接起來,代入 function $T$,請輸出 output。

數據範圍:$1 \leq q \leq 10^5$,$2 \leq n \leq 10^5$,$| f_i | \leq 1000$,$1 \leq$ 邊的長度 $\leq 10^9$。

關鍵字:[ 樹鍊剖分 ]

= = = = = = = = = = = = = = =

這題看完大概就知道他是樹鍊剖分的題目,英文叫做 heavy-light decomposition。請 google 可以查到非常多資訊。

簡單來說,就是把 tree 拆成很多 path,讓每個詢問都只會通過 O( log n ) 個 path,並在每個 path 上用線段樹解決部分問題。也就是說,你如果會用線段樹解決 Tree 退化成 Path 的狀況,就可以用樹鍊剖分來多一個 $log$ $n$ 解決問題了。細節請參考官方 Editorial。

2015年4月13日 星期一

針對本BLOG的問卷調查



我自認是演算法競賽的愛好者,也許「愛好者」這個詞太好聽了,大概要說成「成癮者」吧...對我來說,參加線上演算法競賽的感覺,就如同普遍的人在打 LOL、魔獸之類的遊戲的感覺吧。

但自從動畫不起眼女主角培育法在一月撥出後,我深受其內容感動,覺得自己都當了那麼久的消費者了,不如當一下生產者吧!希望能對台灣的演算法競賽界能有所貢獻。於是就心血來潮,決定寫下自己所參加的每場 SRM 和 Codeforces 比賽的解題報告。

寫 BLOG 至今已經過了三個月了,只有漏掉兩三場左右吧,效率還算蠻高的。但有時會這樣想:「我寫這些題解能對大家有所幫助嗎?比起寫這些題解,是否有其他方式能給予台灣的演算法競賽的愛好者們更多幫助呢?畢竟這些題目的題解官網都有了。」大家有和我類似的感覺嗎?

現在覺得,與其閉門造車,不如問問大家的意見吧,我建立了以下的問卷調查,希望大家能把自己期待在 BLOG 裡看到什麼和我說說,甚至歡迎提供一些很瘋狂的主意(請參考問卷解說),預先謝謝大家 m(_ _)m。

問卷連結在此:http://goo.gl/forms/QlXF0zEz48

2015年4月12日 星期日

Codeforces Round #298 (Div. 2)

這場的題目敘述偏長有些題目都是閱讀題 ( 要自己根據題目發生的事件來判斷有哪些限制,如 pB 和 pD ),對英文不好的人大概很吃力吧 ...

Problem A --- Exam

題意:給找出正整數 $1 \sim N$ 的最大的 subset,使得可以把這個 subset 的所有數排成一列,使得相鄰兩個數的差的絕對值都不是 1,並給出任一種排列方法。
數據範圍:$N \leq 5000$。

tag:[構造]

= = = = = = = = = = = = = = =
身為 Div 2 A 的構造題,應該就是個隨便亂構造都構造的出來的東西吧?合理猜測大部分的 $N$ 值都有辦法找到一個 $1 \sim N$ 的排列滿題目條件,只有 $N = 2, 3$ 時例外。

我除了特例以外的構造方法可直接參考我的 code

Problem B --- Covered Path

題意:有一台車共行駛 $t$ 秒,第 $1$ 秒的速度是 $v_1$,第 $t$ 秒的速度是 $v_2$。每一秒內的速度都是等速,相鄰兩秒的速度差至多為 $d$,請問這 $t$ 秒鐘最長的可能行駛距離是多少?

數據範圍: $1 \leq v_1, v_2 \leq 100$,$2 \leq t \leq 100$,$1 \leq d \leq 10$

tag:[ 數學 ] [ 物理 ]

關鍵字:斜率
= = = = = = = = = = = = = = =
某種程度這題算是閱讀題吧?要確實理解題目所說的物理意義。若把此題的物理意義移除,則會變成:有 $t$ 個數 $a_1, a_2, \cdots , a_n$,已知$a_1 = v_1$,$a_t = t_2$,任相鄰兩數差都不超過 $d$,請問所有數的總合最大是多少? (你若問要是速度出現負數也能這樣轉變題目嗎?我並不清楚,題目關於速度是負的似乎沒寫清楚要怎麼考慮這樣的狀況。)

轉換完題目後就比較好思考了。我們會希望每個數愈大愈好,考慮 $a_1$ 及 $a_t$ 對所有其他數產生的限制會得到不等式: $a_i \leq a_1 + d * (i-1)$ 以及 $a_i \leq a_t + d * (t-i)$。並且直接令 $a_i = \min(a_i + d * (i-1), a_t + d * (t-i))$會滿足題目條件,於是得到能使這 $t$ 個數總合最大的序列了。

這個解法其實是很常見的概念,我印象中 SRM中 Div1 Easy 裡根本有簡化後一模一樣的題目。

另外,由於這題的數據很小,所以也可以使用 dp 來做,$dp[x][y]$ 用來儲存 時間 $x$ 速度為 $v$ 時從時間 $1$ 至時間 $x$ 所能行駛的最長距離。

Problem C --- Polycarpus' Dice

題意:有 $n$ 個骰子,第 $i$ 個骰子的可能結果為 $1 \sim d_i$ ,已知擲出來的骰子結果為 $A$,請對每個骰子輸出一定不可能骰出的點數有幾種。

數據範圍: $n \leq 200,000$,$1 \leq d_i \leq 10^6$,$n \leq A \leq d_1 + d_2 + \cdots + d_n$。

tag:[ 貪心 ]

= = = = = = = = = = = = = = =
個人覺得這題比 B 還要簡單耶?可是 B 的 AC人數還是多很多。這題 pretest沒有會爆 int 的測資,所以可以 hack 到大量只開 int 的解。

對於一個骰子,不難想像他可能骰出的值的範圍是連續的,所以只要求出他最低可能值和最高的可能值就結束了。最高的可能值就是其他骰子的值盡可能小的時候,也就是 $\min (d_i, A-(n-1))$,而最低的可能值則是其他骰子的值盡可能大時,也就是 $\max (1, A-(\sum_{x=1}^n{d_x}) + d_i)$

Problem D --- Handshakes

題意:有一個資訊競賽活動,每個新進場的人都要和在場的所有沒有正在比賽的人握手,且任何時刻在場的任三個人都有可能組成隊伍並開始比賽,直到活動結束,在活動結束前不會有任何人離開會場。給你每個人進場時各和多少數量的人握手,請判斷給你的資訊是否有某種符合的所有人進場順序,若有,請給出一組解。

數據範圍:人數不超過 $2*10^5$。

tag:[ 貪心 ]
= = = = = = = = = = = = = = =
這題我看了大家的 code 後發現有各種做法,我就講一下最多人使用同時也是我使用的方法。

一樣先簡化一下題目,把他變成比較正統的數學描述方法。
若把這些人的握手數按照進場順序寫下來($d_1 \sim d_n$),必須滿足以下三個條件:

1. $d_1 = 0$
2. $d_i % 3 = (i-1) % 3$
3. $d_{i+1} \leq d_i + 1$

我想了一下下後直覺告訴我這題是貪心的題目,若要使用貪心,一個很常見的方法就是,每次決定下一個數時,直接選擇最大的可以用的數,而在這題這樣子做會是對的,而且將有很好的複雜度。

實作方式如下:
1. 設一變數 $v$ 代表我們想要取的值,初始值為 $0$。
2. 若存在握手數為 $v$ 的人,則把他當作下一個進場的人,並且把 $v$ 值加一。
3. 否則把 $v$ 值減 $3$ 並回到步驟 2,若還沒取到 $n$ 個人 $v$ 值就變為負,則答案為 Impossible。
 可參考第一名的 code。

我們不需要擔心步驟 3 執行太多次,因為所有過程 $v$ 的減少量不會超過 $v$ 的增加量加二,而會增加 $v$ 值的步驟 2只會執行至多 $n$ 次,且每次只加一。

至於此方法的正確性嘛 ...有一類的貪心法證明是長這樣:若存在某個解答長的和我們構造出來的的不一樣,一定有辦法經過一些變換變成和我們構造出來的一樣,於是若存在解則我們的構造法一定也能找到解!

於是我們先假設,我們若找出的解答,則會是 $d_1, d_2, \cdots, d_n$,以及現在存在另外一組解答為 $a_1, a_2, \cdots, a_n$。
若序列 a 和序列 d 不同,必有一最小的 index $i$ 使得 $d_i \neq a_i$,並且由於 $d_i$ 是可以挑的最大的數,所以我們可確定 $d_i > a_i$,接著我們令 $j$ 為大於 $i$ 的最小的 index 使得 $a_j = d_i$,接下來我們想要選一個 index $k$,使得我們能把序列 $a$ 的第 $i$ 個數至第 $i+k-j$個數整段能無痛的和 第 $j$ 個數至第 $k$ 個數交換。舉個實例:

$d$ 序列為 0,1,2,3,4,5,6,1,2,3,1
$a$ 序列為 0,1,2,3,1,2,3,4,5,6,1

則 $a$ 序列和 $d$ 序列第一個不同的數的位置是 4,並且在 $a$ 序列中 $d_4 = 4$ 這個數下一次出現的位置是 $a_7$,而我們發現我麼可以把藍色這段和紅色這段交換就變成 $d$序列了!分 case 討論後可以證明,令交換的子序列為最長的子序列,滿足 紅色子序列的所有數比對應到的藍色子序列的數都還要來的大(嚴格),則一定可以交換。(我覺得兩個子序列緊接在一起的 case 並不太好證。但總之我確實把所有 case 都證過了。)

實際上並無法總是只交換一次就把 $a$ 序列變成 $d$ 序列,必須交換數次才能讓同樣的 prefix長度增加為序列長度。

徵求精減的證明 >_<。

Problem E --- Berland Local Positioning System

題意:公車站共有 $n$ 站,公車會從第 $1$ 站出發直到第 $n$ 站,再折返回第 $1$ 站,並一直反覆。有一個人他把上車到下車時所經過的所有站的編號記下來 (包括首尾站,並且他可能繞了好幾圈才下車),但你只知道這些邊號排序後的結果,給你每站之間的距離,請問你是否能確定這個人搭了多長距離的公車?

數據範圍: $n \leq 2*10^5$,給的編號序列一定合法,序列長度為 $m$ ($1 \leq m \leq 4*10^5$)

tag:[ 模擬 ] [ 兩個指標 ]

= = = = = = = = = = = = = = =
賽中我花在 hack 的時間太久,回來寫這題時已經來不及寫不完了@@賽後也懶的寫完...

我想到的方法如下:

令 $d_i$ 為數字 $i$ 在序列中出現幾次,則任意合法路段,把序列 $d$ 按照連續相同的數字分段,一定不會太多段。於是我們可以用一些 tuple $(L ,R ,num)$ 來代表邊號 $L \sim R$ 的公車站都個別出現 $num$ 次。

所以我們就枚舉搭公車的起點,在枚舉開始方像為左或右,由於我們知道他搭公車的站數為 $m$,所以可以快速求出上一段所說的行式,就可以比對看看和這個人所搭的公車有沒有一樣。一樣的話就可以檢驗此種公車路線長度是否和至今合法的路線長度都一樣。

這個做法細節想起來有點複雜,會令人不想寫下去,,,

現在我們再多想一點點。

若先隨便選個點當起點,並經過 $m$個站,我們就得到了其中一種經過 $m$ 佔的公車路線。接著,我們只要把此路線的起點向前移一站,同時也把終點向前移一站,就得到另外一個公車路線了!共移 $2n-3$ 次就可以把所有可能的公車路線都試過了 =口=

於是我們可以輕鬆的使用 map 等資料結構來記錄路線的狀態有沒有和題目所給的序列一樣。

以上第二個方法是我看了第一名的 code 才發現的。

Problem F ---  Simplified Nonogram

題意:Nonogram是個類似數讀的遊戲,以一個 $n*m$的表格,請你把每一個都塗成黑色或白色,使得每一行及每一列連續的黑格段數都和測資指定的一樣。任一種填法皆可。

數據範圍:$1 \leq n \leq 5$,$1 \leq m \leq 20$。

tag:[ DP ]

= = = = = = = = = = = = = = =
我看到這題就立刻聯想到我在 SRM655 出的 Div.2 Hard,畢竟數據範圍長的那麼像...,於是我就直接從 dp 的方向去思考了。這題比我出的那題麻煩,還要輸出解...,很難讓不同層的 dp 共用記憶體。我用來儲存代表每一列的狀態數有 $21$ 那麼大,記憶體若要開 $21^5 * 20 * 2$ 不知道是否開的起來...,但我想說應該亂寫都會過吧,就不開陣列來 dp 而直接使用 STL 的 map。但寫完後使用 Codeforces 的 Custem Invocation 測了一下發現會 TLE ... 最後靠著 "用非常多map代替一個 map" 以及 "一定沒有必要走到的 status 都不要塞到 map裡" 就 AC 了。其實應該只需要靠第二個方法,因為它能減少大量的狀態數。

賽後開了別人的 code 發現,直接開陣列記憶體其實有辦法開的起來,,, (只是要想辦法只使用bool 或 char)。

我 dp 的方式是以 column 的順序 dp,每加一個 column 就更新每一個 row 的狀態,每個 row 的狀態有:已有幾條連續的黑格,以及最後一個是黑的還白的。應該算是平淡無奇吧?就狀態維度有點多令人感到有點煩而已。

而我所位的一定沒有必要走到的狀態是指:若存在某一個 row ,後面無論如何塗黑白格都無法達成目標的狀態。

2015年4月5日 星期日

ZeptoLab Code Rush 2015

這場比賽是 Div.1 和 Div. 2 一起比的,而且共有七題,比 2.5 個小時。

賽中我只寫了前四題 OAQ 賽後賭氣似的把所有題目都寫了一遍,所以這算是近期頭一場我真的有親自寫過所有題目的Div. 1 Codeforces Round。

點我連到官方 Editorial

problem A --- King of Thieves

題意:給一個僅包含 '*' 和 '.' 的字串,請問是否存在恰 $5$ 個 '*',他們的位置是成等差數列。

數據範圍:字串長度不超過 $100$。

tag:[ 模擬 ]

= = = = = = = = = = = = = = =
有各種做法,我的做法是枚舉等差數列的開頭位置和公差,逐一判斷。

Problem B --- Om Nom and Dark Park

題意:給一個完全二元樹,每個邊上都有一個正整數的權重,現在你要把一些邊的權重加上一個正數,使得所有 root 到 leaf 上的的路徑權重合都相同,請問所有邊要增加的值至少多要多少?

數據範圍:樹的深度至多為 $11$。

tag:[ 貪心 ]

= = = = = = = = = = = = = = =
tag 設為 [貪心] 可能有點怪怪的,還是要把他當作數學啊?

從 root 到每個 leaf 的路徑上權重合都一樣,可推得給定任一點 $x$,則 $x$ 到所有在他 subtree 下的 leaf 的路徑上的權重合也都一樣。所以我們難免想要從比較小的 subtree 先考慮。

使用數學歸納法的方式去思考:
現在我們先考慮只有三個點的完全二元樹,他只有兩個邊,根據條件這兩個邊值必須相同,那顯然最好的情況就是把比較小的那個邊加上兩個邊的權重差的絕對值。

接著我們考慮有 $2^n-1$ 個點的完全二元樹,我們先個別把 root 的左子樹和右子樹(也就是大小為 $2^{n-1}-1$)用遞推的方式各別解決,然後把 左/右 子樹的 root 到 leaf 的路徑權重合加進 root 連到 左/右 子樹的邊裡,把他想像成只有三個點的完全二元樹去解決就行了。

所以這題的時間複雜度是 $O(n)$。

Problem C --- Om Nom and Candies

題意:給五個正整數 $C,x1,v1,x2,v2$ ,請求出非負整數 $a,b$ 滿足 $a*x1+b*x2 \leq C$ 且 $a*v1 + b*v2$ 最大。

數據範圍:所有數不超過 $10^9$。

tag:[ 數學 ]

關鍵字:根號
= = = = = = = = = = = = = = =
這是個很常見的題目,例如說曾出現在 2011年上海的 ICPC regional,所以應該是一堆人都見過的題目,我也曾經很仔細的想過這題,印象中實際上可以做到 O(log(數據範圍))。我隨意找了一個 Blog大家參考看看根號數據範圍的做法吧。

而且 code 可以寫的非常簡短:rng_58 的 code (rng_58的說明)

Problem D --- Om Nom and Necklace

題意:給一個字串和一個正整數 $k$,問有哪些長度的 prefix 是形如 $A_0B_1A_1B_2A_2..A_k$,其中所有 $A_i$都是相同字串,所有 $B_i$ 也是相同字串,且 $A_i$ 和 $B_i$都可以是空字串。

數據範圍:字串長度不超過 $1,000,000$。

tag:[ 字串匹配 ]

= = = = = = = = = = = = = = =
賽中我看完題目後,列了一些字串就直接猜到結論了。所是用猜的,但也並不難證明。

結論:所有滿足題間的 prefix,都是某個基本的字串 $s$ 重覆貼個 $k \sim k+1$ 次貼出來的,貼的第 $k+1$ 次可以只貼 $s$ 的 prefix,例如說 $s = "abc",k = 2$ ,那麼貼出來的字串可以是 $abcabc$、$abcabca$、$abcabcab$、$abcabcabc$ 四種。

證明分兩個方向,首先,若把 $A_iB_{i+1}$ 視為 $s$,則可推論所有滿足題目條件的 prefix 都一定由某個字串貼出來。接著令一個方向,設 $s$ 長度為 $L$,且貼的第 $k+1$ 次貼的長度為 $r$ ,則令 $A_i$ 為 $s$ 長度為 $r$ 的 prefix, $B_i$ 為剩餘部分,就能證出所有由 $s$ 貼出來的字串都會是滿足題目條件的 prefix。

知道了這件事後要怎麼做呢?

作法大至上分為 Hash 派、kmp 派、Z algorithm 派。
我不喜歡 Hash,因為 Hash有可能會被像我一樣的邪惡人士構造測資而被 hack,我也不喜歡 kmp,我覺得 kmp 很深奧 0.0 所以這類的題目我都使用 z algorithm。

使用 Z algorithm 後可以知道對於字串 $S$ 的每個 index $i$ ($0$ - base),都能求出最大的 $Z_i$ 使得 $S[0...Z_i-1] = S[i...i+Z_i-1]$。
如此一來我們就可以知道當 $s$ 長度選作 $i$ 時,可以貼出的長度有哪些了。

Problem E --- Transmitting Levels

題意:給 $n$ 個正整數 $a_1, a_2, ... , a_n$,這 $n$ 個正整數是環狀排列的。有 $q$ 個詢問,每次詢問會給一個 值 $b$,問要如何把這 $n$ 個數切成盡量少段,使得每一段數字和都不超過 $b$。

數據範圍: $n \leq 1,000,000$,$q \leq 50$,$a_i \leq 10^9$,$b \leq 10^15$。

tag: [ 貪心 ]

關鍵字:環狀貪心
= = = = = = = = = = = = = = =

如果不是環狀,這題大概只有 Div.2 pB 的程度而已,只要從最左邊開始,每一段都取盡可能的長,不能再取時就把下個樹當作下一段的開頭。

變成環狀後要怎麼處理呢?直覺的方法就是枚舉開頭位置,然後作和非環狀一樣的事,但這樣顯然太慢了。

首先,至少我們都能夠 $O(n)$ 預處理求出,由每個 index $i$ 當開頭,最長的一段能多長(暢度記為 $l_i$ )。

接著,以下提供三種思路:

1.
無論從哪個位置開始,總是有一個時候會跨過第 $n$ 個數和第一個數之間 (我們把某一段恰結束在第 $n$個位置也列入考慮),並且,我們就直接把跨過去的那一段當作最後一段。

若這樣想的話,我們就可以從後面 dp 回來了!dp 時要記錄兩個值,分別是,由某個位置當作開頭貪心去分段,要分段直到跨過去時,共分了幾段,以及最後一段結尾的位置。如果某個位置至結尾位置長度為 $n$ 以上,那我們就更新答案。此做法應該是相當好想好寫的一種。

關於這個做法,我覺得正確性並不明顯,有人和我相同感覺嗎@@?

2.
把 $l_i$ 最小的那一段挑出來(記長度為 $L$ ),那麼無論從哪裡當作起點 greedy,一定會跨過該段,所以我們就不妨直接枚舉那一段每個位置當作起點 greedy 去劃分段落,由於每一段長度都至少為 $L$,所以至多只需要 $O(n/L)$ 就可以知道由某個位至當作起點答案是多少,總共枚舉 $L$ 次,故每個詢問時間複雜度都是 $O(n)$ 。

這是Editorial 給的方法。

3.
若現在不是問你最小的環狀分段法,而是問你從所有位置切下去變成不是環狀後,最小的分段法個是如何。那麼以上兩個方法都不能用了。而這個方法仍可解決,但多了 union find 的時間複雜度。

首先把這 $n$ 個數字重複共貼 $3$ 遍,例如說 $1, 2, 3$ 就會變成 $1, 2, 3, 1, 2, 3, 1, 2, 3$。

以 $b = 4$ 作舉例,我們把所有 index 都當成是一個點,並且每個點都會向右連出去一條邊,連到以該 index 為起點,最長的段落能到達的右界的點,如下圗:

若一直把 $n$ 個數貼下去,將會是個無限大的有向森林。

我們若有知道從某個數當開頭,至少要幾要切成幾個段落,就等於在這張圖上問,從某個點當起點,至少要經過幾條邊才會跨過至少 $n$ 個點。

現在問們要使用 Union Find 來解決這個問題。在 Union Find 的過程中,我們還得記錄每個點到其所在 group 最遠的點的用通過的邊數。

Union Find的順序就由左到右一個一個加把邊兩個端點 Union 起來,以上圗來說,就是綠邊 => 藍邊 => 紅邊 => 綠邊 => 紅邊 => 藍邊的順序。我們只須考慮前 $2n$ 條邊。並且當我們union完第 $k$ 條邊時,我們就會發現第 $k-n+1$ 個點所記錄的到該 group 最遠的那個點所需的邊數,就會是由該點所代表的數開始當第一段,greedy 出來的答案。

Problem F --- Pudding Monsters

題意:在 $n*n$ 的表格中,每行每列都恰有一個擺有布丁,問有多少 $k*k$ 的子表格,也是每行每列恰有一個布丁($k$ 可以是任意數)?

數據範圍: $1 \leq n \leq 3*10^5$。

關鍵字:[ D&C ] [ 資料結構 ]

= = = = = = = = = = = = = = =

唔... 關於這題的解法我沒有特別想講什麼...,我賽後寫的方法完全參考 Editorial。

我賽中一直往資料結構的方向去想,可是我的腦袋對稍微複雜的資料結構實在是沒轍,但賽後看到了另外一個關鍵字:[ Divide and Conquer ] 就如同吸血鬼被打樁一樣... 因為我連想到了這題: sgu 512 Friendly Points,以 D&C 的做法而言這兩題超像啊....,同時 friendly Points 的類題也是日本 JOI 2013/2014 三模的題目かかし (日文解答)。過去雖然我知道有這麼一題存在,可是從來沒有寫過 Orz。

Problem G --- Spiders Evil Plan

題意:給一個每邊都有給長度的 Tree,有好多個詢問,每個詢問有兩個數 $x, y$,你必須回答,至多 $y$ 條 path 所覆蓋的聯通的邊集,且包含點 $x$,則邊集的總長度最大為多少?每個詢問回答玩才能得知下個詢問是什麼。

數據範圍:點數、詢問數不超過 $10^5$。

tag:[ 貪心 ]

= = = = = = = = = = = = = = =
我賽後才看了這題的題目,看完題目後的感想:這題不就是 POI 的題目在稍微變化一下而以嘛 = = 如果我在賽中看了這題而且 pretest 夠強的話應該能在賽中 AC 吧 @@
POI的相關題目是 POI 13th  stage 2 Subway,也可以參考 HOJ 101 捷運路線,和這題的差別就是沒有多組詢問,也沒有一定要包含某個點 $x$ 的條件。

有沒有做過 POI 那題真的對思考這題的時間差很多,另外 POI那題也和 Codeforces gym100020裡的 pH --- Tree 大有關係。Tree 這題問的是,給一個有根數,每次可以從root問某個葉子走下去並把所有邊塗色,問塗 $k$ 次至多能讓多少邊被塗上顏色。我會說 Tree 這題是 POI subway 的簡化版。

關於捷運路線這題可參考 這裡

接下來我要說的是我解這題的方法的概念,實作細節我就不提了...

首先,把樹的中心求出來當作根,接著從找出離跟最遠的葉子,並把根連到葉子的路徑拔掉,之後會變成森林,在一值重複把森林中跟到葉子最遠的路徑拔掉,直到所有邊都拔完為止。如右圖,整張圖就被分成了 $8$ 條路徑。

對於每個詢問 $x, y$,如果點 $x$ 包含在最長的前 $2y$ 條路徑裡面,那麼答案就是前 $2y$條的路徑和。
否則我們就強制在最長的前 $2y$條路徑中,在多連一條與前 $2y$ 條路徑包括 $x$ 的最長路徑,如下圖, $y = 2$,最長的四條為非黑色的路徑,點$x$是圖上標記的紅色的點。顧我們把紅點連到綠點的綠色路徑也加進去,於是目前就滿足了包括點 $x$ 的條件,但是現在多了一條路徑,於是我們必須要刪除一條路徑,而刪除的路徑我們只須考慮兩種選擇,第一種是藍色路徑綠點一下的半截,第二種事原本 $2y$ 條路徑中最短的那條(紫色路徑)。

我想這個做法是非常直覺的,但證明和實作上就必須加把努力囉。

2015年4月1日 星期三

比賽debug側記---把自己的思緒說給別人聽的好處

這篇也是紀錄有關某場比賽的事,不過只特別記錄其中一件插曲。

應該有不少人都聽過黃色小鴨除錯法吧?我個人相信這招對 debug 真的很有用,由其是在正式比賽中心浮氣躁的情況下用這招效果更是顯著 (把隊友當成黃色小鴨之類的),常參加團隊比賽的人或許多少都有這種經驗:當自己debug許久但都找不到bug,於是就要把自己的作法說給隊友聽,請隊友幫忙debug,但說著說著忽然自己就發現 bug 了!這個時候,其實你的隊友的地位就和黃色小鴨一樣而已XD畢竟他什麼都還沒做,只是在用耳朵聽你說。

3/29(日) 受人邀請組隊參加了 UTPC,是個主要給日本人參加的比賽(題目都用日語),不過藉由翻譯功能,多少還是能看得懂題目,並且真的讀不懂的地方可以向日本人的隊友確認。

但這場比賽我的表現實在欠佳,不知是太久沒比團隊比賽還是對第一次組的隊伍不習慣,總之這場我只寫了兩題 pD,和 pH,不過隊友們很罩就是了,最後還使勉強上了記分版上的第三名,唉唉不過大家看到我們這隊的組成應該還是會覺得比的不夠好吧 XD

這場比賽題目共分成 100 分、200 分、300 分三種,照記分版來看 pD 應該是 200 分以下最麻煩的一題,但實際上難度頂多只有 SRM Div.1 500或Codeforces Div.1 pC 左右吧,這裡就不提他了,我要談的題目是 pH --- 回すだけ,是個互動題。整場比賽我花了將近兩個半小時在上面 ...

題意:平面座標上有一個凸多邊行,其中一個頂點座標是 (0, 0),其他頂點座標你都不知道,你只確定它至多 $10$ 個頂點,每個頂點座標皆為整數,並且所有內角都在 170 度以下。現在你可以問至多 $1000$ 個問題,每個問題都形如下:"把此多邊行繞著原點逆時針轉 $x$ 度後,y座標的最大值是多少?"

互動格式:當要問問題的時候,以一個 '?' 加一個空白作開頭,後面接一個浮點數 $x$ 代表你所問的問題中的 $x$。當要回報答案時,答案有 $n+1$ 行 (n為凸多邊形頂點座標),每行都以 '!' 加一個空白做開頭,第一行僅包含一個數 $n$,第二行之後,由 (0, 0) 開始往逆時針回報所有頂點座標。

這題應該不太難,我想了幾秒就想到一個做法:每一個詢問等於我們可以知道這個凸多邊形在哪個半平面裡,並且我們若以 $1$ 度為間隔詢問 $360$ 次以上,那麼原本的凸多邊形頂點,一定在這$360$ 次詢問所得到的半平面的交集的凸多邊形頂點上。那我們就大膽的相信,求半平面交後的凸多邊形上的所有整數座標頂點搜集起來後,就是答案。

實際上有更精簡的做法,不需要使用半平面交,只需要求線段交點就有辦法得到答案,但這裡就不提了,畢竟我的重點是在於這題的 debug 。

總之這題就解法而言其實相當單純,但麻煩的就是很難測試自己程式碼的正確性,它的 Sample 很不親切,完全就只有格式上的舉例而已,於是我就把我的程式分區塊,用我自己的方法檢驗其正確性,大致上無誤後就 submit 了,但是卻 WA了 ... 我再仔細看了一次題目,發現要輸出 $n$ 但我沒有輸出,但是我改了這個 bug後還是 WA。

接下來我又測了很多東西,但真的完全找不到錯誤,於是我又完全改寫做法,改用不需要半平面交的做法(畢竟半平面交我是直接使用 codebook ,很擔心 codebook 其實是錯的 Orz),但還是 WA 掉了,甚至拿到 TLE,真的是莫名其妙呀...一直在考慮要不要把互動的 Judge 程式也寫一份來對拍看看是否正確,但是覺得好麻煩就放棄了。

我就這樣測了好久好久 ... 後來隊友來問我這題到底盡展得如何,我就開始向隊友說這題我實際採用的方法,以及我覺得可能出錯的地方和疑點,說著說著我突然發現,問問題時前面要加 '?',但是我卻加成 '!' 啊...該不會我 debug 那麼久就只是因為這樣吧?之後修掉這個 bug 後就 AC 了。並且實驗證時,AC的八十分鐘前上傳的 code也是修掉這個 bug 就能 AC。

真的非常對不起這場比賽的隊友們 OAQ

2015年3月25日 星期三

SRM654ˋ

向來在台灣時間早上的場次或許因為參加的人偏少,題目有偏間單的趨勢,這場也不例外,我難得沒有重大失誤的破台了。不過我每一題都 debug 好久就是了。

這場第一名Endagorion寫的 Editorial

250 --- SquareScores


題意:給一個由小寫字母和問號構成的字串,並且給你問號代表每個字母的機率,並定意一個字串的分數為所有字母都相同的 substring 個數 (不同位置算不同)。求這個字串的分數期望值。

數據範圍:字串長度($n$)不超過 $1000$。

tag:[ 數學 ] [ 期望值 ]

關鍵字:簡單期望值

= = = = = = = = = = = = = = =
就直接運用期望值可以拆開的概念,全部也只有 $n*(n-1)/2$個子字串,若再多考慮每個字串相同的字母是哪個的至多 $26$ 種可能性去枚舉,最裸的做法時間複雜度是 $O(26n^3)$,但是$s[i...j]$ 全為同一個字母的機率可以由 $s[i...j-1]$ O(1) 轉移得知,所以立刻就壓到 $O(26n^2)$ 了。但實際上這題根本可以做到 $O(n)$,大家可以想想看~。這題算是期望值類的老掉牙的題目吧。

450 --- SuccessiveSubtraction2

題意: 給定一個數列 $a_1 \sim a_n$,考慮算式 $a_1 - a_2 - a_3 - ... - a_n$,我們可以至多家上兩組括號,求最大的可能計算結果是多少。

數據範圍:$1 \leq n \leq 2000$,有至多 $2000$個詢問(每個詢問是把上一筆詢問的其中一個數字改成另外一個數字)。

tag:[ dp ]

關鍵字:最大連續和

= = = = = = = = = = = = = = =
自己亂補上刮號就可以發現,補至多兩個括號,等價於把 $a_3 \sim a_n$ 中至多連續的兩段數字正負對調。

這題做法一堆吧,限制非長寬鬆,加上他每筆詢問實際上只有變動一個數字,那應該是可以做到 $O((q+n) log n)$ 的。

我的做法是 dp 做出每個 prefix 和 suffix 的最大連續和,然後枚舉prefix 和 suffix 切開的位置。

這題還有一個有趣的做法(參考此連結的),先找一次最大連續和的一段正負反過來,然後再做一次相同的事就行了。

850 --- TwoEntrances

題意:給一個長的像 Tree 的家,由兩個 node 是家的入口,現在要搬家具進去每個 node,但是能般進去的條件是,由某個入口到該 node 的 path 上都還沒有放入家具,問般家具的順序有幾種?答案 mod $10^9+7$。

數據範圍:邊數不超過 $3000$。

tag :[ dp ] [ 排列組合 ]

關鍵字:燈飾 dp

= = = = = = = = = = = = = = =

私認為這題難度只有 $500$,若入口只有一個,那他就只是一個非常經典的題目,我這個  BLOG 已經出現過了... 請看 CF290 pD

若是這樣的問題相信不少人都見過,但入口兩個要怎麼處理呢?

先畫意張示意圗 :)

黑點是入口,我們想像一下把代表入口的兩個點釘在牆上掛起來,大概就會變成上圖所示。

我們先想想退化的 case,例如說...掛起來後沒有任何點垂下來。我們會發現,這種 case 的話,任何時刻有擺家具的 node 都是連在一起的!於是就給了我一個靈感,我們可以 dp 狀太設成: $dp[l][r]$ 代表 $p_l \sim p_r$間及其垂下來的所有 node 都擺上家具,但其他 node 都沒有的方法數。

至於要怎麼轉移呢?我們可發現,代表 $dp[l][r]$ 的狀態,最後一個擺上家具的位置一定是 $p_l$ 或 $p_r$ 兩者之一,於是我們分別把 $p_l$ 和 $p_r$ 當作 root,然後想像你是怎麼解原始的經典題版本,那應該就會知道要怎麼轉移了 :)


2015年3月23日 星期一

VK Cup 2015 - Round 1

※ 本篇不含題解,只有簡單記錄一下比賽心得,方便以後搜尋及回憶

= = = = = = = = = = = = = =

馬上就毀了不久前說的 V 字形目標 XD

這場比賽無疑是我寫解題報告至今最簡單的一場Div. 1比賽,可是我出太多包了就掛掉了 Orz 總覺得當我有明確目標的時候就一定會爆炸 ... (看看我至今為止進不了任何 online round)。

這場比賽有幾個特殊的地方:1. 難度沒有按照順序排 2. Codeforces 第一次採用以 250 分為間隔的動態分數。

Problem B --- Group Photo 2 (online version)

tag:[ 枚舉 ][ greedy ]
關鍵字:矩形橫擺直擺

賽前我並不知道題目沒有按照難度排,但尤於求攻心切就先開了 pB (自負能以差不多的時間寫完 A 和 B),但是大概是太急躁了 ... 過了三分多鐘我都還沒看懂題目,在想要不要先回來讀 A 的題目時先看了一下 scoreboard,看了感到非常莫名, pA沒有人上傳,倒是 pE 有少數幾隻貓上傳 ... 這時心裡猜想或許 pE 是 well know 的難題才會發生這種事?於是決定繼續試圖理解 pB,終於理解意思後,立刻把這題連想到我曾經在 Topcoder SRM629 出的 Div1 250 都是橫擺或直擺的矩形問一些事情,馬上就會做了。

Problem E --- The Art of Dealing with ATM

tag: [搜索]
關鍵字:零錢

pB 過了 pretest 後看了 scoreboard,發現有大量的人傳了 pE,以及少數人傳 pB,但沒有人傳 p ,於是我開始相信這場難度沒有按照順序排,但看完 pE想了一下後並不知道怎麼做 ...,賽後看了別人 AC 的 code 才發現我看錯題目了。我沒有看到題目說的每次提領的錢至多只能提領兩種幣額的限制,賽中我不時回來思考這題,花了不少時間。

Problem D --- Social Network

tag:[貪心]
關鍵字:區間貪心

雖然 pE 卡住了,但是一直卡下去很不妙,所以就繼續開其他題,這題題目對我來說也是很難讀懂,但也是讀懂後就會做了,而且 code 很簡短,一個 for 迴圈掃過去就結束了。在我感覺上這題只有一般 Div. 1 B 以下的程度。

Problem A --- And Yet Another Bracket Sequence

tag:[字串比對][ 資料結構 ]
關鍵字:合法括弧

這題我也是看完題目後就會做了,但是覺得可能還會有比這題好寫的題目,在寫這題前先去看了 pC。

Problem C --- Rooks and Rectangules

tag:[ offline ] [ 資料結構 ]
關鍵字:矩形區域類資料結構

這題我倒是沒有讀完題就知道怎麼做 ...,應該說我第一個想到的做法有點困難,但看別人 AC這題的速度大概可以知道這題有更簡單的方法,但我覺得比起去思考更簡單的方法,還是去抄抄 codebook 寫 pA 會比較容易。賽後多想個幾分鐘就想到簡單的做法了。

我複製了 suffix array 和線段樹求 RMQ 的 codebook 迅速的寫完 pA, 但是之後一直 WA 在 pretest 第 12 組,直到賽末。賽中一直 de 不出 bug 時超心急的,我已經好久沒有卡 bug 卡那麼久了,我覺得 code 完全有按照我的思考寫啊!當下覺得要不是我想到的做法是錯的,要不然就是我的 codebook 有錯,可是無論重新檢視自己的做法證確性多少次,都還是覺得是對的,並且我那兩份 codebook 都用了好多次了。又重新看了幾次這份 code 我沒抄 codebook 的部分,都找不到錯誤,過程中索性先回去繼續想 pE 轉換情緒幾次,但也都處處碰壁。直到最後,沒有奇蹟。這場比賽我以兩題作收。

事後沉澱下繼續找 bug,當時心想,要是真的是 codebook 有 bug 的話那還蠻糟糕的,所以也幫抄 codebook 的部分 debug,然後就發現我的 bug 了...,原來我的 RMQ codebook 只當所有數是非負才會對 ...,把這部份修過後重上傳,在第 14 組 test TLE 了...,這也太崩潰 Orz 這代表就算我 RMQ 的 codebook 沒有 bug,我也一定無法 AC 這題 ...。難道我的方法太慢了嗎?我看了一下別人的 AC code,複雜度也和我一樣呀!也是一個 suffix array加一個 O(n log n) 的資料結構,我在測了一下我的 code,發現在 suffix array 的部分就 TLE 了 ...,這是怎樣,這已經是過去我把我自己寫的 suffix array code換成對友寫的快我幾倍的 code耶,結果還是不夠快 Orz,最後我去複製了一分別人 AC 的 code 裡的 suffix array 的部分蓋掉我用的 suffix array,終於 AC了。

雖然 rating 大降,不過這場收穫算是很多吧,把我的suffix array codebook 變得更快,以及除掉 codebook 裡的其中一個潛在 bug。不過上一篇 BLOG 裡寫的目標失敗了還是令人非常傷心 OAQ

2015年3月19日 星期四

Codeforces Round #296 (Div. 1)

這場比賽題目也偏簡單 (個人覺得),至少都算是常見的題型(個人覺得),但是仍然沒有人破台。據個人觀察,近一年內很多上古英武有名的參賽者如 tourist 的參賽頻率都變少了,所以這場我才有機會拿到第三名 >_<,要不然你們想想看,如果 tourist、Petr、peter50216、rng_58、WJMZBMR、ACRush之類的高強度且高穩定性的人傾巢而出的話,我不知道要排到第幾名去了 Orz。

在打解題報告之前先附上一張我 dreamoon 這個 id rating 變紅後的走勢圗!


我現在正在企圖描繪一個嚴格遞降再嚴格遞升的V字型,而且希望右端點能比左端點高 XD 究竟下一場能不能做到呢 >_<,可是下一場是 Div.1 only 的 VK Cup - Round 1 的 online mirror,依經驗這樣的比賽參賽者會少,而且厲害的人會變多,這樣很可能會不僅沒有升高,反而使我的 rating 就此跌下去 ... 好想戰略性撤退 Orz,啊啊啊有這種想法的我好沒有骨氣喔 OAQ

順帶一題近年來的 rating 和台灣的物價一樣,上漲很嚴重,所以畫 V 字才沒那麼難,畫 V 字左端時,深紅色以上的人才 18 個人左右,全世界成為深紅色的人不過三十個,但現在當過深紅色的人已經滿街都是了 ...

這場比賽雖然簡單,但是很多題都有不只一種解法值得我一題,要不然原本比完時覺得題目太簡單不想寫這篇的說 XD

要看官方的 editorial 請點我

以下採用倒敘法從最後一題開始

Problem E --- Triangles 3000

題意:給平面上 $N$ 條直線,請問任取三條直線的所圍成的三角形面積期望值。

數據範圍:$e \leq N \leq 3000$,任兩條線不平行,且任兩條直線的交點座標絕對值在 $10^6$ 內。

tag:[ 計算幾何 ]

= = = = = = = = = = = = = = =
由於題目敘述超短,我寫完前三題後是先看這題的,看來這題時限後,我想了一下下馬上想到一個 $O(N^2 log N)$ 的做法,可是覺得並不好寫所以就回去看 pD 了,pD 上傳並放棄掙扎後,只剩下二十出頭分鐘,覺得時間不夠用,所以就去 challenge 別人。

但是賽後發現,我的思考完全被題目時限限制住了 OAQ,因為我知道若這題官方有比 $O(N^2 log N)$ 更快的做法,就一定不會讓時限那麼長,就以為大概不會有複雜度更好甚至更好寫的做法...,而最後可以發現,官方給出的解答也只是 $O(N^2 log N)$,但若去大家上傳的 code,就可以發現至少存在兩個 $O(N^2)$ 十分鐘內可寫完的做法,我的 $O(N^2 log N)$ 方法也和官方的不一樣,所以這題或許千百人來想就會有千百種做法。

$O(N^2 log N)$ 的做法我就不題了,我來介紹一下官方解答理沒提到的兩種 $O(N^2)$ 做法。

要求期望值,其時就是要你求所有 $C_3^N$ 種取直線方法的三角形面積總合。故要給出一個 $O(N^3)$ 的做法應該不難,直接枚舉任三條直線,再用任意一種求三角形面積公式加起來。於是若要加速應該會去想看看加起來的過程是否有一些步驟可以一併處理。

三角形面積的求法對於解題來說是很重要的。若你訪問一個人要求三角形面積要怎麼算,國中小學生大概會回答你底乘以高,高中生可能會回答你海龍公式、$a \cdot b \cdot sin(theta)/2$、兩向量外積除以二等。而在競賽中的計算幾何,兩向量外積應該是最常用的,但也有一個大家也很常用甚至適用於求任意簡單多邊行面積的方法:

把多邊形每個點想像成一個由原點到該點的向量,其中一個逆時鐘的順序是 $v_1 \sim v_N$,則此多邊行面積將會是 $\sum_{i=1}^N v_i \times v_{i+1}$ (其中 $v_{N+1} = v_1$,$\times$是外積的意思)

這個做法絕大部分有關計算幾合的書都會提到。既然有一個這麼常用到的公式,從這裡下手也無可厚非吧?把這個公式和這題聯想在一起,我們會發現,所有有外積運算的點對都會同時在題目給定的某條直線上。每條直線上將有 $N-1$ 個我們關心的點,這些點共有 $O(N^2)$ 個外積運算,所以我們只要把這些外積運算做到 $O(N log N)$ 甚至是 $O(N)$ 就解決這題了!

要如何加速運算,常見的著眼點就是用一個好的順序處理這些點,使得每次加入一個新的點時,可以用數學或資料結構的方式快速求出和已存在的所有點的外積。我賽中想到的方法,就是使用所有點在該直線上按照此直線向量的方向來決定點的加入順序,再套一些資料結構來做。

但實際上,順序若採用產生交點的直線斜率來排序,將會有更好的性質!(所以在想這類問題時,要多想想各種排序方式,可能會發現更簡單的做法 0.0)

請參考此程式碼。(若有什麼不懂得 function 或運算操作,請務必搞懂他們 >_< 這份 code 超短 !) (補上此奮程式碼賺寫者親自解釋做法的 comment)

我簡單描述這份程式碼在做啥。

1. 把所有直線按照斜率排序。此過程時間複雜度為 O(N log N)。
2. 枚舉直線 $L_i$,按照斜率考慮此直線和其他所有直線的交點,也就是說其他直線是由和他夾角最小的開始枚舉到最大的。
3. 接著重點來了,對於任意三條直線$L_i$、$L_j$、$L_k$,若 $L_j$ 和 $L_i$ 的夾角比$L_k$ 和 $L_i$ 的夾角小,那麼這三條直線所形成的三角形的三個頂點,按照逆時鐘排列,一定是 $L_k$ 緊接在 $L_j$ 之後。簡單來說就是任兩點外積的順序和點加入的順序都一樣
於是我們要求的就是 $\sum_{i < j} \bf{p_i*p_j}$ ($\bf{p_i}$ 是第 $i$ 個加入的點所代表的向量),要把這個加總做到 O(n) 應該不困難,可參考程式碼。

由角度的順序加點和按照交點在該直線上的順序加點最大的不同就是,不用在另外考慮兩點在外積時誰左誰右,所以做法就變簡單很多。

在附另外一個我覺得比較奇葩的做法,請參考此程式碼

這份程式碼相對前一份來說並不好懂(因為很奇葩?)。

奇葩的部分就是他算三角形面積的方式是非常少見 (至少我沒有看過的印象)。

要求三條直線所產生出來的面積,他先另外取一條不和這三條線平形的直線 $L_0$ (你可以看到程式碼中他採用旋轉所有 $N$ 條線一個奇怪的角度,然後另外取的線就直接取 $x$ 軸),然後把這三條線按照和 $L_0$ 的夾角排序,令其分別是 $L_1$、$L_2$、$L_3$,所求面積將等於 ($L_0$、$L_1$、$L_2$三角形面積) $+$ ($L_0$、$L_2$、$L_3$三角形面積) $-$ ($L_0$、$L_1$、$L_2$三角形面積)

用下圖來舉例的話,就是我們要求的黃色部分面積是 (黃+紫) + (粉) - (紫+粉)。

然後大家請不要以為看這張圗對了就覺得這樣算面積的方法一定是對的,實際上我至今還不知道怎樣簡單的證明這個面積算法的正確性,目前我只會使用枚舉高達十幾種 case 來證明 ...

有了這個求三角形面積的方法後,我們就先把所有直線按照和 $L_0$ 的夾角排序,之後在枚舉任兩條直線,計算他們和 $L_0$ 所形成的三角形面積用 $O(1)$ 在計算中有幾次被當成正的,有幾次被當成負的(可參考 code),這題就完成了!

problem D --- Fuzzy Search

題意:給兩個僅包含字母 ATCG 的字串 $S$ 和 $T$ 以及一個非負整數 $k$,$T$ 的長度不超過 $S$,問$t$有幾種和$s$的位置配對方式,使得 $T$ 中每個字母和 $S$ 中最近的相同字母位置差絕對值不超過 $k$。

數據範圍:$字串長度不超過 $200,000$,$0 \leq k \leq 200,000$

tag:[ 傅立業 ]

= = = = = = = = = = = = = = =
//以下這段和做法沒關係
這題比賽中我有想了一陣子有沒有普通的字串匹配解 (我覺得這題若用傅立業太無趣了 ... 最近的一些題目都給你用傅立業就好了啊 = =),但最後還是決定回歸傅立業硬爆,但我發現我沒有把 FFT 放在我的 codebook 資料夾裡 ...,只有一份 NTT 的 code,而且在我地記憶中我的 NTT codebook 超慢...,不過賽中我還是硬著頭皮上了, submit 了兩次,第一次 RE,就想說我陣列或許開太小了(咦我以為我有好好的計算過),於是就在把陣列開兩倍大再上傳,結果得到 TLE OAQ,這題有三秒耶!而且 $n$ 只有 $20000$ 耶!連這樣也TLE...?,這時候我就在思索說,究竟要現場壓一下這份 NTT 的常數,還是回去挖以前 ICPC 組隊時對有用的 FFT 出來?而就在這個時候,Codeforces 公告說,這題的測試資料數據給的比題目所說的數據還大,晚點會 rejudge (難怪第一份會 RE...)。此時我賭性堅強,就決定放著不管啦,最後這題很幸運的以差 0.005 秒的時間獲得 AC,但真的能稱做很幸運嘛?這只能怪我沒有打裡好自己的codebook 吧?在這種人手一份 FFT codebook的時代,大家幾乎都不是親自寫 FFT,而你確 TLE 在不是親手寫的部分,那只能怪自己事先準備不充分了 ...
//以上這段和做法沒關係

只有ACTG四種字母,很容易讓人聯想到每種字母分開考慮,接著來想想看對於一種字母來說,會造成哪些位置不能擺?再問更明確些,如果 $T$ 的第 $i$ 個位置是 'A' 那 $T$ 的開頭不能擺在哪些位置呢?如給定 $i$,應該很容易想到一個 $O(|S|)$ 的做法解決這個問題吧?(應該只是個Div. 1 A難度的問題) 而且也不難發現,對於不同的 $i$ 值,不能擺的位置只是隨著 $\bf{i}$ 的增加向反方向位移而已,若觀察到粗體字的部分,應該就會馬上聯想到 FFT 了吧?所以由這樣的思路看來,這題應不難,以 AC 數量來看他難度和 pC 差不多,他會被排在 pD 就只是因為他用了 FFT。

並且由於我們只關心 FFT 的結果是否非零,所以他的摺積運算可以使用位元運算加速,所以也有很多人是使用位元運算來加速的,一直以來,只關心是否非零的傅立業題都卡不掉位元運算...(例如 CF472G),請看看別人怎麼用位元運算 AC本題,看了後你一定會感嘆說為什麼要去使用 FFT ...。

Problem C --- Data Center Drama

題意:給一個 $n$ 個點 $m$ 條邊圗(可以有重邊和自連邊),請加盡量少的邊並把所有邊定向,使得每個點的 in degree 和 out degree 都是偶數。

數據範圍:$1 \leq n \leq 100,000$,$1 \leq m leq 200,000$

tag:[ 圗論 ] [ 尤拉路徑 ]

= = = = = = = = = = = = = = =
我一讀完題目就連想到本年度台大 PK 賽的 pB --- 給一個圖把他定向,使得所有點的 in degree 和 out degree 的差的絕對值不超過 1。想必這題也是個類似做法(某種程度上把degeree變成偶數,然後在尤拉路徑上做一些構造) 構造題。於是我就立刻想到如果所有degree都是偶數,而且邊數也是偶數且連通時,只要按照任意尤拉路徑的順序,把邊定向為一正一反就能滿足條件了。
接下來就一個一個把粗體字的條件去掉看看要怎麼辦~。若 degree 不是偶數一定得變成偶數才有可能能滿足題目條件,那就兩個兩個奇點(奇數 degree 的點)來配對,但任意一種配對方式都可以嗎@@並不是,實際上必須讓配對後連通塊的數量變愈少愈好,畢竟若之後有某個連通塊若只有奇數個邊,那就還得再增加邊,而若一剛開始就先把很多個有可能變成奇數個邊的連通塊串起來,想必能減少要增加的邊的數量,至於要怎麼把所有含有積點的連通塊串起來呢~這裡就不說了 >_<。最後我們把每個仍含奇數個邊的連通塊隨便找一個點加一條自連邊,就能滿足所有粗體條件了!

上一段只是大略講一下我的思路,至於很多細節還是得好好的證明。

code 可以參考這裡。然後我看到這份 code 才發現題目有圗是連通的這個條件.... 所以這題更簡單了 Orz 都怪我只大略看了題目敘述以及看了所附的圗及 Input 就猜題意了... 但圗是連通的這個條件怎麼可以不寫在 Input 裡啦 Orz

另外還有一種不需要由拉路徑的有 tree dp 感的做法,請參考 this comment

Problem B --- Clique Problem

題意:數線上有 $N$ 個點,每個點都有權重,且任兩個點若權重和不超過兩個點距離時,就有邊連接這兩個點,請求出最大的點團,使得此點團任兩點都有邊相連。

數據範圍:$N$ 不超過 $200,000$,座標介於 $0 \sim 10^9$且兩兩互不相同,權重介於 $1 \sim 10^9$。

tag : [ greedy ] [ dp ]

= = = = = = = = = = = = = = =
這題畫個圗應該就可以發現,此題等價於,在眾多 $[x_i - w_i, x_i + w_i]$ 的區間中,要選盡量多的區間使得讓兩區間交集長度不大於 $0$。想到這裡後就令我覺得,這隨便 dp 都能 AC 吧?於是就憑直覺寫了一個有點稍嫌複雜的 dp。

可是後來看到別人的 code 後整個崩潰 ...

若你也寫了個有點複雜的 dp,去看一下Editorial你就會崩潰了。

題意:有 $w*h$ 大小的蛋糕,有 $n$ 個操作,每個操作會從水平或垂直的某個位置切一刀,請問每個操作後最大的那塊單高面積。
數據範圍:$2 \leq w, h \leq 200,000$,$1 \leq n \leq 200,000$,不會有重複的操作。
tag : [ STL ] [倒著做 ]

= = = = = = = = = = = = = = =
這題以眼就令人覺得是經典的STL模擬聯習題,有些人會因為不熟悉 STL 的用法而沒AC,例如說 set $S$ 要取lower_bound,必須使用 S.lower_bound(x),但有人卻因為使用 lower_bound(S.begin(),S.end(),x) 而獲得了TLE。大家若好好讀熟 STL的使用方式相信對比賽中有一定的幫助 0.0

這題比較值得一題的是,若想像成先一次做完所有操作,再把操作一個一個倒著取消回來,將可以做到 O(n)。