網頁

Saturday 27 November 2010

HKOI 2011 Final Event Detail

Final Event

Date:Saturday, 4th December, 2010
Registration Time:Senior Group: 8:30 a.m.
Junior Group: 1:30 p.m.
Event Time:Senior Group: 9:30 a.m. - 12:30 noon
Junior Group: 2:00 p.m. - 5:00 p.m.
Venue:Rm924, Ho Sin Hang Engineering Building, The Chinese University of Hong Kong, Shatin, Hong Kong.



Monday 15 November 2010

SPFA: Negative Cycle

剛發現原來一直寫錯 SPFA 中的 detect negative cycle
以前一直以為是 update ≥ N 次則有負圈
實則是 入queue ≥ N
因為每入一次 queue, 就表示 shortest path 所經的 edge 數 +1
由於無負圈的 shortest path 最多只走 N-1 條 edge, 所以入 queue ≥ N 次 = 有負圈

Thursday 4 November 2010

POJ 2152 Fire

Problem statement

Given a undirected tree, each vertex can be selected or not. The cost is defined as:
    If vertex x is selected, cost = prize[x]
    If vertex x is not selected, cost = distance to the nearest selected vertex
In addition, for each vertex x, the distance to the nearest selected vertex must <= distance[x]

Find the minimum cost, |V| <= 1000

Solution

其實都幾 obvious 係 dp on tree
不過個 state 比較難諗

dp[x][y] = minimum cost for subtree rooted at x, with the nearest vertex is y

就係個 state
進行 state transfer 時, 主要分的 case 為
1. y 在 x 的 subtree
2. y 不在 x 的 subtree
(畫下就可以推到)

time complexity = O(N2)

類似方法應該可以解決 Hsinchu 2009 的 D

Monday 1 November 2010

Size Balance Tree vs Segment Tree

假設想有一個data structure, 想support:

1. add(x)
2. rank(x)
3. delete(x)

在O(log N)時間內做到

做法可以用陳XX的Size Balance Tree, 不過個人覺得code很長, 在爭分奪秒的ACM上, 用 segment tree 代替可能更好

先把所有 data discretize
(不過可能就要store起所有query.. um..)

揼個 segment tree, 每個 node store sum = left subtree's sum + right subtree's sum
leaf's sum initialize = 0

每次add(x) 就把對應的 leaf set 做 1
delete(x) 就 set 做 0
rank(x) 就在途中加起 left subtree 的 sum