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

IOI 2001 Twofive

其實2個query最終也是要知道:

"Given current table, return the number of ways to fill the rest of the table"


單純的 recursion 會超時

如果是由 'A' 到 'Z' 看看有哪些未用, 然後填落去的話
由於是由小至大地填, 所以一定不會出現唔 valid 的情況



假設原本的 table是

A B C D E

F G H * *

I J * * *

K * * * *
L * * * *

例如某些方法填了 M 和 N,

A B C D E

F G H M *

I J N * *

K * * * *
L * * * *

A B C D E

F G H N *

I J M * *

K * * * *
L * * * *

這兩個方法之後再砌的方法的數目是相同的
重點是「形狀」!

可以用狀態 dp 去避免重複運算

dp 的狀態是每一row填了多少格 (不會中空, 一定是由左開始填)
每次加一個新的字母一定是加在某一row的後面

其實思路不是太複雜

不過這個構做法並不容易想出來
我是看著 sample code 來揼的..

Grey Code

scanf("%d",&n);
for (int i=0;i<(1<<n);i++) printf("%d\n",i^(i>>1));

霸氣。

POJ 2432 Around the world

今日打 individual 有呢題..
其實之前都見過不過唔識做

不過做左2題之後有一題勁難一題勁煩..
逼於無奈要攻呢題




題目大意 -

地球上有 N (N<=5000) 個 farm, given 它們的經度 (0..359), 有 M (M<=25000) bidirectional path 連接某些 pair farm, 行這些 path 都是以最短 (向東飛/向西飛) 方法到達

現在要環遊世界 (唔一定要 visit 所有 farm) , 「環遊」的定義為由 farm 1 開始, 行一條 path, 回到 farm 1, 而且 順時針飛行距離 不等於 逆時針飛行距離 (其實呢個唔係環遊的必要條件, 只是充分條件)

問: 最少要飛多少程




嘗試過各種 dp 的方法都失敗
BFS 又唔知幾多 states 先夠

係呢個灰暗既時刻, 突然想到把所有 node(#farm, distance difference) 扔埋入個 map .. 再開條 stl queue 硬做
諗住實 TLE, 點知.. AC!

仲要係250ms左右, 比想像中快很多

估計係因為實際狀態遠比想像中少, 同埋好多case好快就reach到終點
之後上USACO睇official solution, 都係差唔多 - -' (不過佢題解得solution code)

IOI 2001 Depot

三個字: 倒著做

原本是放數字入去, 其實等同於數有幾多個方法抽返 d 數字出黎

1) row 1 最右的可以就咁抽出
2) row 1 的數字可以抽走, 但留下空格
3) 對於空格, 可以係下面果行搵個適合的數字抽出黎填返, 然後再填返下面的空格

其實係睇寫 recursion 的功力..

South America 2009

#	Solved	Score	A	B	C	D	E	F	G	H	I	J	K
Hussar	10	1055	1/48	1/56	-/-	2/37	1/69	3/224	2/202	3/159	2/27	1/13	1/80
GAGGUY+AC	10	1354	1/33	1/43	-/-	4/296	3/37	1/244	1/165	1/203	1/62	1/54	1/117
Prof. QQ	8	1361	2/117	2/73	-/-	1/67	3/150	-/-	-/-	5/303	6/152	1/7	3/192
BDJ	8	1367	1/206	1/117	-/-	2/130	3/72	-/-	1/-	3/282	4/144	1/16	3/200

(Copy from kn)

開局不是很好, 很久才過到第一題



Summary
Team members: GagGuy, AlanC
Solved: 10/11
Penalty: 1354


Process
A (+0)  dp on tree
E (+1)  AC, math + 二分, hardcode一些東西打錯
B (+0)  simulation
J (+0)  by AC
I (+0)  sorting
K (+0)  在 [1,1000] 中記錄會影響個 value 的點
G (+0)  有點難度, 有很多方法做, 用了AC提出的binary search法, 很強大
H (+0)  似曾相識的 flow, 打武器 (ISAP), build graph 的 code 很長
F (+0)  suffix array, 要搵有幾多條唔同的 suffix 出現 > 1次, 對住 h[ ] 搞幾搞很神奇的出到答案
D (+4)  greedy by AC, 那 4 棍完全是我的錯 =[






Unsolved

C - 疑似 dp, 未諗到




Reflection


今次整體的流暢度不及上次, 不過題目相對較難, 有一些細節也需要更多時間去思考

體會到武器的重要性, suffix array 是因為真的很複雜, 而 flow 雖然徒手也揼得出, 但用武器的話真的可以節省不少時間和精神..!

D 本身並不難, 其它隊很快便過了, 詳細記下發生甚麼事吧

本身 greedy 方是 AC 諗到的, 我也覺得看下去正確, 便幫他寫 input 果 part, 不過第一次返回 WA
之後 de 左幾個 bug 仍然 WA, 我開始懷疑算法的正確性, 始終我無真係 prove 過個 greedy

一直搵唔到 counter example, 但段 code 睇極都無錯, 睇多幾次題目確定沒有理解錯誤
中段 AC 提出可能是 input format 的問題, 我認為這個可能性很低, 也不想糾纏係呢題, 就無咩點理到..

剩下 10 mins 時無野做改下食 input 的方法, 結果竟然 Accepted !


事後覺得我做了不少錯誤..

首先驗正隊友的算法是好的, 因為有些時侯可能想到一些隊友沒想到的 case
但,
AC後來提出是 input format 的問題時, 我 reject 左呢個可能, 某程度上自己的確有點驕傲, 恃著自己的經驗而沒有實行隊友的建議
結果當然是浪費更多時間對一個正確的算法搵錯, 完全影響之後的過程

即係, 改 input format 不用一分鐘, 但做左呢樣樣至少可以確定是不是算法的問題=[

對不起..


改進:
1) 學 suffix array O(N lg N) , 今次的 O(N lg N lg N) 差點就 TLE 了
2) 理解點樣 O(N) 起哂相鄰 suffix 的 longest common prefix 出黎
3) 放下自己, 相信隊友

