2015 Google Code Jam Round 1A-Logging

這篇文章應該算是先前這篇的補充。

故事是這樣的，
某一天我在dreamoon的blog看到這篇文章，（當時飲料盃早已結束）
直覺就認為文中的「我在『別人』的網誌上看到對方閱讀了我的 code 覺得不錯」就是我，
於是也跑去嘗試解那題。
（其實就算沒有這段話，我也會去解啦，畢竟也很好奇自己認為不錯的code會有什麼錯誤）


然後結果就是...我雖然往正確的方向思考，但是沒有順利解出來OAO

2015 Google Code Jam Round 1A

官方題目、比賽網站（可下載練習用測資並judge）

Problem A. Mushroom Monster 這題其實很簡單，但是題目敘述讓人很難理解，尤其對於非英文母語使用者而言，真正的功夫都花在理解題意。
我現在重新簡要的闡述題意：

2015 Google Code Jam Qualification Round

官方題目、比賽網站（可下載練習用測資並judge）
畢竟只是Qualification Round，
沒有名次、時間壓力，只要分數達到20分就晉級了，
我先前就自己下了一個目標：

要只使用python完成qualification round!

證明：連續分數取整之和的根號算法正確性

有一道經典問題是這樣子的：
「給予一個\(n\)，請計算\(\sum\limits_{k=1}^{n}\lfloor{\frac{n}{k}}\rfloor\)」

隨便寫一寫大概就會像這樣：

Blog誕生

今天開始弄這個blog了...
來講講這個blog誕生以前的長篇故事好了：

約莫三週前開始，
因為這個時候高三的同學都在準備學測，
而已經錄取並且不參加學測的我就在圖書館自習。
自習期間正好讀到「Kosaraju's Algorithm」，
經過一番努力，
好不容易理解了這個演算法。
然後突然覺得：

高三段考後的那一週

2015/1/18

今天主要做了兩件事：
1.Facebook Hacker Cup 2015 Round 1
2.Codeforces Round #286 (Div. 1)
其中，第二件可以說是徹底的失敗，兩個小時拿了0分。
目前知道除了我太廢以外，過度依賴std::map是一大失敗因素。
這裡就打一下FB Hacker Cup，比賽結果還沒公告，不過CF上有提供Judge的題目，我都過了。

1.Homework

因數倍數相關、範圍小、詢問多，從這些特徵，不難猜到要「建表」。
找到質數，把這個質數的所有倍數（包含本身）+1。
因為這題測資很弱，而且傳Output比賽，時限不會精確卡到，所以建完表對每筆詢問算一遍就會過了。
更進一步，可以發現在\(B\leq10^7\)下，\(K>8\)就不用處理了，
所以可以把\(K=1,2,...,8\)再預處理，做到時間複雜度\(O(N log log N +T)\)。

2.Autocomplete

題意比較難理解，其實就是在讀到字串\(S\)的時候，計算已經讀入的字串中，
跟\(S\)的最長共同前綴有多長，\(ans+=共同前綴長度+1;\)，如果等於\(S\)長度，\(ans--;\)。
顯然trie支援如此詢問共同前綴並增加資料。
就這樣做一做，時間複雜度\(O(L)\)，其中\(L\)為字串總長度。

3.Winning at Sports

兩種情況分開來做DP，狀態都是訂dp[自己得分][對手得分]。
我是用Top-down來做，基本上不難列轉移關係。
只要注意stressful的DP轉移過程與對手的最終的分有關，大可對每個\(T\)都重做一遍。
時間複雜度\(O(AB)\)，\(A,B\)分別為自己與對手的得分。

4.Corporate Gifting

實際畫一下，會發現單一人的錢不會太大，實測不超過\(11\)。
不知道怎麼確切的卡上限，大可切個\(log_2N\)，取\(20\)，
理由：一個人的錢為\(x\)時，與其有關的人必定包含\(1,2,3,...,(x-1)\)的錢。
這樣卡得其實很寬，不過足夠了。
從沒有子節點的點開始，往上處理，記錄（這個點用\(x\)錢時，這個子樹的最小花費）。
（處理順序要確保：當一個點被處理時，其所有後輩都已處理完。）
依序往上就完成了！ 時間複雜度\(O(N log N)\)。

