啊啊啊但最近覺得我生出來的題目都落入俗套好不開心喔。乾脆退休好了 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 所以我們從反方向的角度思考看看，怎樣的題目會讓我們很難聯想到他在考什麼？
首先我們來看一題：有至多 $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 的過程，大部分的人腦構造應該差不多吧？如果你自己都覺得你看到這樣的題目敘述能直接聯想到演算法，那大部分的人應該也會有這樣的感覺吧？所以出題要出的好，要盡量把題目變成你會覺得過了幾天你再重看這題可能就無法立刻想到做法了。
首先請看 NWERC 2011 Piece it together。當初我解這題是使用 2-SAT 解的 (這題也有其他做法)，且我覺得這題的 2-SAT 的運用方式非常好，於是想把它變成擷取精華變成其他題，於是就生出了這題：2014 TCO Algorithm Celebrity Match, Level Three。把它加入平面座標，以及 binary search 等元素。應該很難和我 idea 的來源題目聯想在一起吧 ...？
我談一下這個問題讓我想到什麼。(讀者回饋第一彈 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 聯絡取得臨時帳號～一起來共襄盛舉吧！
沒有留言:
張貼留言