最大平均值問題

Given a[N] 和 M, 找出長度不少於 M 而平均值最大的 continuous subsequence [1]
例如 a = [2, 5, 2, 5], M = 2 最大是 (5+2+5)/3

Algorithm 1

二分答案 d,  問題轉化為
設 b[i] = a[i]-d , 是否存在一段長度至少為 M 的子串而 sum ≥ 0
設 S[i] 為 b[] 的 partial sum array, 再計算 Suffix[i] = max{S[j], j ≥ i}
只要檢查最大的 Suffix[i+M] - S[i] 是否 ≥ 0
之後睇了 [2],  見到一個 linear 的算法

Algorithm 2

如果定義 s[i] = a[1] + a[2] + ... + a[i], 問題轉為搵 max {(s[y]-s[x]) / (y-x), y - x ≥ M}
將 (i, s[i]) 視為 2D plane 上的點, 等價於求 maximum slope

對於每個 y , 要考慮 p[0, y-M] 的點, 更進一步, 其實只要考慮 p[0, y-m] 形成的 lower hull 就足夠
所以要 maintain 著 lower hull (用一個 stack, 反角形成時便 pop)

直覺是類似 tangent 的連到 lower hull 上, 找 tangent point 可以用 binary search
也可以利用 lower hull 的 slope 是 monotonic increasing 這個性質
如果在 lower hull 上 p[y] 是對於 p[x] 的切點, 對於 x' > x, y' < y, 這個組合不會好過 (x, y)

所以只要記住當前的切點, 每次只向右移, 一共是 O(N)

References:
[1] POJ 2018 Best Cow Fences
[2] 周源 <浅谈数形结合思想>

Team Training 2/6/2010 - CERC 2004

Rank	Name	A	B	C	D	E	F	G	H	I	Total	Time
1	gagguy	-	+ 1:26	+ 0:46	+1 3:42	+2 1:09	+ 2:26	+ 1:44	+ 3:37	+ 0:25	8	975
2	chin	-	+ 1:23	+1 1:58	+3 3:15	+ 2:11	+ 4:26	+ 0:48	+1 2:48	+ 0:30	8	1139
3	dannyyip	-	+ 4:01	+ 2:26	-	+ 1:17	-	+1 2:58	+3 4:16	+2 0:45	6	1063
4	Prof.QQ	-	-2	+ 2:18	+1 3:08	+ 0:30	-	-4	-5	+ 0:10	4	386
5	Leo	-	-	-	-	-	-	-	-	-	0	0
	Submissions	0	5	5	8	6	2	8	12	6
	Accepted	0	3	4	3	4	2	3	3	4
	Solvability	0%	60%	80%	37%	66%	100%	37%	25%	66%

今天在CU打的training.. 老實說, 看結果是幾滿意的 (不要自滿 .\/.)
據說在 onsite 還有前三.. 算是一個 suprise 吧

學習一下 kn 的紀錄方法



Summary
Team members: GagGuy, AlanC
Solved: 8/9
Penalty: 975



Process
25 - I (+0)  本身在寫C的2-SAT, AC 說很頹便先做
46 - C (+0)  發現原來不是2-SAT, 只是普通DFS, 浪費了不少時間..
69 - E (+2)  AC 做的, array 開小了
86 - B (+0)  AC 看的, 本身無咩頭緒, 佢話係二分+貪心, 加左自己的猜想, 其實個算法沒有prove到的, 有點水過的感覺
104 - G (+0)  shortest path by AC
146 - F (+0)  DP, 其實不簡單的, 只是之前做過USACO很相似的版本, 當時還是看solution才做到
217 - H (+0)  bipartile matching by AC, build graph 看上去很煩
222 - D (+1)  convex hull, 一開始睇錯題目以為好難, 後來AC更正返+講埋solution, 我只係做coder XD 一開始用 monotone chain 把共線的點都 push 入 stack 又忘了開大 stack 而錯了一棍





Unsolved

