2017年2月28日 星期二

農場例行賽 #25 後記

這篇已經現在我的 FB 塗鴉牆試過水溫了,現在把他轉到這裡來 >__<
= = =
好久沒有為了準備一場農場例行賽感到如此焦躁了,於是決定把這次的經驗記錄下來,也讓大家看看一場農場例行賽是怎麼誕生的。
若不知道什麼是農場例行賽的朋友可以參考我們的粉專 競程日記 的關於頁面,啊不過似乎也沒什麼說明XD,總之就是每周辦該粉專的小編們會想辦法弄出一場有關演算法的程式比賽給台灣的學生們遊玩
= = =
起初的農場例行賽(在我還沒接手前,也就是第十場以前),有一半的題目(比較難的那一半)是挑現成的題目,剩下一半則是小編們自己出。
而我接手後,由於我無法忍受自己辦的比賽放著不是自己準備的題目,於是就改成全部自己出了。但出題目是件很花時間的事情,後來就盡可能到處拉人幫忙出題目,雖然我們一直釋放善意希望台灣的學生能自己來找幫忙出題目,但最初主動來找我們的都是非台灣的學生 0.0,那時覺得沒什麼拒絕的理由,就都答應了。
而昨天這場農場例行賽就是使用一位非台灣學生所提供的 problem proposal,雖然題目是根據別人提出的 proposal 出的,但具體細節以及要不是使用都是由我強烈的主觀所決定的 >__< 所以若覺得題目不好的話,千錯萬錯都是我的錯!
雖然是這樣說啦,這周的原定比賽時間是禮拜五,但這位出題者直到星期三晚上才跟我們說生不出最難的那題,大家看到這裡應該會問說,都有 proposal 且也被我同意了,為什麼會生不出來呢?這是因為,在當周的星期日時,他告訴我,他後來覺得這題放在最後一題太簡單了,他希望能搞出一個再難一點的題目,並告訴我他能在星期二以前完成。但到最後似乎沒有擠出任何點子...
其實我本來就有覺悟會遇到這種事,所以也沒受到太大動搖,於是就接手這份工作,開始思考我要怎麼補上這個洞。
原則上,我會希望,我能夠根據他給我的 proposal 來加強難度,達到能讓大家都滿意的標準,他原本給我的 proposal 是這樣的:

```
給一個連通且有權重的圖 G,每條邊的權重會是個與 t 有關的(一次/二次)式,給一個 t 所允許的區間 [t1,t2],求最小的 MST(Minimum spanning tree)。
點數(N) <= 100,邊數(M) <= 200,預期複雜度 O(M^3 log(N))。

P.S. 後來好友們表示,這題的單筆詢問版本其實曾出現在台灣的三四年前的國手選拔比賽中,也曾出現在 USACO 的題目中。
```

