比賽 × 4

Topcoder SRM 624

題目非常 standard, 估計是為了測試 TopCoder 終於肯 support 大於 50 的 vector input

加上不久前開始 support special judge TopCoder 支援的題目類型終於可以跟其它 OJ 相提並論

Zepto Code Rush 2014

E 在 system test fail 了, 不過憑著 5 棍 hack 和 RP 仍然保住 T-shirt 一件

GCJ 2014 Round 3

終極 fail

IPSC 2014

Task H: 構造 integers input 使得 C++, Java 的 hash table (對應為 unordered_set 和 hashset) insert n 個 integer 的時間為 O(n²)

Contest 時沒有做, 不過若不是這題也未必會知道 C++/Java hash table 的 implementation
兩個 language 的 hash table 也是用 chaining, insert 時會 search 一次整個 bucket, 所以只要不斷 hash key collision 就可以退化為 O(n²)
然後跟據題解的不斷 dig into source code, 就可以發現:

- C++ 的 hash table size 必為 prime, 並 default 在 load factor = 1 時 double hash table size; 而 hash function 則為 modulo 現在的 hash table size
- Java 的 hash table size 為 2's power, load factor = 3/4 時兩倍化, hash function 則是用 shift bit

知道實際的數字就可以輕鬆殺掉 unordered_set 和 hashset! 所以以後 CodeForces 繼 anti Java Quicksort 後可能會出現 anti hashtable..


Task M: 求 s-t maxflow, 額外限制: 每條 s-t flow 長度不長於 L. Small: L ≤ 3, Large: L ≤ 6

Small 的話可以很容易 model 做 maxflow, 很 standard
Large 解題報告用了一個例子去說明很可能沒有 "一般" maxflow 的做法, 因為當 L > 3 存在 integral capacity graph 但答案不是 integer
但其實不難發現可以 model 為一個 O(L|E|) 個 variables 的 LP, 相當於 60000 個 variables.. 於是放棄之

Contest 過後看題解, 原來這個就是 intended solution! 不得不說 simplex 真是奇妙的東西

題解 booklet

World Finals 2013: Before the contest

到 Saint Petersburg 中途碰到了不少麻煩
首先是 miss 了 181 巴士, 要拖著行李走到 Farsta Center
然後買 airport bus ticket 時排隊, 前面有兩個人問了 10 分鐘以上
終於到了機場, 發現所謂的 25kg bag allowance 是連 onboard 行李一起計, 超重了 4kg, 要多付 320kr

總算到了 Saint Petersburg, 等行李等了半小時...
出閘, 匯合立志, 然後才發現原來和 Per Austrin 同機, 不過由於樣子和上年差太遠所以認不出, 比較 shock 的是 Per Austrin 竟然叫得出我個名

由於上年已經來過 Saint Petersburg, 所以很多地方都去過

CUHK @ ITMO

上次沒有去大樓的另一邊

和火車站隔壁的商場

也沒有去夏宮 Peterhof, 所以在 dress rehearsal 那天便去了
Peterhof 位於離市中心 50km 的地方, 不過小巴開得很快所以一小時便到達
總括來說, 就是一個有很多精美的噴泉的皇宮

於是, 比賽前的幾天便是在飲飲食食和遊覽中度過

WF 2009 K - Suffix-Replacement Grammars

有趣的題目, 雖然其實不難不過挺 inspiring
Link: http://livearchive.onlinejudge.org/external/44/4455.pdf

解法

猜想: 只需考慮把 S 的 suffix 替換成某一條 rule 中的 string 的 string
一開始覺得每次做 replacement 前, current string 必定為 starting string 的 prefix + 某條 rule 為 suffix
但是很想便找到反例, 因為使用 production rule 的次序不一定按 increasing length order
例如
Goal: ABC → DEF
Rule:
BC → GH
H → I
AGI → DEF

於是, 便想到要把 string S transform 成 string T, 主要有兩種方法:
1. S → I₁ → I₂ → .. → T  (same length)
2. 對於每一個 S 與 T 的 common prefix, transform 餘下的 suffix

方法1 只要 shortest path 便可輕鬆解決
方法2 把問題 reduce 成 length 更小的 case, 所以只要由 length=1 開始便可以遞推上去

由於 constrains 不大加上已經是早上七時, 所以隨便寫了 Floyd-Warshall 和很多地方都沒 optimize
Execute 了差不多 30s (time limit = 36s)

答案上限

