Individual Training 29/06/2010

F - PKU 1065 Wooden Sticks

給定 N 組數 (a_i, b_i), 每次用一個 cost 可以 cover 一條 sequence 且每項的 (a_i, b_i) 都小於之後的那項, 問 min cost


首先很直觀的想到用greedy, sort by (a,b), 然後順著做, 如果未被 cover 就拎, 再順序掃後面的, 拎到就拎

這個greedy是對的, 時間O(N²)



後來學到 O(N lg N) 的做法, 方法也是 sort by (a,b), 然後找 b 的 longest decreasing sequence!

想一想也發現是很合理, 條 LDS 的每一項就是代了每條 sequence 最尾的那個 object
由於搵 LDS (LIS) 可以 O(N lg N), 整體也是 O(N lg N)





D - PKU 2036 I Conduit!

給定平面上 N 條線段 (input 準確至小數後兩位), 問合併哂 overlap 的後實際上有幾多條線段


其實呢個係做ctli在hkoj上的The keep都有寫過, 方法是把所有segment sort by

1. 斜率
2. y - 截距
3. x1 值 (設 x1<x2)

之後順序判斷+合併就是了, 要注恴的是無限slope的segment

由於見input只去到小數後兩位, 明顯地可以純整數咁做 (記分數form), 由於我用左

scanf("%d.%d",&x,&y);
p=x*100+y;

去食input


WA 兩棍後才發現我會將例如 3.05 和 3.5 都化作 305

頗深刻的bug

IOI 2002 Utopia Divided

諗左好耐, 最後都係去左搵果年既 report

的確是很巧妙的做法..! 不過唔易諗到



定義 alternating sequence為一數列 X1, X2, X3, ... Xn
其中 |X1| < |X2| < |X3| < ... < |Xn|
而且 sign 是互相交替的

例如 -1,4,-6,7
和 2,-3,7,-10




alternating sequence 有一個性質
就是 整條數列之和的正負 等同於 Xn 的正負

例如Sum (-1,4,-6,7) = 4  [與7同號]
Sum (2,-3,7,-11) = -5  [與-11同號]



1D 的情況
要將 n 個數字 X1, X2 ... Xn 排好和 assign 正負值, 而且頭 x 個之和是指定為正或負 ( S[x] = '+' OR S[x] = '-' )




先將果 N 個數字由小至大 sort
然後 assign 正負相間, 做成一條 alternating sequence

咁一開始取值正定負呢?


由 alternating sequence 的特性, 為了滿足 S[n] , 因此 Xn 應與 S[n] 同號

這樣便可確保 Sum( X1,X2,X3...Xn) 的正負號必滿足 S[n]
而且入面數字的次序點調都得


咁點先可以滿足 S[n-1] 呢?
由該性質可得, 如果可以整到一條 長度n-1, 最尾那個數字的正負號=S[n-1] 的話, 便能滿足 S[n-1]


現在是 X1, X2, X3, X4, ...Xn
有兩個選擇,

1)
X1, X2, X3... Xn-1

2)
X2, X3, X4... Xn


用邊個選擇? 就係睇 S[n-1] 同 Xn 同號 還是 同 Xn-1 同號 !!

由於是一條 alternating sequence, Xn 必與 Xn-1 不同號, 因此總能找到與 S[n-1] 同號的

By induction, 重覆此步驟 n-1 次, 便能滿足 S[1]..S[n] !


例子:
n = 5
S[ ] = {-,-,-,+,+}
X[ ] = {2,3,4,5,6}


Step 1 [ assign 正負, 使 X5 與 S[5] 同號 ]

X[ ] = {+2,-3,+4,-5,+6}


Step 2 [滿足 S[4] ]
X[ ] = {-3,+4,-5,+6,+2}

Step 3 [滿足 S[3] ]
X[ ] = {-3,+4,-5,+6,+2}

Step 4 [滿足 S[2] ]
X[ ] = {+4,-5,-3,+6,+2}

Step 5 [滿足 S[1] ]
X[ ] = {-5,+4,-3,+6,+2}

IOI 2002 The Troublesome Frog

用了一個看似是 O(N³) 的方法做..

pick 2 點, check 下佢可唔可以成為 path 的頭 2 點, 然後再行條 path , 睇下係咪 path 上的每一點都存在

另外很重要是加了一些優化

1. 由左面的點開始做
2. 如果假設條 path 是 valid 但長度也不長於 current max, 就唔使 check 了

所以看似是 O(N³) 的方法在 pku 只 run 了 16ms


不過再想, 其實可能是 O(N²) 來的

照解題報告的方法, 如果將兩點 (A,B) 視為一個 vertex, 咁只有 N² 個 vertex

而由於加了那2個優化, 應該可以確保每個 vertex 最多只行一次

Individual Training 22/06/2010

今次題目偏向數學..

比較興奮的是做到B (雖然其它人一開波就做到) , 但這題其實幾年前已見過, 但一直都未識/未敢做, 算是又對 number theory 踏前了一步..


F - PKU 1997 Word Puzzle

題目: given 一個 200*200 的 lowercase letter array, 再 given 1000 個長度不多於 20 的字串, 問係個 2D array 度起哂 d word 出黎後 (8方向) , 剩返邊d character


做法: 直接搵會超時 (200*200*8*20*1000) , 所以我將果 1000 個 word 用一棵 trie 儲起哂, 每次向8個方向行直接知道有無字, 將複雜度降為 200*200*8*20



B -  PKU 1061 青蛙的约会

題目: 在一個長為 L 的 ring 上, 兩隻青蛙分別為於 position x 和 y 上, 每一個 time period 它們都會向同一方向跳 m 和 n 格, 問最快幾時先會同時在同一個 position, 可以無解

L <= 2100000000


做法: 印象中第一年玩HKOI mini comp 就見過呢題, 不過當然唔識做.

如果把方程寫出.. 就是

x + T*m = y + T*n   (mod L)

T(m-n) = y-x   (mod L)

簡化一下.. 就是要解 T*a = b   (mod L) , 也就是所謂的解模方程

諗左好耐, 發現同 extended euclidean algorithm 有關 !

T*a = b   (mod L) 即

T*a + L*k = b

如果對 a 和 L 搵 GCD 的話, 由 extended 果 part 可以有

a*i + L*j = gcd(a,L)

結論 1: 如果 b % gcd(a,L) 不是 0, 則輸出 Impossible

如果將條方程左右乘大 b/gcd(a,L) 的話.. 就得到

a*i*b/gcd(a,L) + L*j*b/gcd(a,L) = b

解得 T = i*b/gcd(a,L)

但注意這只是 T 的其中一個解,  T 應該有無限個解的
output 要最小而非負的 T

由於 a*i + L*j = gcd(a,L) , 得知 T 的每一個解相差 L/gcd(a,L)

即一般解為 T + r*L/gcd(a,L) ,  r = integer

有呢樣野搞兩搞就可以將佢變返做最小而非負


其實做到呢題真係好開心, 算係一個突破吧
平時做 judge 一定唔會自己諗到, 要在果個環境下先會做到..



仲有一題很難但值得打出黎..

D -  UVa 10692 Huge Mod

搵 a₁^a₂^a₃...^a_n mod m

有少少想法.. 但如果真係要做應該有排 struggle ...

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得穩陣更重要