USACO DEC10 Threatening Letter

這是 USACO DEC10 GOLD division 的題目, 據說提交率/通過率很低
不過說穿了其實不難, 只是看對 Suffix Array 的運用是否熟練

題目大意是, 給出兩條 string A, B
現在可以不斷 copy 出 A 的一段 substring, 問最少要 copy 多少次去砌出 B
N ≤ 50000

首先想到的是很 greedy 地砌出 B, 即在 A 中選出和 B 的 prefix 有最長 common prefix 的suffix
所以就要用 suffix array
題解 suggest 了兩種做法

1. 設 S = A+B, 對 S 做 suffix array, 然後每次在 S 中 process
2. 對 B 做 suffix array, 然後不斷做 binary search

由於我覺得方法 2 好像在 worst case 中會達到 O(N² lg N), 所以很理所當然的用了方法1
每次找出 B 由 current 開始的 prefix 與 A 的 suffix 中最長 LCA 的一條
即是在 SA[] 中, 分別向上和向下找出第一條在 A 開頭的suffix

版本1 我是真的向上下掃一次的, 其實理論上應該會去到 O(N²), 不過還是水過了
版本2 對每條在A開始的 suffix 中向上下掃, O(N) preprocess (case 10 run 了 300ms)

POJ 3415 Common Substrings

做做下竟然要用到尋日果個data structure!
真不知是巧合還是甚麼

很正路的先compute S=A+B 的suffix array和計算height array
然後數法就是對於每一條在A開頭的suffix去數map到幾多條B開頭的, 分別向上和向下掃一次
所以就要用昨天的data structure去計算了, 因為LCP在SA中是decreasing的

題外話
我的O(N lg N lg N) 武器 run 了 34xx ms
但貼左個 O(N lg N) 的就變成 18xx ms了

COCI 2010/2011 Contest 3

香港時間2200-0100..!
十分合適我的生理時鐘

Q1-Q4: 頹
Q5: 望下去很有趣, 直覺會想到
最後還是做到了, 方法大概是

計算的次序:
1: [1,1]
2: [1,2],[2,2]
3: [1,3],[2,3],[3,3]
4: [1,4],[2,4],[3,4],[4,4]
..

首先想到的是每一個range都儲著max和min
做到第i步時, 把a[i]和每一個range的max和min比較和update, 再把每一個range的(max-min)加落answer

但續個range計和update是O(N²), 所以運用了一個很trivial的fact:
(max[1]-min[1])+(max[2]-min[2])+...+(max[n]-min[n]) = (max[1]+max[2]+...+max[n])-(min[1]+min[2]+...+min[n])

即是, 每一步儲著兩條list: max list 和 min list
而這條list要support以下operation
1. Push(x) - change all elements smaller than x to x
2. Sum() - sum of all elements

然後就想到條list其實就是一條類似stack的東西, 而每一個entry儲著frequency和value, 其中value是increasing/decreasing的
每一次Push(x)就一直pop走大於x/小於x的entry, 並累計frequency, 最後push返落條list度, 途中maintain Sum
由於每一個entry只會入/出條stack一次, 所以整個算法為O(N)

Q6: 未想到, 暉好像想到, 其實這樣挺好的, 因為如果我們一隊的話便可以把所有題目solve了(想像)

ACM ICPC 2010 - Kaohsiung 戰記

照舊是由我分題目。這次只有一份題目, 和training的時侯一樣。分好後便設定好vim, gedit等環境, 這次用的是Linux, 加上keyboard十分順手, 令打字速度提升了10%。一開始看到J, 立即發現是很簡單的動態規劃, 便上機了。寫到一半呀暉告訴我A是赤裸裸的最大生成樹, 加上看到不少隊伍過了A, 便先寫A, 秒殺之。

24 min - Problem A - MST (1Y ; GagGuy)

過了後繼續寫J, 過了樣例便提交, 返回WA。此時whh的F可以做, 是很經典的二分圖匹配, 便換他上機。不久, 發現了J的錯處, 改之, 第2個Yes。

37 min - Problem J - DP (2Y ; GagGuy)

過題後呀暉問了我題D的一些東西, 和最近點對有關, 我便告訴他中大一直以來的做法, 便列印whh的F並由呀暉做D。我便隨手拿起G看看, 原來是prufer code, 211才剛學完, 不過不太肯定做法, 便先用樣例來試驗。過了不久, 便傳來呀暉射鵰的聲音。

50 min - Problem D - Closest pair (1Y ; Fai)

此時whh也找到F的錯處了。我便找呀暉討論一下G, 確定了做法。本來我打算寫的, 但是呀暉告訴我B是一條計算幾何的題目, 我想用些時間準備一下, 便很放心的把G交給呀暉。同時, whh的F也過了。

56 min - Problem F - Bipartite matching (1Y ; whh) 

B是一條和判斷相似圖形有關的題目。由於數據很小, 應該可以用很直觀的方法做。於是便先計劃一下怎樣寫。不久, 便傳來第5個Yes。

64 min - Problem G - Prüfer code (1Y ; Fai + GagGuy)

