TCO 2010 Round 1

250 - 水題

500 - 兩個 register A,B 一開始 set 做 1 , 每次可以做 A = A+B 或 B = A+B, 問要將 A set 做 L (L <= 10^6) 最少 operation 數

1000 - given一個城市, directed graph, 其中一個 vertex 係酒店, 而家俾你 set 一些 tour, 每個 tour 收費 P, set 幾多條 tour 都得, 條件是每個景點 (vertex) 最多只能被一條 tour 所用, 每個 tour 的成本為 edge 的 cost, 求最大 profit  (|V| <= 50)



250 雖然頹, 但精神狀況太差, 又有頹bug, 得返~220

500 USACO 有條少少似, 不過果條唔識做. 打個表出黎睇下都睇唔出 pattern, 於是試下1000

1000 諗左陣, 發現係 max cost flow! 做法大約係拆點, hotel out = source, hotel in = sink, source 連出去之前有條容量無限 cost 為 P 的邊, 然後每 sent 一個 flow 就試下 update current max

諗到後很興奮, 因為睇落去得好少人做1000. bug唔多, 完場前5mins submit



challenging phase 由於500唔識做好難cha人500, 1000大家又都係flow咁

到system test.. 驚見 1000 failed system test 了  =(
就係咁, 跌出rank850之外, 無得出線..



之後搵返, 原來係做SPFA時,  initialize 我 set vis[ ] = -1, 但由於有負cost, 所以有機會做成明明無 path 都想起返條 path 出黎, 搞到 TLE ..

改善: 實現算法時要諗得全面, 尤其係topcoder, 與其貪code短, code得穩陣更重要