網頁

Thursday 24 March 2011

URAL 1691 - Algorithm Complexity

題目:
給出一個有向圖, 設 F(N) 為由 S->T 長度為 N 的 walk 的數目, 問是否存在一非負整數 k 和常數 C 使得 F(N) <= CNk
Input: Graph, S, T
Output: k 的最小可能值


題解:
題目十分technical, 其實是說 S->T 的 walk 的數目是否能寫成 N 的多項式 (有點像big-O 的定義), 即 F(N) = O(Nk)
仔細想, 如果不能的話其實就是指數式, 即 F(N) = O(cN)

在甚麼情況下會變成exponential呢? 首先想到的是如果每步都有多於1種選擇, 咁就變左ck, 如 sample 2
然後又想甚麼情況才是N2, N3 等, 就會發現就是把 N 步「分配」到不同的環中, 即 C(N,M) = O(NM)

所以, 先對圖做SCC
每個SCC可以分為數類:
1. 只有一個node
2. 一個簡單cycle
3. 以上皆否

明顯地, 如果S->T 能路過 type 3 的SCC, F(N) 就即刻變左 exponential
剩下的, 便是在縮點後的DAG中找 S->T 路過最多 type 2 的 path, 做 memorization dp 即可

怎樣判斷是type 2 還是 type 3 呢? 只要在該SCC中比較一下 |V| 和 |E|

還有URAL的stack size很細, 100000 個 node 做一次 dfs 都 stack overflow
解決方法: 我將由 1->n 改為 n->1 就過了..

Sunday 20 March 2011

小記

近幾次的 CF 的 SRM 都打得很差..

Friday 18 March 2011

URAL 1676 - Mortal Kombat

Problem
Given a N x M bipartite graph, determine which edges can be selected in a perfect matching.

Solution
First, find an arbitrary matching. If an edge is selected in the matching OR contains in any augmenting cycle, output that edge.

To determine whether an edge is in an augmenting cycle, find the SCC in the residual graph. See whether both ends of an edge is in the same SCC.

Trick: N may not equals M. My solution to this is add a dummy node in the left side.

Sunday 13 March 2011

POJ 2986 - A Triangle and a Circle

要搵一個三角形的一個圓形 intersection 的面積

做法: 對於三角形ABC 和圓C, union的面積 = [ABO ∩ C] + [BCO ∩ C] + [CAO ∩ C] (signed area)
而每一次計圓心三角形的 intersection 可分為4個case

另外, 使用 asin 和 acos 時, 應該 handle asin(1.00000..001) 的情況

Friday 4 March 2011

URAL 1699 - Turning Turtles

Problem
Given a W x H map where the passable cells form a tree. Q queries: what is the number of turns required travelling from cell (x1, y1) to (x2, y2)?

W x H ≤ 100000
Q ≤ 50000

Solution
Obviously it is a LCA problem. However, the problem is the weight of edges depend on 3 nodes (not 2). Assign weight[u][v] =

1 if parent[u], u, v is a turn
0 else

For Query(x,y), find z = LCA(x, y). Then find 2 children of z, x' and y', such that the path is x->x'->z->y'->y. The answer is sum[x]-sum[x']+sum[y]-sum[y']+IsTurn(x',z,y'). Special handle the case x or y = z.

I implemented a dfs to pre-process the tree for LCA queries. However it will cause stack overflow. Therefore I implemented a non recursive version tree traversal, using stacks. So complicated..