其實我看了 proposal 後就知道其實存在 O(M^2 log(N)) 的做法,可是覺得這個方法對我來說超麻煩,只跟他說:我覺得這題難度大概是第四題的難度(一般來說題目共五題,由簡單到難),且因為二次式的處理再加上去可能會太複雜(我不太喜歡硬是把兩個不同問題結合成一題的東西),使用一次式就好。
但現在為了要說服他原本的題目其實也夠難,所以就告訴他這個方法的存在,再把它改成多組詢問一定就足夠難了,並告訴他我會幫他生出解答。於是我決定放棄星期四晚上的打羽球活動來準備這題。
但星期四晚上有個意外插曲:星期五我們辦比賽的時間在星期四晚上才公告說也有一場 Codeforces 的比賽,Codeforces 就是我們借來辦比賽的平台,他們自己也辦了比賽的話我們就無法再同一時間辦比賽了。而且我相信若兩個比賽半在同個時間,大家會選擇參加 Codeforces 的比賽而不是參加我們的... 總之小編們因此決定把比賽時間一到星期日晚上。
由於我身性懶散,接下來的時間點就跳到星期六晚上了...
由於我所理解的 O(M^2 log(N)) 做法要使用到 Link-Cut Tree,並且這是個我從來沒有寫過的東西,整個就不知道要從何寫起... 又胡思亂想一陣後,決定還是先來寫個爛爛的時間複雜度 O(M^3 log(M)) 作法,但我連寫這個做法都覺得卡... 寫完後就冒出了自暴自棄的想法:其實就這樣出個 N,M <= 100 也沒有真的太簡單。而且當時已半夜兩點了,所以我就開始實踐這個自暴自棄的想法啦!首先來弄比 Sample Input 看看。
決定範例測資是一件很大的學問,你給的測資會影響題目的難度,如果可以使用很小的數據就涵蓋各種邊邊角角的 case,就能夠讓參賽者比較好理解這個題目的各個面向。以這題來說,我會覺得,點數和邊數少,且若隨著 t 的改變, 構成 MST 的 tree 也常常改變的話,那就是個好的、能讓大家容易理解的範例測資,於是我就構造出了三個點三條邊,且三種 spanning tree 都存在一段時間區間會是 MST 的測資,我把他們的函數圖形畫在紙上仔細端詳並看了我生的測資的答案後...
!!! 怎麼開始覺得 MST 對於 t 的函數圖形是凹函數... 這時我完全瘋掉啦!因為這若是凹函數,題目的設計就會變得很有彈性。我馬上敲卡恩叫他幫我一起想,到底這是不是凹函數,若是的話要怎麼證明。結果呢,證明方法其實超簡單的,卡恩馬上就想到了。很多數學證明都是這樣啦,沒人告訴你這件事是對的你都不會注意到,但告訴你是對的並叫你證明,卻有可能馬上就證出來。嗚嗚此時我感到超難過的,我沒有聽完題目就馬上聯想到他是凹函數的直覺...若當初有這個直覺得話,這幾天的日子一定很好過...不過這件事也再次驗證我在 ioicamp 所講的話:「通常畫一些簡單的測資能夠幫助自己更理解題目」。
所以說,若是凹函數,會有什麼好性值呢?是凹函數的話,一個區間的最小值一定發生在區間兩端啊!所以每組詢問只要做兩次普通的 MST 就可得到答案,再得到這個結論後,就覺得求最小值實在是有點蠢,也有點容易讓參賽者不小心就 AC,所以就把題目改成求區間的最大值,那麼你就還得用三分搜預處理出整個函數的最高點位置及高度。
於是之後就繼續把後續的事情處理一陣,包括決定數據範圍、生測資、測假解之類的,弄完的時候大概快六點了吧(倒),而 link-cut tree 的做法就從此不了了之,我也懶得測 link-cut tree 的做法能否通過我生的所有測資 (我的設定是希望若真有人寫 O(M^2 log(N)),應該要 AC 啦)。
就結論來看,不只有我沒這這個直覺,這場比賽的大部分參賽者也沒這個直覺(雖然是有一個人在 code 裡使用了三分搜,但他每個詢問都做一次三分搜就 TLE 啦),所以這題應該是有一般 Codeforces 比賽的 (Div. 2) E 以上的水準的。應該是有滿足客戶 (參賽者+原出題者?) 的需求 XD
= = =
最後拿整個事件來討論另一件事:出題能力和解題能力有關係嗎?這個問題雖然稱不上月經文,但每一兩年還是可以在 Codeforces 上看到有人討論。
首先先定義好這裡的「出題」是什麼意思,一般的演算法比賽的出題包括了「設計題目」和「提出解答」兩部分。「設計題目」就是題出一個有標準答案或有標準衡量答案的好壞的問題。「提出解答」則是給出一個解決這個問題的方法。
一般而言,我們用來評斷一個問題的好或壞的標準通常是:1. 設計出的題目,是否是一些 well-known 的問題,如果是,就會被大家嫌棄你這題只是個很多人都知道,會讓解過的人在比賽中受惠的「壞」題。 2. 提出的解答,究竟有沒有創意,是不是大部分人想不到的作法,若是,這題則是「好」題。
要避免 [1.] 的情形發生,那就是要看得夠多題目,才不會自以為想出一個新題卻是期很多人都看過的題目。而要達成 [2.] 的目標,需要的怎麼想都是解題能力吧?
順帶一提,如同時滿足 [1.] 和 [2.],那就可以發論文了吧,畢竟這代表著你在 well-know 的題目有嶄新的突破 XD
若大家判斷題目的好壞的標準真的和我所描述的差不多的話,你們是否有發現,若一個人很有創意的設計了很多問題,但都只是簡單題,那他也只是創造了很多不壞的題目而已;反之,若一個人偶爾才擠出一點題目,但解法都很精妙,那我們會說這個人出了不少好題。
好啦連我自己都覺得上面這段感覺上是在玩文字遊戲而已 XD 那就再舉個更極端的例子好了,若 A 提出一個問題,想了好久都不會,但 B 卻解出來了,你們會覺得誰功勞比較大呢?
說到這我就想到... 最近有個人寄信問我:「我想辦一場 Codeforces Div.2 的比賽,但目前還缺難題,我已經設計好題目了,你可以幫我想解法嗎?」看完這則信後,我思考了一下,想說剛好最近習得已讀不回的技能,也對他使用看看來提升技能等級...
拉回來 = =,總之,我覺得設計題目是相對容易的事,最近有另外一個人問我說,我到靠什麼來激發我出題的靈感?我回答說:「玩小遊戲、到戶外走走、看動畫等等」,他就回我說:「看動畫能提供你點子? :p 但我從未能從動畫中得到點子XD」
我來舉一個我在看動畫得到點子的例子:有一部動畫,在片尾曲的時候有一個人一直在螢幕裡走來走去,我看動畫的習慣是片頭片尾曲都會完整聽完,但這個時候沒有劇情嘛於是某天我看到這一目的時候就在想...如果他有留下腳印且左腳和右腳的腳印是可以區隔的...我有辦法根據他留下來的腳印知道他有至少有幾步是倒退走嗎?於是 Codeforces 578E 這題就誕生了。
我聯想到這樣的問題,大家會覺得很奇怪嗎?但我覺得聯想到題目這種事情感覺上也不是我自己能控制的啊,我個人是覺得,看看新東西,看看不同風景,都有機會激發題目的靈感,雖然那個片尾曲我也是看了好幾次,不知道為什麼突然其中一次就有靈感就是了...
但我覺得比起有靈感,更重要的是你是否會抓住那個靈感,認真去想突然在心中冒出來的問題,並真的把他解出來,以腳印這題為例,我冒出這靈感後大概又原地發呆了超過半個小時才想到解法。 (補註:以這個例子來講,半個小時其實算是花的時間超少,很多時候其實是想好幾天的...)
嗯...寫到這裡突然覺得我舉的這個例子似乎只會讓人覺得:你就天才吧!舉這例子只是想炫耀吧!我是能從你這個例子得到什麼收穫啦!
那我就拉回這段討論的原點吧,我原本是說,我是要拿前面所提到的,出這次農場賽最難的這題的事件來討論「出題能力和解題能力有關嗎?」這件事。這題「設計題目」的人就並不是我,但原出題者只提出了 O(m^3 log n) 的作法,若這題就按照他原本的 prposal 出出來,大家會覺得他是個好題嗎?應該只會覺得他就只是普通不壞的題目而已吧。對解題者而言,通常把時間複雜度壓到可以 AC 的程度後,就不會再想下去了;但身為出題者,則該盡可能的壓低演算法的時間複雜度,或是把題目調整成限定難想到的做法才能 AC 的數據限制。也就是說你一定得比參賽者還更了解該題目的各種性質,能做到這點,就意味著你擁有更高的解題能力。所以,你擁有更高的解題能力時,就愈能把「不壞」的題目變成一個「好題」。我想,我有在這場比賽確實地幫他把一個「不壞」的題目變成一個「好題」。

