本次農場例行賽的其中兩題是近期 Atcoder 題目改變讀入限制條件，另三題則是系列題，這次我們不按照題號，先從 Atcoder 改編的題目講起吧。
= = =
Problem B - Write a Special Judge!
這題是從 AGC007 - Shik and Stone 改編，原題是我自己的原創題，兩題的差別只在於 Input 是否為合法的 path。其實原題最初的版本就是大家現在看到的題目，但是 Atcoder 的審題者覺得不夠簡單所以才增加 Input 限制條件，因為加了以後就只要判斷路徑經過的格子數是不是 $n + m - 1$ 就行了。(可以想想看為什麼這題不能這樣解)
雖然現在不能直接數 '#' 字元的個數來判斷答案，但相信這題仍存在各種解法，這裡給出一個筆者認為挺好理解及寫程式碼的作法：先從左到右，再從上到下遍歷所有格子，每遇到一個新的 '#' 字元就檢查是否在上一個 '#' 字元的右邊或下面，並要確定第一個和最後一個 '#' 字元的位置分別是左上角和右下角。
額外聊一下，這題測試者在驗題時，連兩次雖然過了所有測資，但他的程式碼其實都還是錯的，讓我有機會再加強測資，非常感謝測試者屢敗屢戰的精神！
我的程式碼如下：
Problem D - Edit Sequence
這題是從 ARC063 - An Invisible Hand 改編，兩題的差別在於新題把敘述大量簡化以及 Input 的數列變得可出現重複數字。不瞞大家說會有這題的出現其實是因為該場比賽我沒有看到不會有重複的數字這個條件 XD (該場比賽我對許多人都那麼快 AC 該題感到不可置信 ... 賽後在開別人的程式碼來看才發現我漏掉條件了)
首先，我們令 $f(a) = h$。要解這題，直覺的想法是：先把造成 $f(a) = h$ 的數字們找出來，試著改變他們當中的一些數使 $f(a)$ 變小。
舉個例：當 $a$ = [3,5,3,3,5,2,3,4,3,3,2,4,1,2,3]，此時 $h=2$，現在我們把與 $h = 2$ 有關的數字留下來如右：[3,5,3,3,5,2, ,4, , , 2,4,1, ,3]，可以發現我們能把留下來的數字分成兩兩部相交的區塊如:[3,5,3,3,5][2,4,2,4][1,3]，每個區塊只包含兩個不同的值，且愈右邊的區塊較小的數的值是嚴格遞減，分完區塊後，只要把每個區塊分成兩半(其中一個可以是空的)，左半邊都改成區塊較大的那個值，右半邊都改為區塊較小的那個值，如：[5,5,3,3,3][4,4,2,2],[3,3]。經過這樣操作， $f(a)$ 的值就變小了！以上所用到的計算或操作都可以使用簡單的 dp 或記數來做到 $O(n)$，細節請參考程式碼。
在 Codeforces 上，有人提出了利用 matching 和 maximum flow 的關係，最後用貪心的方法解上述分完好多個小區塊地之後的部分。連結請點我。
我的程式碼如下：
Problem A - Score Distribution 1
這題是系列題的第一題，不妨假設 $p_1 \le p_2 \le \ldots \le p_N$。由於選 $x$ 題的總得分的最小可能值就是 $\sum_{i=1}^x p_i$，最大可能值則是 $\sum_{i=N-x+1}^N p_i$，所以我們只要讓 $i$ 從 $1$ 到 $N-1$ 依序檢查 $i+1$ 題的最小題分和是否嚴格大於 $i$ 題的最大題分和就行了。當然，絕對不可以傻傻地每次從重新把 $i$ 個數的核都重新計算一次，必須有效率的計算。
我的程式碼如下：
Problem C - Score Distribution 2
這題是系列題的第二題。以下都假設 $p_1 \le p_2 \le \ldots \le p_N$。
只看範例測資猜答案的話，也許你會猜做法是二分搜出最小的滿足條件的連續 $N$ 個數，但非常抱歉，我不是這麼好心的出題者 >__<，若使用這一類的方法，找出來的數列數值可能超過 $10^9$，但其實還是有辦法找到在範圍內的其他答案的。
在解這題之前，我們來證明此系列題的一個重要的性質：若存在 $i+1$ 題的題分和小於或等於某 $i$ 題的題分和，我們就稱這個 $i$ 是 bad。若已知 $i$ 是 bad，那麼所有大於 $i$ 但不超過$(N-1)/2$ (本篇提到的除法都是整數除法) 的 $j$，也一定是 bad。
證明：因為 $i$ 是 bad 等價於 $S_i = \sum_{j=1}^{i+1} p_j - \sum_{j=N-i+1}^N p_j \le 0$，且不難發現 S_i 是個先遞減再遞增的數列，且此數列最小值一定是 $S_{(N-1)/2}$。(以後我們稱$S_{(N-1)/2}$為該數列的判別式，記做 $\Delta(p)$)
有了以上性質，首先我們可以知道，若測資的 $y > (N-1)/2$，答案一定是 Impossible。接著我們也知道 $S_y \le 0$ 且 $S_{y-1} > 0$。
現在我們只考慮數列 $p$ 只由兩種數值組成，且前 $(N+1)/2$ 個數一樣都是 $v1$，後 $N/2$ 個數一樣都是 $v2$。
於是我們就可以列出兩個不等式： $v1 \times y> v2 \times (y-1)$ 及 $v1 \times (y+1) \le v2 \times y$。我們只要另 $v1 = y$、 $v2 = y+1$ 就可以同時滿足這兩個不等式了！
我的程式碼如下：
Problem E - Score Distribution 3
這題是系列題的第三題。以下都假設 $p_1 \le p_2 \le \ldots \le p_N$。
我們稱 $p$ 的一個子序列 $q$： $q_1 = p_{k_1}, q_2 = p_{k_2}, \ldots, q_m = p_{k_m}$ 是 good ($k_1 < k_2 \ldots < k_m$)，若且為若此子序列的分數們滿足小月的要求。
首先，我們會發現，若保留此 good 子序列的所有數值不變，並把其他的數都變為$p_{k_{(m+2)/2}}$，那麼整個數列就會變為 good。(因為這樣改變後 $\Delta(p)$將會等於 $\Delta(q)$)
接著應該有種直覺，若存在某個長度為 $m$ 的子序列，那麼也一定存在某個長度為 $m$ 的"連續"子序列是 good (意即 $k_1 = k_2 -1 = k_3 - 2 = \ldots = k_m - m + 1$)。其原因是，我們只要取以 $q_{(m+1)/2}$ 為連續 $m$ 個數中的第 $(m+1)/2$ 個數，判別式只可能變大。於是我們就找到連續的長度為 $m$ 的 good 子序列。
最後有一個解這題的關鍵性質：若一個連續子序列是 good，則此連續子序列的連續子序列也是 good！
證明如下：設此連續子序列 $q$ 長度為 $m$。我們在移除此子序列最右邊的數變成 $q'_1, q'_2, \ldots, q'_{m-1}$，若 $m$ 為偶數，$\Delta(q) - q_{m/2+1}+q_m = \Delta(q')$；若 $m$ 為奇數 $\Delta(q) - q_{(m+1)/2} + q_m = \Delta(q')$。無論 $m$ 是奇數或偶數，此子序列的判式在移除最右邊的數後都只會變大，所以移除後仍是 good 的子序列。同樣的可以證明移除左邊的數後也仍是 good 子序列。於是對於任意的子序列，都可以藉由先移除右邊的數在移除左邊的數達來獲得，至此證明完畢。
當知道這個性質後，就不難想到能在時限內找到最長的 good 子序列的方法。例如說，我們枚舉子序列的右界，然後去二分搜最左邊的 good 子序列左界，就一定可以枚舉到最長的 good 子序列。甚至若讀入檔案原本就把題分按照非遞減數列給你的話，是存在 O(N)的作法的。
我的程式碼如下：
2016年11月26日 星期六
2016年11月7日 星期一
農場例行賽 #13 官方解答
時隔一年多耍費日誌又出現新文章了！這代表此部落格要復活了嗎～唉再看看吧 Orz 有時覺得自己一頭熱也不知道寫這些題解到底有何用，基本上官方都有題解了啊～但我現在似乎算是農場例行賽的官方，所以題解只好自己來寫了 Orz 恕不支援英文版題解 >__<
= = =
在這之前先來介紹一下農場例行賽。
這系列的比賽是 Facebook 粉絲專業 競程日誌 所舉辦的每周例行賽，目前比賽所在的平台為 Codeforces 的 Group tw-icpc-blog ，最初主要是由卡恩 (tmt514) 和蜥蜴 (drazil) 負責打理題目。 而自從第 10 場開始蜥蜴邀請我幫忙出初階組的題目，於是我也加入了～
說句心裡話，每週參賽的人數都少少的不到五人，真沒想到這系列比賽能出到十幾場 wwwwww。那我為什麼要淌這趟渾水呢？目前是為了練快速出原創題的手感吧，因為最近感到我都出不了難題，覺得超難過，想要碰碰運氣能不能不小心生出個難題來，但這幾周下來似乎毫無成果的樣子 QQ 不過說到底... 練這個究竟有啥意義呢 XD
= = =
Problem A - Become an Escapiest!
這題是個簡單數學題。
首先，我們可以把每個可逃脫座標個別處理，只要有一個座標可以逃脫就夠了。
接著，要判斷是否可以從某個座標逃脫，條件有二：
1) $P$ 和 $x_i$ 要在 $B$ 的同一側。
2) 你要能比熊早到達 $x_i$。
這題雖然簡單，但似乎有不少人會忘記判斷條件 (1) XD
我的程式碼如下：
Problem B - Become an Escapiest Again!
這題是常見的 BFS 題。
我們可設計狀態如右：step[x座標][y座標][上一步是遞增 or 遞減] = 到此狀態至少要幾步。
而有兩個狀態我們要設為起點(也就是初始 dp 值為 0): step[0][0][遞增] 和 step[0][0][遞減]。
每個狀態的下一步可以走到哪大家就自行判斷或參考程式碼吧～
我的程式碼如下：
Problem C - Problem setter is also an Escapiest!
這題是不常見的構造題。
先閒聊一下，原本沒有這題的，這題是在試著生 problem B 的測資時冒出來的。原本我 pB 測資 random生成時答案要不是 $-1$ 就是 $2 \times N-1$ 實在是非常困擾 XDrz，很多時候，生測資其實比解該題難上好幾倍呀 XD
閒聊到此。
- - -
首先先注意到，最佳解的路徑一定不會通過同一個格子兩次以上，這是因為格子狀的東西是奇偶分明的，有些格子一定走到時一定是偶數步，其他的則是奇數步，所以走出第一步後，不管什麼時候踏入同一格一定永遠是走(遞增/遞減)的數字近來，所以若有某個路徑會走過同一格兩次以上，我們一定可以把第一次進入該格到位後一次進入該隔間的步數都省略掉。於是我們在構造測資時就不必考慮經過同一格兩次以上的路徑了。
上一段講那麼多，但其實大家應該都會直接猜路徑是 S 形吧 XD 當 $N \equiv 3( mod 4)$ 時 S 行走過的格子數是 $(N \times N + 1) / 2$，剛好滿足條件！ 而 $N \equiv 1( mod 4)$ 更是不用說了，接著我們就是要想辦法讓逃跑路徑除了 S 型別無選擇了！
於是我們就得限制住某些相鄰的格子的數字的大小關係(那些大小於的開口是朝向比較大的數字) 如下右，並且我們很開心地發現這些大小關係沒有 cycle 存在！於是我們的最後一步就是填入數字滿足這些大小關係。有沒有發現這其實就是拓樸排序問題呢？於是我們已經確保這題是可解的了，出題者並不是沒有把問題解決就丟給參賽者解唷 XD
但所有 AC 的人包括出題者都不是使用拓樸排序解啦 XD 我們再仔細看看這個大小關係圖，可以發現要自己直接構造並不是那麼困難，因為你會發現編號為奇數的 row 都大於編號為偶數的 row！所以我們就每條 row 分別填入數字就好啦，並且把 $1 \sim N \times N$ 中比較大的數字分給編號奇數的 row填，比較小的數則分給編號偶數的 row 填。
於是剩下的問題就是給你一條 row 相鄰兩隔的大小關係，請指定的相異 $N$ 個數使得所有大小關係皆滿足，這應該是個農場例行賽初階組最簡單的題目的程度的問題了吧～這部分就交由讀者囉。
我的程式碼如下：
Problem D - Become an Escapiest is not easy!
這是個不常見的 BFS 題。
先處理一下所有的 $d_i$ 的最大公因數 $g$ 不為 $1$ 的 case。明顯的，此時我們有機會走到的座標都是 $g$ 的倍數，所以若 $E$ 不是 $g$ 的倍數就哭哭逃不掉了，並且我們也只需考慮那些為 $g$ 的倍數的 $x_i$ 們。最後，不妨把所有數包括 $d_i$ 和殘存的 $x_i$ 以及 $E$ 都除以 $g$，於是問題就變成最大公因數為 $1$ 的版本了。
再來想想簡單一點的版本：$E < 10^6$。
這個本版甚至是比 Problem B 還要更容易構思出程式碼的，大家可以自己想想看，而且呀，這個版本的問題是解出原來版本的問題的其中一步唷！大家先想想看要如何拿從這個簡單的本版當跳板來解這題吧。
合理的猜測是，我們可以把題目所出現的 $x_i$ 比較近的都分在同一組，更精確地說我們可選定一個參數 $D$，兩個座標 $x_i$ 和 $x_j$ 若差的絕對值不超過 $D$ 就一定要分在同一組。分組出來後每個組別裡最遠的兩個座標都不會超過 $D \times N_i$ ($N_i$為第 $i$ 組的座標數)若每一組都可以從所有點的左邊跨到所有點的右邊，那就是可逃走的了。
最後的問題就是如何決定 $D$ 的數值了，其實啊，大家可以不用那麼認真來決定 $D$ 的值，因為考慮到時間複雜度問題， $D$ 不可能太大嘛，所以就直接不妨直接設 $D = 100$ 吧 ~ 你若有這麼做的勇氣就可以 AC這題了 XD 對不起這是超不良示範 >_<
好啦我們認真解決這個問題。首先要知道 $D$ 的意義是什麼 (題外話：唉，至今還是搞不懂航海王裡的 D 究竟是有何意義 XD)，它的意義是，若連續 $D$個整數座標都是可走的，那麼這 $D$ 個座標都可以藉由卡恩製的傳送道具互相往返，且 $D$ 必須不小於所有 $d_i$ !!! (標紅色是因為最初的標程忘了考慮這個條件...所以若有人在比賽中寫出正解是會拿到 WA 的 QQ)
如此一來，若能逃到某組座標的右邊任一點和下一組之間的所有座標點就保證可以到達了！
若我們不去考慮如何證明 D 一定不會太大的話，要求出最小的 $D$ 值，只要慢慢增加 $D$ 的大小並做 DSU 即可，或是用 BFS測試之類的。
實際上啊，若只有兩個傳送道具傳送的距離長度分別是 $x$ 和 $y$ 且 $x$、$y$ 互質，則 $D$的最小值就會是 $x+y-2$，藉由此性質，我們有辦法證明 $D$ 的值一定不會超過 $d_i$ 中最大的兩個數的和，有興趣就自行更深入的研究相關問題吧。
我的程式碼如下：
總結：
稱我還有餘力的時候，大家快糾朋引伴來參加農場例行賽吧~
= = =
在這之前先來介紹一下農場例行賽。
這系列的比賽是 Facebook 粉絲專業 競程日誌 所舉辦的每周例行賽，目前比賽所在的平台為 Codeforces 的 Group tw-icpc-blog ，最初主要是由卡恩 (tmt514) 和蜥蜴 (drazil) 負責打理題目。 而自從第 10 場開始蜥蜴邀請我幫忙出初階組的題目，於是我也加入了～
說句心裡話，每週參賽的人數都少少的不到五人，真沒想到這系列比賽能出到十幾場 wwwwww。那我為什麼要淌這趟渾水呢？目前是為了練快速出原創題的手感吧，因為最近感到我都出不了難題，覺得超難過，想要碰碰運氣能不能不小心生出個難題來，但這幾周下來似乎毫無成果的樣子 QQ 不過說到底... 練這個究竟有啥意義呢 XD
= = =
Problem A - Become an Escapiest!
這題是個簡單數學題。
首先，我們可以把每個可逃脫座標個別處理，只要有一個座標可以逃脫就夠了。
接著，要判斷是否可以從某個座標逃脫，條件有二：
1) $P$ 和 $x_i$ 要在 $B$ 的同一側。
2) 你要能比熊早到達 $x_i$。
這題雖然簡單，但似乎有不少人會忘記判斷條件 (1) XD
我的程式碼如下：
Problem B - Become an Escapiest Again!
這題是常見的 BFS 題。
我們可設計狀態如右：step[x座標][y座標][上一步是遞增 or 遞減] = 到此狀態至少要幾步。
而有兩個狀態我們要設為起點(也就是初始 dp 值為 0): step[0][0][遞增] 和 step[0][0][遞減]。
每個狀態的下一步可以走到哪大家就自行判斷或參考程式碼吧～
我的程式碼如下：
Problem C - Problem setter is also an Escapiest!
這題是不常見的構造題。
先閒聊一下，原本沒有這題的，這題是在試著生 problem B 的測資時冒出來的。原本我 pB 測資 random生成時答案要不是 $-1$ 就是 $2 \times N-1$ 實在是非常困擾 XDrz，很多時候，生測資其實比解該題難上好幾倍呀 XD
閒聊到此。- - -
首先先注意到，最佳解的路徑一定不會通過同一個格子兩次以上，這是因為格子狀的東西是奇偶分明的，有些格子一定走到時一定是偶數步，其他的則是奇數步，所以走出第一步後，不管什麼時候踏入同一格一定永遠是走(遞增/遞減)的數字近來，所以若有某個路徑會走過同一格兩次以上，我們一定可以把第一次進入該格到位後一次進入該隔間的步數都省略掉。於是我們在構造測資時就不必考慮經過同一格兩次以上的路徑了。
上一段講那麼多，但其實大家應該都會直接猜路徑是 S 形吧 XD 當 $N \equiv 3( mod 4)$ 時 S 行走過的格子數是 $(N \times N + 1) / 2$，剛好滿足條件！ 而 $N \equiv 1( mod 4)$ 更是不用說了，接著我們就是要想辦法讓逃跑路徑除了 S 型別無選擇了！
於是我們就得限制住某些相鄰的格子的數字的大小關係(那些大小於的開口是朝向比較大的數字) 如下右，並且我們很開心地發現這些大小關係沒有 cycle 存在！於是我們的最後一步就是填入數字滿足這些大小關係。有沒有發現這其實就是拓樸排序問題呢？於是我們已經確保這題是可解的了，出題者並不是沒有把問題解決就丟給參賽者解唷 XD但所有 AC 的人包括出題者都不是使用拓樸排序解啦 XD 我們再仔細看看這個大小關係圖，可以發現要自己直接構造並不是那麼困難，因為你會發現編號為奇數的 row 都大於編號為偶數的 row！所以我們就每條 row 分別填入數字就好啦，並且把 $1 \sim N \times N$ 中比較大的數字分給編號奇數的 row填，比較小的數則分給編號偶數的 row 填。
於是剩下的問題就是給你一條 row 相鄰兩隔的大小關係，請指定的相異 $N$ 個數使得所有大小關係皆滿足，這應該是個農場例行賽初階組最簡單的題目的程度的問題了吧～這部分就交由讀者囉。
我的程式碼如下：
Problem D - Become an Escapiest is not easy!
這是個不常見的 BFS 題。
先處理一下所有的 $d_i$ 的最大公因數 $g$ 不為 $1$ 的 case。明顯的，此時我們有機會走到的座標都是 $g$ 的倍數，所以若 $E$ 不是 $g$ 的倍數就哭哭逃不掉了，並且我們也只需考慮那些為 $g$ 的倍數的 $x_i$ 們。最後，不妨把所有數包括 $d_i$ 和殘存的 $x_i$ 以及 $E$ 都除以 $g$，於是問題就變成最大公因數為 $1$ 的版本了。
再來想想簡單一點的版本：$E < 10^6$。
這個本版甚至是比 Problem B 還要更容易構思出程式碼的，大家可以自己想想看，而且呀，這個版本的問題是解出原來版本的問題的其中一步唷！大家先想想看要如何拿從這個簡單的本版當跳板來解這題吧。
合理的猜測是，我們可以把題目所出現的 $x_i$ 比較近的都分在同一組，更精確地說我們可選定一個參數 $D$，兩個座標 $x_i$ 和 $x_j$ 若差的絕對值不超過 $D$ 就一定要分在同一組。分組出來後每個組別裡最遠的兩個座標都不會超過 $D \times N_i$ ($N_i$為第 $i$ 組的座標數)若每一組都可以從所有點的左邊跨到所有點的右邊，那就是可逃走的了。
最後的問題就是如何決定 $D$ 的數值了，其實啊，大家可以不用那麼認真來決定 $D$ 的值，因為考慮到時間複雜度問題， $D$ 不可能太大嘛，所以就直接不妨直接設 $D = 100$ 吧 ~ 你若有這麼做的勇氣就可以 AC這題了 XD 對不起這是超不良示範 >_<
好啦我們認真解決這個問題。首先要知道 $D$ 的意義是什麼 (題外話：唉，至今還是搞不懂航海王裡的 D 究竟是有何意義 XD)，它的意義是，若連續 $D$個整數座標都是可走的，那麼這 $D$ 個座標都可以藉由卡恩製的傳送道具互相往返，且 $D$ 必須不小於所有 $d_i$ !!! (標紅色是因為最初的標程忘了考慮這個條件...所以若有人在比賽中寫出正解是會拿到 WA 的 QQ)
如此一來，若能逃到某組座標的右邊任一點和下一組之間的所有座標點就保證可以到達了！
若我們不去考慮如何證明 D 一定不會太大的話，要求出最小的 $D$ 值，只要慢慢增加 $D$ 的大小並做 DSU 即可，或是用 BFS測試之類的。
實際上啊，若只有兩個傳送道具傳送的距離長度分別是 $x$ 和 $y$ 且 $x$、$y$ 互質，則 $D$的最小值就會是 $x+y-2$，藉由此性質，我們有辦法證明 $D$ 的值一定不會超過 $d_i$ 中最大的兩個數的和，有興趣就自行更深入的研究相關問題吧。
我的程式碼如下：
總結：
稱我還有餘力的時候，大家快糾朋引伴來參加農場例行賽吧~
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$之類的，測資就會足夠強了，賽前還是想的不夠多啊...
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$之類的，測資就會足夠強了，賽前還是想的不夠多啊...
訂閱：
文章 (Atom)