農場例行賽 #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)