# Day 0 第 0 天可以說是最**慘**的一天。 1. 從機場搭到 NUS 坐了一個很**慘**的計程車，司機開著開著居然自己迷路了！本來 22$ 的車費最後付了 37$. 2. 之後想說去新加坡市中心逛逛順便吃個飯慶祝一下，沒想到又坐了一班很**慘**的公車，整個車都是塑膠味… 3. 最最最**慘**的是我們去吃了一家很**慘**的店，裡面的湯麵跟**飽和食鹽水**一樣鹹，而且又貴，結帳的時候一看，87.8$，眼淚都掉出來了… 4. 回到宿舍，房間裡面有桌子，有椅子，可是...居然沒有冷氣QQQQQQ (台灣是冬天，但新加坡卻是赤道國家欸orz... 晚上房間大概 30 度，又溼又悶，實在很難睡...)。最後好在 Hanhan 找到了一間有冷氣的 Lounge ，三個人便趁著半夜四下無人偷偷搬到裡面睡了… 回去時大家一把濞涕一把眼淚，士氣低落… # Day 1 ## 開場 在開幕式前我們的隊隨(?)還帶我們去逛了一圈 University Town，發現那個校區的學生宿舍真的超高級的，下面有游泳池，旁邊有圖書館、電腦教室、運動場…而且每一個都超大，真不愧是 NUS。 開幕式的時候有各隊介紹還有最重要的獎品介紹，那時候介紹首殺獎的時候我們特別仔細看，發現 pA 的牌子特別大，其他的比較小，就想說 pA 大概是被預設成 Global First AC 的題目了，八成是水題。 ## 測機 一進去就看到我們的位置上有一個大大的螢幕，還好 Hanhan 讀信讀的很仔細，有看到可以申請大螢幕。果不期然之後很多隊都開始搶螢幕了… 因為 Judge System 是用 Kattis ，品質有保證，不像台灣站是舊 PC$^2$ ，還要測 RE Verdict 是 RE 還是 WA ，Stack Limit 有沒有調等等的鳥問題。基本上也沒有什麼好測試的，就確定可以傳題目，可以影印東西之類的。 值得一提的是 Kattis 有 Command line submission tools，印象中是在說明那個分頁可以下載一個`submit.py` 還有 `.kattisrc` 。不過缺點是題目的名字最好要取的跟題目一樣 (如 pA 就是 `cool1.cpp`)，有點麻煩。 # Day 2 正式賽。結果好像因為太早了，大家頭腦都怪怪的。 一開始就我們的貫例，Hanhan 負責打 `.vimrc`，我和 Step4 看題目。 首先當然是看昨天偷偷知道的簡單題 pA，大意是有個照著固定的序列移動的機器人，要求他的循環節。感覺好像算簡單但好像又沒有這麼好寫。沒想到我才打個三行，嚇呆了！對面的隊伍已經來了一個氣球了！這題題目敘述也不短，也不是什麼一行題，對面的是手速小天王喔！再寫一陣子，發現好像沒有那麼好寫，改了一陣子總算範測都過了，對面已經來了第二顆氣球了！！傳上去，立刻吃了一個 WA ，想了一下原來這個做法是錯的！後來轉頭一看，才發現**原來大家過的題目都是E&F啊！pA除了我們跟本沒有人傳…**一個拿到假情報的概念。 之後我就去旁邊看要怎麼修， Hanhan 也很快的把一個水題 E 寫掉了。 接著 Step4 金腦想出了 pD ### prob D. 題目好像是給你一個數字 $N$ ，你要找最接近 $\sqrt{N}$ 的因數。 $N$ 的因數有 $10^{10}$ 個。 做法好像是把 $N$ 拆成 $N = n_1 \cdot n_2$ 且 $n_1, n_2$ 的因數在 $10^5$ 左右，之後把兩個數的因數排序後用雙指針掃過就可以了。 說起來很簡單，可是好像也沒有那麼容易想到。 中間好像有點小 Bug ，最後 Hanhan 先掃了另一個水題 F (線段覆蓋)後才過這題的，不過這題也算是這場比賽難度在後面的題目了吧…靠著這題我們才拿到 First Accept Price. (結果後來發現其實沒有Bug, 是 debug code 沒刪QQQQ...) 之後想了一下 A，可以改但有點小麻煩，於是先看別人過的題目，發現好像不少隊過 pC ，發現好像蠻簡單的，基本上照著題意做就是了，善用 `set` 等等的資料結構很容易把他壓到 $O(N \log N)$ 後來 G 卡了一小段時間 ### prob G. 給你一個序例，你要把他切成很多段，並且前一段的總合不能超過後一段，問你最多可以切幾段。 這是一個看完了就會讓你忍不住想 greedy 的題目，不過看到 WA 一片， $N$ 又只給到 $3000$，明顯就是個陷阱…最後還是乖乖寫個 DP $ DP(i, j) = \min\limits_{\text{sum}(i, j) \geq \text{sum}(j, k)} DP(j, k) + 1 $ 要把 $ \min DP(j,\cdot)$ 存下來才會變成 $O(N^2)$。 接著 Step4 把 pI 開出來了，好像是一個排列組合題 ### prob I. 有 $a, c, m$ 個 A, C, M，問你任兩個不相同的排法有幾種？ 其實概念好像不難，先把 M 排好，那就相當於要在每兩個M中間插入 AC..AC or AC..ACA or CA..CA or CA..CAC，仔細算一算就可以了。 之後我跟 Hanhan 講了 pJ 的做法 ### prob J. 給你一顆樹，你要支援兩種操作 1. 改一個點的顏色(顏色只有 100 種) 2. 詢問一個點的子樹中有多少顏色滿足這種顏色的子節點有奇數個 還滿簡單的，就把樹壓扁後 做 Xor Range Query 即可 而且 `g++` 剛好有個好用的 `__int128` 可以用。 因為 Hanhan 線段樹寫的飛快，一下就寫完了，不過有點**慘**的是題目說點有 $200000$ 個，我看成 $500000$ 個，結果 Hanhan 以為是 $50000$ 個，傳上去就 RE。 接著我們的 `__int128` 好像用法錯了(好像 `__int128` 隨便 cast 成 `long long` 會出問題)，本來要省時間的沒想到又吃了一 WA。 接著我就繼續修我的 pA ### prob A. 其實麻煩的點只是找到的序列可能是 ABCDABCD (A,B,C,D 表示一個位置)，但 ABCD 才是最小循環節。 因此題目轉成要找字串的最短重覆序列，算是經典題吧…可以用 KMP 做。 對於一個字串$S[1..n]$，用 KMP 可以找出所有 $i$ 滿足 $S[1..x] = S[(n-x+1)..n]$ ($S[n]$ 的 fail function 一直走即可)，而如果 $n-x$ 可以整除 $n$ ，那 $x$ 就是一個循環長度，找最小的即可。 還滿**慘**的，一開始被騙去寫這一題，結果還沒有 first AC。 ### prob H. 之後是 pH ，你要構造一個 $n \leq 4 \times 10^5$ 個點的凸多邊形 (每個角要嚴格 $\lt 180^\circ$)，點座標都要是 $0$ 到 $4 \times 10^7$ 內的整數。 好像之前有看過類似的[題目](http://dreamoon4.blogspot.tw/2015/05/problem-zero.html)，大意是找一堆不同的最簡分數當斜率即可。 pH AC 後剛好 180 分鐘，剩下兩個乍看不太能做的題目。看了一下 Score Board 發現我們 penalty 大爆炸，Opportunity 雖然少我們一題，不過就算他們 A WA 很多次，只要在賽內 AC (299 min 也可) 都會贏我們，而其他隊看起來就算題數追上好像 penalty 也不會贏我們，看上去像是個穩拿 iPad，寫出一題就有機會拿 Mac 的情況。 一開始我們看了一下 pB ，題目是接著 pA 的，你要構造一組測資使得循環節 $> 10^6 $。理論上循環節的長度也只能 $n^3 = 8 \times 10^6$ 而已，光是 $\Theta(n^3)$ 就夠難了，更別說常數還要好。想著想著還是去想 pK 好了，這時也封盤了，Opportunity 也以經過 pH 了，只能靠題數贏了。 這時後 Step4 pK 有想法了。 ### prob K. 給你 $N$ 個點，問你包住至少 $K$ 個點的最小圓半徑。有兩種測資，$N \leq 5000, K \leq 200$ 和 $N \leq 100000, K \leq 20$。 精度只要求 $2$ 位小數($\epsilon = 0.01$)。時限有 $15$ 秒。 首先有一個 $O(N^2 \log N \log 1/\epsilon)$的做法，如圖，可以先二分搜半徑 $r$，然後枚舉在圓邊界上的一個點 $A$，此時圓心 $B$ 一定在以 $A$ 為圓心 $r$ 為半徑的圓上，當圓心在這個圓上滑動時，一個點會進入圓一次，出去一次，也就是有個角度區間 $[\theta_l, \theta_r]$ ，這樣就變成線段覆蓋了(pF)。 First we have an $O(N^2 \log N \log 1/\epsilon)$ solution. Binary search the radius $r$ and enumerate through which point , say $v$, should be on the border of the bounding circle. Now the center of the circle $B$ will all be on a circle with radius $r$ and center at $A$. When center $B$ is moving along the circle, every point will enter the circle once, and also leave the circle once. So for every point, there will be an interval $[\theta_l, \theta_r]$ (possible empty) such that the point is inside the circle. Now we transform the problem to "given some interval, is there a $\theta$ such that $\theta$ lies in at least $K$ interval?". Which is a similar problem to pF. ![](http://i.imgur.com/koInw1E.png) ----- 另一邊的話因為 $K$ 很小，所以只要枚舉一個點和他附近的一些點構成的圓即可…做法是用線段樹套`set`（其實`vector`就可以）把一個點為中心的正方形的所有點抓出來(如果點比 $K$ 多太多，大概 $5$ 倍，答案一定比 $r$ 小)，似乎 $O( (NK\log K + N\log^2 N) \log 1/\epsilon)$。 For the other side, since $K$ is small, we could prove that when enumerating a point $v$, it is enough to just consider all the point in the square with side length $2r$ and center at $v$. And if the point among them is bigger than $5K$, we could also proof that the answer would be smaller than $r$ (by pigeonhole principle). Hence if we then use the method before, the time complexity is $O(NK \log K)$ each time. The only problem remain is how to get all the point in the square, which could be achieve easily by using segment tree of `set` (or even `vector`). ---- 寫了之後傳上去，一個大 TLE 字。這時候看了一下 Score board，不看不知道，一看嚇一跳！ RRwatameda 不只傳了 pA ，連 pB 都傳了！ 這時候我們三個人臉都綠了，雖然封盤不知道結果，但是 pA 沒過沒道理去傳 pB ，所以他們大概是過了 pA。 而 pB 又是構造題，一翻兩瞪眼，都有 pA 檢查了，基本上傳了一定會過。 iPad 瞬間變成了 iPad mini… 這時候我們狂傳了一陣 pK 左改一下 eps，又改一下迴圈精度，但還是怎傳怎 TLE，只好放棄來想想看或許比較簡單的 pB 了，最後只想出了一個機率 $n^{2+\alpha}$ 的爛方法，用 pA 試了一下，只有 $80000$ 左右。然後比賽就這樣結束了… ## 賽後 之後我們三個人都一個苦瓜臉，左想右想都覺得不合理，看 RRwatameda 封盤才過 pA 的，怎麼沒過 5 分鐘一下子就解掉 pB 的，不知是 tourist 上身了還是怎樣。之後我們吃飯都在想 pB ，怎麼想都卡住，最後只有 Step4 想出一個 $N^3/8 - \epsilon$ 的方法 (但要 $N^3 / 8 + \epsilon$) 才會過… 最後沒輒，別人金頭腦，被電也沒辦法… ## 頒獎 最後 Step4 在頒獎時把 pK 改一改，把二分搜優化一下，然後 `long double` 改回 `double` 就過了！ 沒想到原來我們做法沒錯，只是常數太大，優化一下就可以了。 當下很嘔，早知道不要跟著 RR 想 pB ，專心優化 pK 就好。 最後開盤的時候我們已經心裡有底，只有 iPad mini 了。 當在開 RRwatameda 時我們已經準備走上台了，沒想到 pA 開出來 AC ，但 pB 開出來，**一個大 WA 字**。三個人都嚇傻了！原來我們都被唬了orz，頓時間百感交集，變回 iPad 是蠻開心的，但是如果沒有被 pB 嚇到可能會過 pK 啊… 總而言之對我們來說這是一場蠻好笑的比賽，各種假情報、自己騙倒自己的概念… 不過獎品真的是有史以來我們參加過最好的一個比賽！