URAL 1557 - Network Attack

題目一句講完:
給出一個無向圖 G (可以有重邊/自環), 問有多少種方法 remove 2 條 edge 使得 G 變成 disconnected

一開始從 build BCC 的方向想, 可分為兩個 case: remove 一條 bridge + 任意, 以及在同一個 BCC 內 remove 兩條
不過想不到怎樣做 case2, 所以放棄了
後來想到可以用 DFS tree, 因為 tree 比較容易處理

先找出 G 的任意一棵 DFS tree
首先, 要使得 G disconnect 的話至少要 remove 一條 tree edge, 這樣就限制了很多可能性
以及, DFS tree 的其中一個特性是沒有 cross edge

Case 1: remove tree edge + remove back edge

很簡單, 只要記錄 subtree 的連通性便可以
Compute dp[x][y] = x 的 subtree 中有多少條 back edge 連到 y
便可以知道 x 的 subtree 有沒有連到外面, 如果是 0 條 edge 或 1 條 edge 就有方法做成 disconnect

Case 2: remove tree edge + remove tree edge

首先再分成 2 個情況: 兩條 tree edge 有沒有 ancestor 關系
如果沒有就很簡單, 做法和 case 1 十分類似

如果有的話則比較麻煩, 如圖, 紅色是想 remove 的 edge, 現要判斷綠色部份是否有連到藍色部份
而且要在 O(1) 內判斷
其實可以改變一下 dp[][] 的定義, 利用沒有 cross edge 的特性, 可知 x 的 subtree 只會連到 x 的 ancestor
dp[x][y] = x 的 subtree 中有多少條 back edge 連到 x 的第 y 層 ancestor
再使用 partial sum, 則可快速判斷

總時間為 O(N²+M)

URAL 1128 - Partition into Groups

由於想不到, 所以看 solution

做法很簡單, 先隨便 partition
然後 while child x has ≥ 2 enemies in his group, move child x to another group

Let badness = | { (x, y): x, y are enemies and lies in same group } |
可見 badness 在一次 operation 後會下降至少 1
而 initial badness ≤ 3N, 及 0 ≤ badness
所以一定有 solution, 而且 O(N) 找到

URAL 1464 - Light

很感動, 搞了幾天終於過了
開始有信心做其它 sweep line 題

詳細算法在 kn 的 blog 有, 都是 sort by angle + sweep line
不同的是我用的是 heap
開頭以為可以用 stl priority_queue, 但在處理 delete 時, 不能像以前 expire + reach top 才 pop, 因為只是存在在 heap 中就會打亂次序
所以只好人手寫一個 heap

在發現無數的 bug (例如離散角度時沒有處理 -PI 和 PI 同時存在等等) 後, 加上無限的 WA, 終於過掉了!
之後再把無用的 code 刪掉, 竟然可以 runtime 第一
雖然其實沒有甚麼大不了, 但還是興奮了一陣子

Petrozavodsk Summer 2011. USU Contest

好像是俄羅斯 IOI camp 的比賽 (好似係), 據聞難度十分高
見在 URAL 上舉行, 忍不住去玩

開始後不久見到有人過 J
首先想到 f(n) 可寫成一堆連續數的 Fibonacci 次方
如果有 f(n) 的質因數分解 form, 可以輕易找到答案

算法1 - 把 1~n 分解, 把每個數的質數加進 primes[] 中, N * sqrt(N)
submit test case 5 便 TLE..

算法2 - precompute 1~n 的質數, 分解時只試質數
submit - 還是 TLE..

算法3 - 分解一個數時, 只試質數, 再加上如果剩下的數是質數便 break
加上這個優化後 (%mod 變成 -mod 那些應該是一定要的) 終於過了..

之後做 D
如果 n = a*a*b, 那麼 a³ ≤ n 或 b³ ≤ n
所以只要試 n^1/3 以內的數


K - KMP + DP
狀態是 dp[i][j] = 前 i 個 character, prefix 為 j 可以 match 到多少次
但 '?' 轉移時有些麻煩, 因為不能 greedy 地 match 下一個, 我的做法是不斷走 fail 更新, 理論上好像會達到 N³, 不過還是過了

URAL 1580 - Dean's Debts

首先 N 個 unknowns 至少要有 N 條 equations
多過 N 條的話只保留 linear independent 的
之後便聯想到一個 |V| = |E| 的 Graph, 即頂環樹

有一個頂環樹, 一定是從環的部份開始解
但是不是每種環都有唯一解, 要 odd cycle 才可以 (用 determinant 可以證明)
所以每個 connected component 要至少有一個 odd cycle 才有機會有唯一解