由於以前聽聞過, 答案是會 exceeds 32-bit integer 的所以避免了 (可能的) overflow 錯棍
但是上限是多少呢 ?
一開始以為是 100²⁰, 當然不是 tight 的

假設對 length 為 k 的 transform 的 rule 有 r_k 條 ( Sum{r_i} ≤ 100 )
假設 X, Y 為 length k 的 string, 若 X 能 transform 成 Y, 最多要做 MAX_k 次

所以, 得 MAX_k = MAX_k-1 * r_k
而且 MAX₁ = r₁
所以答案上限 = Product{r_i}

但也不是一眼看出即是多少, 2⁵⁰? 3³³?
使用 dp 可得最大約為 7.4 * 10¹⁵ (3³² * 4)

ACM ICPC 2011 - Kuala Lumpur

比賽前要把背包放在一個房間, 中途看見只有 9 種氣球, 代表只有 9 題, 即是很有可能要以罰時決勝負, 對我們有點不利, 因為我們的罰時一向都不是太好

其實比賽在 9:15 便開始了, 比去年準時很多. 我負責分題目, 感覺上沒有甚麼頹題. 不久後 whh 上 A, submit 後得到 WA.. 此時己經有些燥, 在開始便已經落後人. 幸好第 2 棍便過掉

A - tui (whh, 19 + 1WA)

中途 ff 告訴我 E 的題意, 我一看便知道是一般圖匹配, 這時還覺得挺開心, 因為有武器而且我覺得不會很多隊伍能做到. 不過由於代碼很長, 決定先放在一邊, 和 whh 研究 I, 很快發現用多一支 vector 一定不會使答案變差, 所以 vector 的次序並不重要, 便猜想可以把 vector flip 至第1, 2 象限再處理, 不過不是很確定, 所以交給 ff 和 whh 處理, 我則處理 G - string 的題目, 很快便想到可以用 suffix array (其實用 kmp 便可以), 於是便啪啪啪打武器, 中途和 ff 交替讓他做 H. 寫好 G 後 submit, 返回 WA, 不久後 ff 的 H 也 WA 了, 很差的開局. 約 15 分鐘後發現一些 for loop initilize value 寫錯了, 此時 ff 的 H 也過了

H - dp (ff, 67 + 1WA)

G - suffix array (gg, 74 + 1WA + 1RTE)

此時完全沒有興奮的感覺, 因為很多大學己經拋離我們 (台大好像己經 5+ 題). 此時 ff 和 whh 又沒有其它題目可做, 於是便打 general graph matching 的武器, 其中一行代碼是 g[i][j] = g[i][j] = -1, (馬後炮) 使我有點懷疑武器的可信度.. 不過還是要打, 順利過 sample, submit 後得到 TLE, 便給 ff 做 F (shortest path?) 和給 whh 做 I, 我則把60多行的 code 印出來做人肉 diff..

之後便是差不多一小時的空白, 我的 E 完全找不到 bug, 他們的 F, I 也嚴重卡題的情況 (加起來 WA 了 5 次), 而我隨便 gen 了一個大 case 發現會在一些 do{}while() loop 中 loop 死, 但又找不到 bug, 使我十分焦燥. 大約過了一半的時侯 ff 終於過了 F, 總算有些進展...

F - shortest path (ff, 166 + 2WA)

終於 4 題, 但罰時是在同題數中最高的. 我們的分工是: whh 做 I, ff 做 C, 我則做 B - 在去年的 training 中見過類似的, 做法十分麻煩, 是 segment 內嵌 BIT, 如果之前沒做過的話我也懷疑我寫不出.. 此時腦袋己經十分疲累, 但幸好是第 2 次寫, 故寫得頗順利, 提交卻得到 RE, whh 的 I 也繼續 WA, 愈來愈令人焦急.. 幸好 ff 的 C 一棍過了, 十分慶幸不用 debug C 這種題呢

C - evaluate expression + randomize (ff, 227)

不久發現 lower_bound() 有些位 handle 錯了, 改之, 終於過了 B, 鬆一口氣

B - segment tree + BIT (gg, 234 + 1RTE + 1WA)

之後看之前看錯題目的 D, 認真想了一想後覺得不太難, 便接著做, 是比較像"OI" style 的題目, 當然由我解決掉~

D - adhoc (gg, 260)

這時侯我們仍然有希望可以全清的, 因為可能 E 只是一個小 bug, 加上 I 有很多隊做到, 在剩下的 40mins 我們應該也可以做到. 但愈試 E, 愈是開始覺得是武器出錯.. 他們的 I 好像也試了另一個 approach, 但最終也是過不了.