如果用到遞迴，要小心自己電腦上的stack overflow，可以用以下編譯參數處理：
g++ -Wl,--stack=0x2000000

2015/1/15

2015ioicampOJ6(區間最大連續和 by 線段樹)

連結：2015ioicampOJ6
邏輯不難理解，只是寫起來複雜、麻煩而已。
線段樹每個節點都保存「區間總和」、「區間最大左綴」、「區間最大右綴」、「區間最大連續和」，
（左綴、右綴定義仿照前綴、後綴，相信很好理解這種講法）
接著只要能轉移就好：
「區間總和」=左「區間總和」+右「區間總和」
「區間最大左綴」=\(max(\)左「區間最大左綴」\(,\)右「區間最大左綴」+左「區間總和」\()\)
「區間最大右綴」=\(max(\)右「區間最大右綴」\(,\)左「區間最大右綴」+右「區間總和」\()\)
「區間最大連續和」=\(max(\)左「區間最大連續和」\(,\)右「區間最大連續和」\(,\)左「區間最大右綴」+右「區間最大左綴」\()\)
有了以上關係之後，不管是build、query、modify，其實寫起來都一樣！

TIOJ1137(無向圖找割點)

連結：TIOJ1137
參考資料：建中講義(p.8~p.9)
經典的Tarjan's Algorithm ，不過我也是第一次真正寫。
一開始還寫了個假解，也就是對於根節點（這題保證圖連通，只有一個根節點），
我竟然判斷子節點的low值有沒有大於根節點的深度，而且還AC了！
還好寫完之後找了資料讀一下，才發現這個錯誤！
因為只是找割點，所以可以把back-edge跟回到parent的tree-edge混在一起也無妨。

2015/1/14

TIOJ1092(NPSC2006初賽)

連結：TIOJ1092
不知道要打什麼...
很單純的博奕問題，只要注意博奕問題中的「先手」是有選擇權的主動方，
以這題來講，主動方應該是站在圈外的人！
接著就是把邊反過來存、拓樸排序、依序處理。
因為一個小小的bug，害我拖了好久才弄完。

TIOJ1027(高精度開平方根)

連結：TIOJ1027
參考資料：直式開方法
其實這題沒什麼算法特點，比較接近給初學者練語法的題目。
（當然，屬於比較複雜的語法練習了）
我原本不會直式開方法，昨天亂戳題目戳到這題，突然覺得很好玩，就寫了。
最大的價值應該是這題逼我查資料認真的讀、學了直式開方法。
此外，如果會用比較傾向物件導向的寫法，例如開一個struct或class、寫建構子、重載運算子等，會比較好寫。

2015/1/13

UVa1153(相當於2014TOI初選第五題)

連結：UVa1153, 2014TOI初選
這題多虧CBD讓我找到一樣的題目，原本初選那題遙遙無解的。
不過出現在UVa還蠻可恨的，傳完等上5分鐘只得到Submission Error，
重複超多遍，而且這題又用到了「測資間輸出一行空行」以及「"before"但是可以同時」這些容易誤解的陷阱，
何況範測又給那麼弱，還好最後有讓我看到AC！
去年TOI1!時，室友跟我講了一個greedy：把它時間軸反過來，然後從可以選的工作中選能夠最晚開始做的
不過，在下面這種case會爛掉(TOI的輸入格式)
2
5 1
8 7
其實我一直深信上面那個greedy是對的，直到不久前才發現有這種情況會壞掉。
後來在FB社團有人討論，CBD就給了UVa的那題。
UVa那題有充分明顯的提示，所以不難想到解法：
1.按照deadline由小到大排序所有工作
2.依序加入這些工作，如果有擺不下的，就看看已經加入的工作有沒有花費比較長的，把它換掉。
很簡潔的算法，顯然步驟2.需要priority queue輔助，同時有很多東西其實不用記錄的。
複雜度：\(O(n\ log\ n)\)