由於頭5條都做得頗順利, 使我們一度在scoreboard上稱霸。此時的分工是由我做B, 呀暉做E - 一條頗麻煩的題目, whh看H - 一條很長的題目。準備了一會後, 我便開始寫B。寫的過程不算順利, 很多細節要處理。因此中途先給呀暉做E。然後就開始卡題了。我的B和呀暉的E都不斷返回WA, 眼見其它大學不斷超前我們, 而我們又沒有題可以過, 使我十分焦急。幸好, 呀暉的E在第3次提交時通過了。

172 min - Problem E - Ad Hoc? (3Y ; Fai)

我繼續做B, 而呀暉和whh聯手看H。H是一條graph題, 但看似不簡單。這時我才發現理解錯了B的題意, 但更改也不算太麻煩。可惜仍是返回WA。此時他們的H想到了做法, 便先給他們寫H, 可惜又返回WA。此時剩下一小時多一點, 已經有不少隊伍9題, 我們又卡了2題, 使我再一次十分著急, 便先出去吃東西冷靜, 並整理了一下思路, 決定換另一種方法寫B。而他們再看一次H後, 發現好像理解錯了, 把題目深化了很多。回來後重新寫B, 並處理了有重點的case, 但仍是WA。幸好, 在封board後18分鐘, 我們的H在更改後通過了。

258 min - Problem H - Shortest Path (2Y ; whh)

剩下40分鐘, 而我又覺得B差一點就能過了, 呀暉的C好像又很有想法, 使我一度想過上9題的希望。接下來的時間都是我和呀暉交替寫B和C, 可惜最後B仍是不能通過, C則不夠時間完成。最後以7題結束, 排名12。

ACM ICPC 2010 - Jakarta 戰記

這是 IsolatE 有史以來最發揮到 teamwork，很認真也很開心的一場 acm。
Scoreboard : http://competition.binus.ac.id/icpc/result/final.html


一開始便夾好了由我分題目，自己分到了數條graph的題目。通常 A 較簡單，但一看 A，怎看也很難，先放下。然後看看 B，二叉樹計數，直覺是動規規劃。這時whh已差不多完成 C。再想了一會 ，whh 便作出了比賽的第一個提交，發現是全場第一個提交，1Y。我接著上機做 B，但再想一想，發現有些地方不清楚，便先給呀暉做 D。然後看到 F，疑似是強連通分支，這時呀暉提交了 D，WA。此時 whh 可以做 I，不久呀暉發現 D 的錯，第2個Yes。緊接著 whh 的 I 也很快 1Y了。輪到我上 F，很熟練的寫出強連通分支，寫完提交，WA。 然後想起SCC收縮後形成的是有向無環圖，我卻當成了樹，很低級的錯誤，修改，第4個Yes。之後呀暉上機寫I，我則看whh給我的E，也是和樹有關的題目，十分合我的口味。一開 始想到了輕重邊割分，但細心想，可以用簡單的 DFS+LCA 代替。不久，呀暉完成 J，提交，WA。在等待列印的時侯，我上機寫 E，由於有武器的關係，很快便完成，過不了樣例，由於未有其它題目可以上機，因此可以很奢侈的輸出訊息除錯。中途呀暉發現 J 的錯，第5個Yes。發現找LCA出錯了，但又找不到是哪裏錯。時間一秒一秋的過去，終於發現打少了一個分號，眼殘了。改回，立即過樣例，提交，1Y，第6個Yes。和whh討論B，呀暉則研究A。B的動態規劃是O(N^3)，應該超時，因此遲遲未敢上機。whh指出總時間應該會是O(N^2) ，於是便開始寫了。寫到一半覺得很多細節，便先讓給呀暉做 A，中途whh 發現可以最後才乘以C(m,n)，把動態規劃降為O(N)! 這時想起武器中有求C(n,r) mod P 的快方法，便很興奮的打下去。這時和上一次過題目差不多一小時了，有點焦急。過樣例，提交，返回RE。和whh一起除錯，同時呀暉提交的 A 也 WA了。這時兩題也卡了，有點危機的感覺。試了一個case，發現迅速RE了。原來理解錯了武器中的參數，立即修改，擔心了一會long long的問題，這時呀暉的 A 也改好了，不久我也提交 B，出現第 7 和第 8 個 Yes。剩下兩題，一題是有點難的數學題，另一題竟是training中見過的AC自動機+DP，但我沒有太大信心可以寫出。這時分工是 whh 和呀暉想 G，我想 H。需然知道 H 解法的大概思想，但很多細節也很麻煩，預計在比賽中做到的可能性不高。不久後便封board了。差不多時侯他們的 G 也可以寫了，呀暉和whh每人負責一部份，不久便完成了。提交，TLE。想辦法優化，再改，再試，第2個TLE。這時大約餘下20分鐘，焦急，再改，再試，再提交。最後，第9個Yes就出現了(293+3)。興奮得跳了起來。最後以9題結束。後來得知冠軍也是9題，就感到有些可惜，如果之前做回training時做不到的那題AC自動機的話，我有信心在半小時內完成 H，不過比賽就是會有遺憾的。