結論:出題能力和解題能力很有關係的!所以大家快來幫農場例行賽出題所不定也可以反向激發解題能力唷!(詭辯?XD)

2017年2月12日 星期日

農場例行賽 #23.5

為什麼會有這場奇怪的比賽出現呢?主因是 tmt514 和 drazil 在出題目時,常常會不小心舉出一些太偏離普通的演算法競賽或有些刁難的題目,於是我就想說,就辦一場讓大家隨心所欲、不限至題目類型的比賽吧~雖然最終看來...這些題目大部分還算是普通的 = =,大家還是很克制的沒有出真的非常奇怪的題目 (drazil 之前跟我舉了好多他想出的題目,但最後都自己否決掉了 XD)

這場由我生的題目有 B、C、F,A 和 E 是 drazil 出的, D 是 tmt514 出的。

我這裡就稍微解釋一下我出的題目大致上的獲得 AC 流程和對這些題目的看法,就不附上程式碼了。


Problem B - Everyone look forward to high rating user


會想到出這題是因為... 就如題目敘述所說的,我還蠻喜歡看這些關於厲害的人的表現數據的,但是我過去又很懶得研究 API 之類的東西,所以就沒有什麼動力寫程式碼列出我想知道的事情。

但最近工作後,其實每天做的事大概就是解這題所需要做的事情吧 = =,一直查一直查 tools 怎麼用,實際思考程式結構的時間挺少的。於是漸漸地對查 tool 怎麼用這件事麻痺了吧?把這提出成題目也不會給自己太大壓力,是個輕鬆三個小時左右就可以生完的題目。