SCC(Strongly Connected Components)--Kosaraju's Algorithm

reference data:

建中講義(最後兩頁)
演算法筆記
From Stanford

Stanford那個雖然是英文，但是寫得最好，另外兩個資料給的範例圖都太簡單、不夠複雜。
不過有些內容不交叉比對每個參考資料，可能會沒辦法理解。
SCC定義參考Stanford就好，這裡不贅述，重點是Kosaraju's Algorithm。
作法如下：
1.以類似於找拓樸順序的方法，對原圖\(G\)做DFS並記錄timestamp(差別在於，不要判環，所以反而會比較好做)。
2.將原圖的邊通通反向得到\(G^T\)。
3.按照步驟1.得到的偽拓樸順序(參考演算法筆記的說法)對\(G^T\)走訪，所有還未處理而被走訪到的點便屬於同一個SCC。

結束了!? 是的，算法內容看起來好精簡，而且每個步驟都是linear time，總時間複雜度\(O(|V|+|E|)\)
不過它的正確性實在讓人困惑，似乎不怎麼直觀。
在說明它的正確性時，先假設大家都知道對圖\(G\)以SCC做的縮圖會是DAG(縮圖定義參見Stanford)。
以下開始說明：
首先，因為縮圖會是DAG，所以縮圖必定存在拓樸順序。
假設我們已經知道每個SCC包含的點，將圖\(G\)的偽拓樸順序的每個點對應到所屬的SCC，
將重複出現的SCC中，偽拓樸順序較後面者刪除，如此便能得到縮圖中的一組拓樸順序。
這部份的理由也相對不易理解，再細說如下：

假設有\(A,B\in{G}\)為兩塊相異的SCC，\(u\in{A},v\in{B}\)兩點分別為所屬SCC在偽拓樸順序中最前面的點且\(u\)在\(v\)之前。
縮圖拓樸順序\(A\)在\(B\)之前不合法當且僅當存在路徑由\(B\)到\(A\)，
根據SCC及縮圖定義，此情況也等價於原圖中存在路徑由\(v\)到\(u\)。
假設上述內容成立，即存在路徑由\(v\)到\(u\)且縮圖拓樸順序\(A\)在\(B\)之前不合法，
因為\(u,v\)不為強連通(Strongly Connected)，所以必不存在路徑可由\(u\)到\(v\)，
考量DFS先找到\(u\)的情況，那麼\(u\)點完成時，\(v\)點還沒被遍歷；
反之，若\(v\)點先被遍歷，那麼在\(v\)後續的擴展過程中必定會遍歷到\(u\)；
以上兩種情況皆與「在偽拓樸順序中\(u\)在\(v\)之前」相矛盾，
故縮圖拓樸順序\(A\)在\(B\)之前必定合法。
（後半段的思考過程類似於單純的DFS找拓樸順序，但需注意圖上有環，因此若\(u,v\)不為所屬SCC在偽拓樸順序中的第一個點，此結論不成立）

並且我們知道，由任意一個點\(v\)出發，在\(G\)中能到達的點，其所屬的SCC必為：
1.與\(v\)同一個SCC 2.為\(v\)所屬的SCC在縮圖中能到達的SCC
再者，顯然將圖\(G\)的邊反向後，不會影響SCC的狀況，但在縮圖中，
因為是DAG，所以圖上的「祖先-後輩關係」會相反（雖然不是真正用詞，但是應該不難了解其意思）
如此一來，縮圖中的拓樸順序反轉後，便會是\(G^T\)的縮圖中的一組拓樸順序。
因此若我們按照最開始的偽拓樸順序走訪圖\(G^T\)，是按照圖\(G^T\)縮圖中的拓樸順序的相反順序走訪，
使得點\(v\)能抵達的點，若為上述的第二種情況（為縮圖中後輩SCC的點），那麼必定早已處理過了，
（因為是按照拓樸順序的相反順序）
那麼所有能抵達且還未處理的點便是與\(v\)同一個SCC的點囉！
這個算法完成了，算是蠻巧妙的~

至於題目與應用...我也沒有找到。