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) 放下自己, 相信隊友