先附上 Codeforces API 的連結。先聲明,我並不釋出完題目就知道用哪個 method 的,出題前我還不知道那些 method 怎麼用 = =,但至少... 這題要做的事用想的就覺得不太難,API 如果不能輕鬆得到結果的話,那這個 API 也太沒用了吧 0.0

我簡單地用 Python 試了幾個 method,最後決定使用 contest.ratingChanges 這個 method 來獲得 rating 資訊,因為我只要獲得每場比賽所有人的 rating change,就可以獲得這題所想要的結果了,而且只需要不到 $1000$ 個詢問,若你真的每個 Codeforces user 都詢問的話,由於它限制一個 ip 每秒中最多能詢問 $5$ 次,可能跑一天還跑不完吧 XD (不過我這樣寫可能還是要跑個十幾分鐘吧 )

使用了此 API 後,我就先把他丟給我的 JSON 檔案丟到 online json visualizer,例如 這個,於是我就可以快速地了解他的 json 結構,找到我想要的資料的位置,於是我就寫了一個能印出所有滿足 newRating > 2765的 (user, newRating) pair,之後再用 c++ 處理這些資料,把答案寫死在 code 裡,這題就大功告成了!

順帶一提,據說賽內唯一一個 AC 的人是肉眼一個一個看排名前面的人的 rating 的 ... 所以說我這題目並設計得不好,讓人還有機會不藉由 API 就在塞內獲得 AC... 應該要使用排名在一千左右的人當主角...。

P.S 可能還是有人想知道我 api 是怎麼使用的,我還是貼一下我的程式碼好了,但我對 python 真的完全不懂 >_<,相信熟悉 python 的人一定能有更輕省的寫法


Problem C - It's a hard problem that I believe you can't solve by yourself


這題則是標準的 OEIS 題,標題都說地那麼明白了,並不期望大家在三小時內寫出來啦... 若這種題目有那麼多人能在三小時內解出來,那麼那些研究這個問題的 paper 大概沒什麼太大的價值吧 XD

雖然這題是 OEIS 題,但也不是最簡單地把前三個數放進去就能找到答案的 OEIS 題。首先,你會注意到,第 $n$ 個數一定是 $n!$ 的倍數,所以我們就可以把它除以 $n!$,若你把前三項經過這樣的處理,或許就有機會找到答案了~但可惜的是,在我寫這篇 blog 的時候,輸入前三個數將獲得高達 $324$ 項結果,你要一個一個檢查是不是你想要的序列,可能比 Problem B 人眼搜索 Rating 前 $80$ 高的人還難吧 XD。

接下來要做的事應該已經呼之欲出了,寫個簡單的爆搜程式搜索出第四個數,就可以在 OEIS 上找到唯一的序列,剛好也就是這題的答案~ OEIS 上也有附了一個簡單明瞭的公式,使用它就能 AC 了。

若有興趣想深入研究這個問題,請自行翻閱 OEIS 附的 reference 吧。

最後提一下,為什麼我會選擇這個序列呢?這個問題其實是我當兵期間研究的眾多問題之一。有時睡不著就會亂想題目,有天開開心心地再這個問題上獲得了一個 $O(N^2)$ 的解,想要之後出在比賽上,但當時並沒有把解法記下來。直到退伍後才認真把 code 寫出來,但這時我只能做到 O(N^3),已經想不起來在軍中時 O(N^2) 的作法到底是什麼,抑或是根本當時就想錯了?但最後我還是把它當它寫成題目的 proposal 投稿到 SRM,結果卻被 cgy4ever 發現其實 OEIS 有這個序列!而且還有好多論文在研究這個問題!知道後整個崩饋 T_T 最後這題就不了了之啦~

最後的最後再提一下, 賽中唯一 AC 的人並不是靠 OEIS,而是 google 了關鍵字:"number of partitions with k-intersection matchings" 而找到相關論文的。

Problem F - This is a sign-in Problem!


這題就如同標題所說的,是個簽到題

近來我們發現,若最簡單的題目不夠簡單,我們無法準確地獲得有參加比賽的人數,所以比進行間多放一題簽到題。並且我們因為簽到題多捕獲了 3 個有讀題的人!謝謝大家的餐與 m(_ _)m