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.

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(M²)

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.

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了