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\le 4\times {10}^5$ 個點的凸多邊形 (每個角要嚴格

$<{180}^{\circ }$)，點座標都要是

$0$ 到

$4\times {10}^7$ 內的整數。 好像之前有看過類似的題目，大意是找一堆不同的最簡分數當斜率即可。

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$ 而已，光是

$\mathrm{\Theta }(n^3)$ 就夠難了，更別說常數還要好。想著想著還是去想 pK 好了，這時也封盤了，Opportunity 也以經過 pH 了，只能靠題數贏了。

這時後 Step4 pK 有想法了。

prob K.

給你

$N$ 個點，問你包住至少

$K$ 個點的最小圓半徑。有兩種測資，

$N\le 5000,K\le 200$ 和

$N\le 100000,K\le 20$。 精度只要求

$2$ 位小數(

$ϵ=0.01$)。時限有

$15$ 秒。

首先有一個

$O(N^2\log N\log 1/ϵ)$的做法，如圖，可以先二分搜半徑

$r$，然後枚舉在圓邊界上的一個點

$A$，此時圓心

$B$ 一定在以

$A$ 為圓心

$r$ 為半徑的圓上，當圓心在這個圓上滑動時，一個點會進入圓一次，出去一次，也就是有個角度區間

$[{\theta }_l,{\theta }_r]$ ，這樣就變成線段覆蓋了(pF)。

First we have an

$O(N^2\log N\log 1/ϵ)$ 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.

---

另一邊的話因為

$K$ 很小，所以只要枚舉一個點和他附近的一些點構成的圓即可…做法是用線段樹套set（其實vector就可以）把一個點為中心的正方形的所有點抓出來(如果點比

$K$ 多太多，大概

$5$ 倍，答案一定比

$r$ 小)，似乎

$O((NK\log K+N{\log }^{2}N)\log 1/ϵ)$。

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-ϵ$ 的方法 (但要

$N^3/8+ϵ$) 才會過… 最後沒輒，別人金頭腦，被電也沒辦法…

頒獎

最後 Step4 在頒獎時把 pK 改一改，把二分搜優化一下，然後 long double 改回 double 就過了！ 沒想到原來我們做法沒錯，只是常數太大，優化一下就可以了。 當下很嘔，早知道不要跟著 RR 想 pB ，專心優化 pK 就好。

最後開盤的時候我們已經心裡有底，只有 iPad mini 了。 當在開 RRwatameda 時我們已經準備走上台了，沒想到 pA 開出來 AC ，但 pB 開出來，一個大 WA 字。三個人都嚇傻了！原來我們都被唬了orz，頓時間百感交集，變回 iPad 是蠻開心的，但是如果沒有被 pB 嚇到可能會過 pK 啊…

總而言之對我們來說這是一場蠻好笑的比賽，各種假情報、自己騙倒自己的概念…
不過獎品真的是有史以來我們參加過最好的一個比賽！