完場後十分灰, 也不想知道自己的 ranking, 在發現 E 竟然可以用 bipartite matching 水過後更加燥.. 隨手畫一個 case 都可以炒掉 bipartite matching, 怪不得這麼多隊伍過了..

其實以我們的實力 9 題是可能的, 雖然開局很差, 但其實還是有很多機會可以全清 (例如放棄 general graph matching 的武器嘗試水, I 也應該更早放棄 iteration 的 greedy 算法), 不過還是輸了, 感覺十分差

今次分題目不是分得很好, 不過有數題也是有 (x, y) 的坐標 input, 但其實全部都不是"真正"的 geom 來的; 不過對台大這種 "三名高手型" 來說可能沒有甚麼差別吧

今次完全浪費了 whh 的戰力, 大部份時間都在試 I 的錯誤做法 (greedy flip vector), 希望 fuzhou 的題目可以讓 whh 發揮吧

Sem3 10/13: Prolog

因為 AI 的關係所以接觸到 prolog
一開始覺得很莫明奇妙, 即使想拿到 list 最尾一格也要搞一大輪, 很躁
功課也完全沒有頭緒, 無從入手
不過得到 david 大大的指導, 逐漸明白其實就是在寫 CFG 的 rules (雖然也很煩)
功課有個 online judge system, 可以大約知道自己寫的對不對, 也是不錯的
總括來說對 prolog 的印象還是正面的

由於要準備武器的關係, prolog 的功課做到 8x 分便放棄了 (無左 course grade 2 分..)
即是說 project 又要努力一點了

其實人身在吉隆坡, 後天便比賽了, 雖說有 59 team 參加, 但仍然是十分緊張
不過每次 regional 過後便要還 assignment 債..

Team Training 10/10/2011, 12/10/2011

ChengDu 2007

D: simulation by whh
J: 簡單題 by whh
B: AP by gg
- 其實很早就寫完, 不過沒發現伏, 花了點時間把所有情況想清楚
H: 1999題 by faifai
A: partial sum by whh
C: dp on tree by gg
- 寫得很差, 想漏一些東西導至 code 得很複雜 -> debug 困難, 之後重做短了 40 多行
F: state dp by whh
- 好像是插頭 dp, 錯了很多次, 懷疑有比較簡單的做法
E: by gg + faifai
- 和 faifai 討論了一下, 發現原來看穿了就很簡單, 我負責 RMQ 的部份, TLE, 發現可以很簡單地用類似 histogram 的方法降至線性, WA 了幾次後發現是 LL 的問題, 最後 293 + 4 過了

I: 見此
G: 原來用 A* 就可以, check 的時侯只考慮有機會 intersect 的 rectangle

Kuala Lumpur 2010

很難得的接近full team打.. (3人出席時間加起來應該有13小時, 好像是開學以來最多的一次..)
就扮真比賽記錄吧

開始 whh 負責打template, 我分題目, 發現把很多題目都分了給ff. 不久 ff 發現簡單的 B, 瞬切. 我看的 I 很像 Jakarta 的 B, 很快便推到式, 在 ff 做完後便接著做, 過不到 sample, 先給 whh 做 H (因為忘了 output test case number 錯了一棍), 很快找到 bug, 改之, WA 後發現把 test case 數目看成 input size 了.. 改好便過了第 3 題, 暫居榜首 (好像是). 此時 ff 寫 D, 我手上有 F (grid, 可能是 BFS), G + J (geom), 同時 whh 問我 C 是不是很熟面口, 一看發現竟是我 211 project 的題目! 不過由於有太多題目在手加上 whh 好像沒有其它題目做, 便把算法告訴他由他來想細節, 等自己可以專心做我負責的題目. 不久後 D 輕鬆 WA, 由於 debug 不能, ff 便改做好像較簡單的 A, 不過寫到一半又發現 trivial 的 greedy 好像有反例, 和他討論了一下又找不到方法解決. G 是 standard 的二分, 於是便搶先寫, 途中他們發現很多隊過 A, 便覺得應該可以頹做, 結果是可以的. 我的 G 也緊接著 A 過了. 之後好像是 whh 和 ff 交替寫 C 和 D, 突然發現 live archive 的題目和 official site 的 D 是不一樣的! (好似係minor difference), 改後仍是 WA, 而 C 就 AC 了, 便讓 whh 幫 ff 的 D debug, 我做 F (standard steiner tree, 比較麻煩的是 vertex 有 weight). 不久後成功過 D, 我的 F 則 WA, 不過可以用 machine 有效率地 debug, 很快便發現 vertex weight handle 錯了, 改+過之. 此時剩下一半時間和 2 題, 如果不是預先知道題目難度的話應該會覺得很大機會全清的. 分工是我做 J, whh 做 E, ff 則 2 邊協助, 和 ff 討論了一下, 很快便找到不是過 2 點的 case, 便想到一個很複雜的line rotate 算法. 不過 whh 好像對 E 沒有甚麼想法, 便問了一下他的意見, 他覺得過 1 點的話 line 是 fix 的, 我覺得合理, 也會易寫很多很多, 於是便開始寫. 不過也是寫得很差, rotation 的部份不長但花了很多時間, 過 sample 後好像己經是 260 了 (寫+debug 了一個時間..), WA 後發現 1 點的 case handle 錯了, 改後竟然得到 TLE, 便努力 opt rotation 的部份, 繼續 TLE, 最終發現 rotation 的 index 有點問題, 改之, 此時剩下數分鐘, 雖然只是 training 沒有緊張的感覺, 但在 297 時 AC 也是很興奮的