環的解可以綫性計算, 然後順著邊計算 tree node 的解
之後多餘的 edge 只要 check 是否 consistent 便可以

總時間 O(N+M)

URAL 1833 - Hopes of Rowing

題目可轉化為一堆 bonus[a_i] + bonus[b_i] ≥ k 的不等式
By 直覺, 一定存在一 optimal solution 其中 bonus[i] 為 k/2 的倍數 (0, k/2, k)
(其實好像可以 prove, 不過我不懂)

先假設上面的前題正確, 但是三種可能性很難處理, 所以先統一所有 bonus 都是 k/2, 那樣就只剩下兩種可能性
再轉化為 (其實這 step 不是這樣想出來的, 而是由 solution 推導出來):

bonus1[a_i] + bonus2[b_i] ≥ k/2
bonus1[b_i] + bonus2[a_i] ≥ k/2

其中 bonus1[i] 和 bonus2[i] 都是 0 或 k/2

把 (bonus1[a_i], bonus2[b_i]) 視為一條 edge, 會得到一 bipartite graph, 而且要做的其實就是 minimum vertex cover!

由 König's theorem 可知, 對於 bipartite graph, minimum vertex cover = maximum matching
所以之後只要做 matching 再找出 cut 便大功告成

URAL 1691 - Algorithm Complexity

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


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

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

所以, 先對圖做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 就過了..

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.

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..

URAL 1770 - The Party of Ural Champions

A useful observation: The original graph can be obtained from removing some edges from the given distance matrix. Futuermore, if d[i][k]+d[k][j] = d[i][j], then edge (i → j) may be removed.

My solution used Reversed Floyd-Warshall algorithm. The basic idea is like

for k=1 to n
  for i=1 to n
    for j=1 to n
      if d[i][k]+d[k][j]==d[i][j] then d[i][j]=INF

However, the problem do not allow directional edge, so we need to avoid setting d[i][j]=INF but keeping the edge (j → i). To solve this problem, I used the following method:

for k=1 to n
  for i=1 to n
    for j=1 to n
      if d[i][k]+d[k][j]==d[i][j] AND r[j][i] then d[i][j]=d[j][i]=INF
      else if d[i][k]+d[k][j]==d[i][j] then r[i][j]=1

At last, don't forget to see if the input matrix satisfy triangular inequality

URAL 1043 - Cover an Arc

First, find the center and the radius of the circle.
Since we are looking for a bounding rectangle, we need to calculate minX, maxX, minY, maxY.

Intuition: Just compare with the up-most, leftmost, rightmost and the down-most point of the circle!
Next, we have to determine whether a point on a circle is on an arc.

Arrange the two ends of the arc A,B such that A->B is clockwise.
To check whether P is on the arc, just see whether triangle APB is clockwise or not, which can be easily done by cross product.

Last Bug:

mnx = (int)(mnx+1e-10);
mny = (int)(mny+1e-10);
mxx = ceil(mxx-1e-10);
mxy = ceil(mxy-1e-10);

Correct version:

mnx = floor(mnx+1e-10);
mny = floor(mny+1e-10);
mxx = ceil(mxx-1e-10);
mxy = ceil(mxy-1e-10);

Incorrect version won't work with negative numbers..

URAL 1130 - Nikifor's Walk

好像是很經典的題, 題解十分巧妙
做法在這裏

回溯答案我用了tree去記錄, 如果merge i+j, 則由i到j連一條weight 0的edge; 如果merge i-j, 則連weight 1的邊, 最後從source做一次dfs
其實那些properties對我來說並不明顯, 所以還是在這裏做個記錄吧


Claim 1. For any two vectors u,v where |u|,|v| <= L, either |u+v| <= sqrt(2)*L or |u-v| <= sqrt(2)*L

Proof.
|u+v|² = |u|²+|v|²-2|u||v|cos(θ)
|u-v|² = |u|²+|v|²+2|u||v|cos(θ)
In either case, the square of magnitude will not greater than |u|²+|v|² = 2*L²


Claim 2. For any three vectors length not greater than L, it is always possible to choose 2 of them such that the length resultant vector performing addition OR subtraction is not greater than L.


Proof.
I seen a proof on other's blog using the formula above, using the fact that there must exists a θ >= 120 degree.

Let three vectors be v,w,u.



Let the brown vector = v.
If v+w or v+u falls in yellow, then the length of v+w or v+u <= L
Else if v+w or v+u falls in red, then the length of v-w or v-u <= L
Else, v+w and v+u falls in blue or green, then the length of w+u or w-u <= L

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.