A - 難+煩的geom, 有少少想法, 最後還是沒 code 出來.. (雖然有一小時剩, 剩30mins時回家了)




Reflection

其實今次個 system 不斷出現技術上的問題, 好多題都無緣無故一開始俾左個錯的 feedback (AC->WA, WA->AC), round down 又其實係 round up, EOF 寫做 0 0, 如果無呢d 真係可以再快好多
不過我覺得最大得著唔係 rank 或是和其它隊的比較, 而係對自己和隊友的進步
今次可以話打得幾順, 卡題情況甚少, 低級錯誤也可說是沒有, 過題時間基本上是很平均的
同埋我同AC的 coding 準繩度都不錯


另外, 合作性
我覺得今次真係合作得很好.. 基本上4hr 部機無空閒過的, 真係做到一題接一題..!
另外便是coding/debug上的合作, 可能因為大家平時打code既style都相近, 睇對方的code基本上不成問題, 而且還做到「一個打, 一個check」的 stragery
諗algo方面, 其實我覺得大家都進步左/成熟左, 可能是今次的題目簡單?
其實我覺得我和AC的默契真的不錯, 邊個上機/睇題目都好流暢, 大家都發揮好高既efficiency


改善方面, 今次無帶武器, 發現自己有些算法不是很熟 (matching/convex hull)
而且今次的題目也算是我們熟悉的 topic (沒有 Nim/geom/difficult maths 等) , 所以未來還是應該要去接觸更多的 topic

GCJ 2010 Round 1A

朝早九點開波..

A - "K"子棋, given current state, 問 rotate 90^o 後邊一邊會勝出 (可以both/neither)
但開頭 score 分佈出錯左, 以為有 trap, 所以無即刻揼.. 決定睇埋B,C先

B - given sequence {An} in [0,255], 可以 add/delete/change (各自有 cost) , 目標係試 neighbour 的 difference <= M, 求 min cost

C - 兩人玩的game, 一開始有兩個數 (A,B), 每一個 step 可以改為 (A , B-A*k) 或 (A-B*k , A) , k 是正整數, 問某個 range 入面有幾多 pair (A,B) 是 winning state



analyze下, B 明顯係 DP, 應該幾輕鬆 ; 但 C 疑似 Nim game 果類, 基本上係未 code 過
之後佢出 clarification 改返分數, 發現 A 佔分最少, 於是放心去寫A, 大約 30 mins 時 A-small  Correct!


今次打算用一個 strategy - 唔隊 large 住, 之後有時間再 double check 多次, 因為 large 得一次機會同埋GCJ 計時間係計最後 submission, 對penalty無咩影響 (如果之後會再 submit 的話)
寫 B - DP, change 同 delete 好易 handle, add 諗左一陣, 確定係 round up 除法, 過 test case, Correct!


之後就朝 C 進發
C - 睇多睇又唔似 nim, 於是用 memorization 的方法去打個表搵observation, 得到
 123456789
1*........
2.**......
3.***.....
4..****...
5...*****.
6...******


很明顯地有 pattern -- 之後就陷入一小時的掙扎
一開始以為係好簡單既 pattern, 但試左幾個 sequence 後後面又總係唔 work, 於是出動武器 - KMP 用電腦去搵 pattern, 但 turns out 佢係無一個 "repeat" 既 component ..!
唔忿氣, 出動埋 guassian , 話唔定係一條 polynomial , 入左頭 5 個數落去就知唔 work - solve 出黎的 coefficient 唔係 integer ... 睇黎條 sequence 唔係 polynomial ..


諗
諗
諗


剩返 20 mins 果陣, 突然發現

 123456789
1*........
2.**......
3.***.....
4..****...
5...*****.
6...******



每一行/列 * 的數目 等於 果行/列 的篇號!
諗深一層, 其實係同 self-describe sequence 差唔多  突然感覺到離答案只差一步

揼... 揼... 揼...

大約剩返 8 mins 時揼好, submit, Incorrect
灰左一灰, 但立即想到是 BIT 越界問題, 改, Correct!




Result ..

113

gagguy Me

100

2:30:38

32:50

1:36:12

50:27

1:39:01

2:26:02 1 wrong try

2:26:38

不過最滿足都係做到條 C







後記

睇返 official report, 原來 B 有 O(NM) 的做法, C 和 golden ratio 有關
GCJ 牽涉的範疇真的很廣泛, 學多d野才是上策

Code Forces Contest #11

這次的題目對我來說比較 thinkable 呢
一如以往, A 和 B 理論上都可以秒殺的, 不過 B 看漏了 input 可以 < 0 , WA 了一棍

C 是 given 一個 n*m 的01 matrix, 要數有幾多個由1圍成的 square , 一個 square 有兩種:

A)
01110
01010
01110
B)
00100
01010
10001
01010
00100

以且那些 square 不能在 edge or corner touch 到其它不屬於果個 square 邊界的 1, 例如
00001
01110
01110
01110
00000

n,m <= 250



D 是 given 一個 undirected graph, 數有幾多個 simple cycle (無self-cycle, 無 repeated edge/node)
|V| <= 19