網頁

Monday 27 December 2010

POJ 2826 - An Easy Problem?!


A geometry problem. Not complex, but need to be careful and it is easy to miss some cases.

First, there are some conditions that the answer will be 0.00
1. Either one segment is horizontal
2. The segments have no intersection
3. The segments are parallel

If the segments passed those cases, then find the intersection point P of the segments.
The area will be a triangle.



However, there are one more case that needed to be consider.



Saturday 25 December 2010

URAL 1124 - Mosaic

Solution

Model the solution to a graph.
Each box is a vertex, and if box x has a piece with color y, add a directed edge (x, y).
Then, the number of movement is the number of edges plus the number of jumping to another node.

If the graph is undirected, then what we need to do is count the number of odd degree node. (211 homework!)
However, since there are equal number of pieces for all colors, that means for all node x, the number of incoming edges = number of outgoing edges.
That means the number of jumping required = number of connected component - 1

Overall time complexity = O(|V|+|E|) = O(M2)

Thursday 23 December 2010

URAL 1077 - Travelling tours

Solution

First, the number of tours = |E| - |V| + |C|, where |C| is the number of connected component.
The algorithm will explain it.

For each connected component, find an arbitrary spanning tree.
For each back edge (u,v) in the spanning tree, the back edge (u,v) + the tree edge connecting u to v forms a cycle.
Since the back edge is used only in this cycle, it is a valid tour.

Hence the number of tours = the number of back edges = |E| - number of tree edges = |E| - |V| + |C|.

This is optimal because after we create a spanning tree, each cycle must include some back edges.

Friday 17 December 2010

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(N2 lg N), 所以很理所當然的用了方法1
每次找出 B 由 current 開始的 prefix 與 A 的 suffix 中最長 LCA 的一條
即是在 SA[] 中, 分別向上和向下找出第一條在 A 開頭的suffix

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

Monday 13 December 2010

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了

Sunday 12 December 2010

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(N2), 所以運用了一個很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了(想像)

Sunday 5 December 2010

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。

Wednesday 1 December 2010

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,不過比賽就是會有遺憾的。