Team Training 6/10/2011, 8/10/2011

Tehran 2010

A: 簡單 by whh
B: 麻煩題 by faifai
H: Graph by whh
- 我用了 SCC 做, 其實只搵 source SCC 可以寫得簡單點
G: by whh
E: 枚舉 by gg
- 發現 hint 是錯的..
C: game 題? by faifai
D: 煩膠 by gg
I: 頹sim by gg
- 水過的, gen 個全是 robot 的 map 輕鬆 TLE..

K: 可以用 DnC on tree + BIT 做, 不過很麻煩, 懷疑可以用動態樹

NWERC 2010

A: greedy by faifai
H: sim by whh
C: by faifai
E: count degree by gg
B: dp by faifai
F: lower bound flow by gg
- 本身無諗住咁早打.. 統粹唔想空置 machine
J: by gg
- 很簡單, 但大家也好像很遲才發現這題
G: by gg
- 用類似 stack 去做

Team Training 19/9/2011, 21/9/2011, 26/9/2011

South America 2008

F: 極頹 by whh (6)
C: 頹 by whh (17)
G: 頹 by gg (41)
A: shortest path by gg (69)
- 起點做一次, 終點做一次, 然後再起點做一次
K: ad hoc by gg (85 + 3WA)
- 只試 Sum 的 factor, 可以 check remainder, 我的做法是 simulate 走圈的 process
E: 日期題 by whh (91 + 3WA)
I: euler path by gg (162 + 2WA)
- 顏色為 vertex, 城市為 edge, check 能否成為 starting edge 首先要連著 odd degree vertex (如有), 和 remove 後會不會做成 edge disconnection
J: simulation by whh (199 + 2WA)
D: dp by gg (195 + 1TLE + 1WA)
- 一開始使用 O(N² * K) 的 dp, 之後再做使用 2 個 dp array 可以降到 O(N²)

B: 數學題, 好像是做 factorizing by whh

Hangzhou 2010

H: 簡單題 by whh (17)
B: 二分 + 類似 TSP 的 dp by gg (67)
J: KMP + dp (94)
C: 唔知係咩題 by whh (114 + 1)
F: CG + convex hull by gg (130)
D: 五子棋(201 + 1)
- 做法是找+數 winning position

G: AP + LCA, 雖然上年聽 joe 講過, 但寫的時侯還是遇到很多問題, 最後做法是 tree node = BCC + AP

Seoul 2009

A: 簡單題 by whh (17)
F: 最遠點對, 但沒有看到題目中要來自不同正方形的限制, 水過的 by gg (71)
B: by whh (109 + 2)
D: maximum subsequence average by gg (141 + 7WA)
- 做法有很多, 二分/迭代/凸包, 一開始寫二分 WA, 應該是精度問題, 最後過的版本是迭代 + 沒有用 floating point
E: Josephus by whh (217)
H: disjoint set + BIT by gg (241 + 2WA)
C: greedy by faifai, implement by gg (273 + 7WA)
- 一開始覺得是簡單的 greedy, 但又想不到, 看明 faifai RE 的 code 後再寫
I: probability by whh, 題目 1999 又長 (284)

J: 竟然看漏了一重要部份, 之後可以輕鬆 dfs 解決, 處理同位置的點用了一個巧妙的方法, 把距離都是 d 的點加上距離為 2d 的限制

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

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