951 views
 owned this note
# 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 啊… 總而言之對我們來說這是一場蠻好笑的比賽,各種假情報、自己騙倒自己的概念… 不過獎品真的是有史以來我們參加過最好的一個比賽!