2011-03-23 Wed
HKG Time - 1900 to 2400
啱啱尋晚係 research deadline 後
第二次正式齊腳 training
今次做 World Finals 2004
悲劇呀！
2011年3月24日星期四
2010年12月31日星期五
2010-12-30 Team Training - Daejeon 2010
2010-12-30 Thur
HKG Time - 1910 to 2410
OJ提交：
這幾天身體有點不適，直接影響表現了
這份題目頹題及難題各參一半
頹的很頹，一眼看出算法
難的我覺得很難，但都給 CTLi 早段時期秒殺了
毫無疑問，我們再一次給 Judge 玩殘了...
(~按嚴重情度排列)
HKG Time - 1910 to 2410
OJ提交：
這份題目頹題及難題各參一半
頹的很頹，一眼看出算法
難的我覺得很難，但都給 CTLi 早段時期秒殺了
| Rank | Name | Solved | Time | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | RoyalRoader.(KAIST) | 10 | 733 | 1/4 | 1/16 | 1/27 | 1/49 | 1/36 | 2/118 | 1/74 | 1/85 | 1/165 | 1/139 |
| 2 | ManiAC | 8 | 843 | 1/4 | 1/39 | 3/91 | 3/60 | 1/24 | -/- | -/- | 3/280 | 1/150 | 1/75 |
| 3 | nekonekosoft.(National.Taiwan.U) | 7 | 656 | 1/11 | 1/109 | 1/59 | 2/31 | 1/48 | -/- | -/- | 1/158 | -/- | 1/220 |
| 4 | reverse_iterator.(Seoul.National.U) | 7 | 748 | 1/4 | 1/12 | 1/83 | 3/117 | 1/24 | 2/225 | -/- | -/- | 1/223 | -/- |
| 5 | BurgerKing.(KAIST) | 7 | 758 | 1/3 | 1/34 | 1/25 | 2/155 | 1/66 | -/- | -/- | 1/242 | 1/213 | -/- |
| 6 | const_iterator.(Seoul.National.U) | 6 | 501 | 1/10 | 1/14 | 2/53 | 2/109 | 1/63 | -/- | -/- | -/- | 1/212 | -/- |
| 7 | d3sxp.(Kyoto.U) | 6 | 522 | 1/6 | 1/24 | 1/57 | 2/78 | 1/110 | 1/227 | -/- | -/- | -/- | -/- |
| 8 | Say.Yes.(Seoul.National.U) | 6 | 605 | 1/4 | 1/38 | 2/56 | 4/155 | 1/32 | -/- | -/- | 1/240 | -/- | -/- |
| 9 | Noname1.c.(Korea.U.) | 6 | 611 | 1/4 | 1/28 | 1/47 | 4/140 | 1/77 | -/- | -/- | -/- | 3/215 | -/- |
| 10 | PENDING.(Seoul.National.U) | 6 | 709 | 1/3 | 4/68 | 1/26 | 1/166 | 2/152 | 4/154 | -/- | -/- | -/- | -/- |
毫無疑問，我們再一次給 Judge 玩殘了...
(~按嚴重情度排列)
- Problem F - Memory 嚴重不足
當我們自滿地把 memory usage 由 19x MB → 110 MB → 51 MB，還是 MLE!!
2010-12-28 Team Training - Tianjin 2010
2010-12-28 Wed
HKG Time - 1320 to 1815
OJ提交：
賽情：
HKG Time - 1320 to 1815
OJ提交：
賽情：
- (我們開了 scoreboard simulation) 在封 board 前一分鐘 4 條，遙遙落後於中遊隊伍
- Joe 在 239 min Accept B，士氣大增!! (?)
- 最後一小時通過 3題!! 以題數獲得 第2 !!
- (詳情參下)
2010-11-17 Team Training - Cheungdu 2010
2010-11-16 Mon
HKG Time - 1915 to 2345
空歡喜一場...
以為 champion 了...
中山一隊才沒這般弱
HKG Time - 1915 to 2345
空歡喜一場...
以為 champion 了...
中山一隊才沒這般弱
2010-11-15 Team Training - Tianjin 2010 - Online
2010-11-15 Mon
HKG Time - 1915 to 2415
Deadline 過後... 終於可以好好 Training 了...
選錯題目了...
HDU 根本沒有 Tianjin 2010 的題目 -_-
狀態很一般...
首次用紙筆算不定積分： sqrt(1+x2) ...
代入：x = sinh(t)
HKG Time - 1915 to 2415
Deadline 過後... 終於可以好好 Training 了...
選錯題目了...
HDU 根本沒有 Tianjin 2010 的題目 -_-
狀態很一般...
首次用紙筆算不定積分： sqrt(1+x2) ...
代入：x = sinh(t)
2010-10-20 Team Training - Jakarta 2009
2010-10-20 Wed
HKG Time - 1915 to 2415
聞說是比較困難的一 set 題目
但做的時候，感覺只算是中上難度
嗯... 其實有很大程度是因為
那些(數學)難題全部被 CTLi 輕鬆秒殺...
所以，Training 至 2.5 小時左右
我們已經做到了 Champion 的成績
(跟 Champion 一樣解掉 8題，Penalty 比較好)
值得高興的是，我 跟 Joe 合力把 題B 解掉
HKG Time - 1915 to 2415
聞說是比較困難的一 set 題目
但做的時候，感覺只算是中上難度
嗯... 其實有很大程度是因為
那些(數學)難題全部被 CTLi 輕鬆秒殺...
所以，Training 至 2.5 小時左右
我們已經做到了 Champion 的成績
(跟 Champion 一樣解掉 8題，Penalty 比較好)
值得高興的是，我 跟 Joe 合力把 題B 解掉
2010-10-14 Team Training - Phuket 2009
2010-10-14Wed
HKG Time - 1915 to 2415
Solve 8 out of 10
Penality < SJTU => We champ-ed
However, we did have a little prior knowledge about the problem set.
HKG Time - 1915 to 2415
Solve 8 out of 10
Penality < SJTU => We champ-ed
However, we did have a little prior knowledge about the problem set.
2010-10-04 Team Training - Danang 2007
2010-10-04 Mon
HKG Time - 1930 to 2430
據說是一份比較難的題目 (但難度又未至歐洲賽區)
這份題目特別在的地方...
是 Number of test case 小 (<=20), 但 N,M 的規模很大(e.g., <=10^5)
當時在做的感覺是... 很暴力
今次我們 Team solve 了 7題
犯的低級錯誤比較少
算不錯吧
HKG Time - 1930 to 2430
據說是一份比較難的題目 (但難度又未至歐洲賽區)
這份題目特別在的地方...
是 Number of test case 小 (<=20), 但 N,M 的規模很大(e.g., <=10^5)
當時在做的感覺是... 很暴力
今次我們 Team solve 了 7題
犯的低級錯誤比較少
算不錯吧
2010-10-06 Team Training - NWERC 2004
2010-10-20 Wed
HKG Time - 1900 to 2400
是日比較沒建樹，只做了一題- -
稍為在算法方面作了零星的 suggestion
最後一題：Minimax Triangulation 居然 AC 不了...
HKG Time - 1900 to 2400
是日比較沒建樹，只做了一題- -
稍為在算法方面作了零星的 suggestion
最後一題：Minimax Triangulation 居然 AC 不了...
2010-08-31 Team Training - NEERC 2003
2010-08-31 Tue
HKG Time - 1900 to 2400
NEERC (Northeastern Europe) 勘稱全球最難的 Regional Site
(不過這是 2003年 的 NEERC，以經是 7年前...)
我們 team (Joe + CTLi + Kn) 以 7年後 的技術
解掉 11 題之中的 10題
題數與當年 onsite Champion 打和
(*若果考慮 Live Archive 對 題C 不負責任的 I/O，詳情見下)
而罰時則勉強以 1x 的稍勝
是次 Training 在準繩方面相當差...接連犯了相當多個低級錯誤：
HKG Time - 1900 to 2400
NEERC (Northeastern Europe) 勘稱全球最難的 Regional Site
(不過這是 2003年 的 NEERC，以經是 7年前...)
我們 team (Joe + CTLi + Kn) 以 7年後 的技術
解掉 11 題之中的 10題
題數與當年 onsite Champion 打和
(*若果考慮 Live Archive 對 題C 不負責任的 I/O，詳情見下)
而罰時則勉強以 1x 的稍勝
是次 Training 在準繩方面相當差...接連犯了相當多個低級錯誤：
2010年11月28日星期日
2010-11-28 Team Training - Dhaka 2010 - 晨早特訓
2010-11-28 Sun
HKG Time - 0930 to 1330
晨早特訓
昨晚只睡了三小時今天早起就當是調整生理時鐘吧
是次 Training CTLi 狀態大勇
使我們在沒有 scoreboard 的情況下
三小時多便 AC 6題 Champ (?) 了
最後還在 247 min 做好第 8 題...
25頁武器終於做好...
大家要加油呀...!!
HKG Time - 0930 to 1330
晨早特訓
昨晚只睡了三小時今天早起就當是調整生理時鐘吧
是次 Training CTLi 狀態大勇
使我們在沒有 scoreboard 的情況下
三小時多便 AC 6題 Champ (?) 了
最後還在 247 min 做好第 8 題...
25頁武器終於做好...
大家要加油呀...!!
2010年9月25日星期六
2010-09-25 Team Training - Shanghai 2009
2010-09-25Sat
HKG Time - 1330 to 1830
因為星期三中秋, 冇咁一次 training
所以星期六 (我地呢team) 約番黎打 Code!!
Joe 話, 呢個 site 堅難
有幾難? 事前佢只係透露
出線所須題數, 同 champion 既題數相差一倍
最後, 我地喺犯下無數低級錯誤既情況下
做出出線既題數 (4題) 之中, penalty最低既一隊
照咁講, 即係出到線...
...但係... 今日表現真係太過...差
HKG Time - 1330 to 1830
因為星期三中秋, 冇咁一次 training
所以星期六 (我地呢team) 約番黎打 Code!!
Joe 話, 呢個 site 堅難
有幾難? 事前佢只係透露
出線所須題數, 同 champion 既題數相差一倍
最後, 我地喺犯下無數低級錯誤既情況下
做出出線既題數 (4題) 之中, penalty最低既一隊
照咁講, 即係出到線...
...但係... 今日表現真係太過...差
2010年9月3日星期五
2010-08-25 Team Training - Kanazawa 2002
2010-08-24 Tue
HKG Time - 1915 to 2415
是 CTLi 強勢歸來的第二場 Team Training
8條題目 全清！
其它隊伍亦做出與 on site champion 同樣題數(5+)的成績
雖然今次做的同樣是日本 Site
全套題目仍是「暴力、硬做」的風格
但由於這已經是 8 年前的題目
就現今技術而言，難度不高
算法都很直接
亦不需要花很長時間 plan code （ 題B 及 題C 除外）
這次嘛... 本人開始的 題A 卡了相當多時間
吃了一下 TLE 及 一下 WA ...
實在太太太太抱歉...
還好在其後的 題C 及 題H 能分別 1A
不然真的非常拖累整體罰時...
題A - ICPC 2565 Calling Extraterrestrial Intelligence Again
解(Kn)： Prime Sieve + 二分
1st attempt：線性掃描每個 Prime number，定之為 height
再二分查找 最大的 height ── 結果是 TLE
這個很不明白... 明明複雜度只是 O(M lg M) per query... (M = # Prime's)
HKG Time - 1915 to 2415
是 CTLi 強勢歸來的第二場 Team Training
8條題目 全清！
其它隊伍亦做出與 on site champion 同樣題數(5+)的成績
雖然今次做的同樣是日本 Site
全套題目仍是「暴力、硬做」的風格
但由於這已經是 8 年前的題目
就現今技術而言，難度不高
算法都很直接
亦不需要花很長時間 plan code （ 題B 及 題C 除外）
這次嘛... 本人開始的 題A 卡了相當多時間
吃了一下 TLE 及 一下 WA ...
實在太太太太抱歉...
還好在其後的 題C 及 題H 能分別 1A
不然真的非常拖累整體罰時...
題A - ICPC 2565 Calling Extraterrestrial Intelligence Again
解(Kn)： Prime Sieve + 二分
1st attempt：線性掃描每個 Prime number，定之為 height
再二分查找 最大的 height ── 結果是 TLE
這個很不明白... 明明複雜度只是 O(M lg M) per query... (M = # Prime's)
2010年9月2日星期四
2010-08-17 Team Training - Ehime 2004
(一些細節後補...)
2010-08-17 Tue
HKG Time - 1915 to 2415
CTLi is back!!
今天是首次 Full-team Training
Ehime 是日本賽區
日本的題目類別/特色 包括：{普通、麻煩} × {暴力、Simulation、幾何}
表現還不錯
9 題之中
AC 7題
剩下兩題包括：
題A - ICPC 3185 The Balance
解(CTLi)： 擴展歐基里得算法 (Extended Euclidean Algorithm)
CTLi 面帶慚愧地說，平日的他寫 EGCD 時不會卡這麼久...
2010-08-17 Tue
HKG Time - 1915 to 2415
CTLi is back!!
今天是首次 Full-team Training
Ehime 是日本賽區
日本的題目類別/特色 包括：{普通、麻煩} × {暴力、Simulation、幾何}
表現還不錯
9 題之中
AC 7題
剩下兩題包括：
- 題 I (3D Geometry)
原本 CTLi 想出了一個非常漂亮的算法！
但由於抵受不住 jet lag
他沒有精神處理一些 degeneracy
提早回家 @@ (若否，Training 期間理應一定能解掉此題) - 題 H (3D Geometry)
這題 Joe 之前已經 AC 過
所以把這題留到最後才開始 code (當時尚餘 1X 分鐘)
題A - ICPC 3185 The Balance
解(CTLi)： 擴展歐基里得算法 (Extended Euclidean Algorithm)
CTLi 面帶慚愧地說，平日的他寫 EGCD 時不會卡這麼久...
2010年8月14日星期六
2010-08-10 Team Training - NWERC 2002
2010-08-10 Tue
HKG Time - 1900 to 2400
這次的題目不算太難（8年前的舊題目...）
在訓練前預先知道這份題目當中有一道難題（題E）
略過此題，其它的幾乎全部做了出來
今天我們 team （= Joe + Kn + Bill） solve 了 6 題
另一 team （= Chin + Danny + Hao + Jian）也不錯，同樣 solve 了 6 題
而超超到後期不肯做題... - -
飲恨是 Joe 的 題G... 我沒能幫甚麼... 他只差一點點
Problem A: ICPC 2670 Euro Efficiency
解(Joe)：簡單 DP
令 DP[X] := 完成 $X 的交易，所需最少的硬幣個數（包括「給」和「找」）
注意：需要計算 DP[1..N]，其中 N > 100
沒有仔細想 N 最 tight 的上界... 當時隨便選了 40000 便算了
Problem B: ICPC 2671 Markov Trains
解(Kn)：超暴力 DFS!!
DFS 窮舉所有 strategy（即規劃路線）
分別計算各種情況（窮舉班次 miss / arrive 的可能性）下
最後以 map<string,int>
── 每次 DFS至目的地時，遞加：map[s] += prob;
想過 DP，但題目對 strategy 的定義...
例如 路線容許 重覆經過同一個 city、班次開出與否有 uncertainty
似乎不太可能發現 strategy 的無後效性
當時 Chin 的 team 把這題 AC 了...
然後還一度以題數超越了我們
所以我們也一定把此題做出來
正當我在擔心這算法能否在時限內水過之際...
居然 0.016 sec 極速 WA（然後也極速 AC） 了...
Problem C: ICPC 2672 Hansel and Grethel
解(Kn)：簡單 2D 幾何
HKG Time - 1900 to 2400
這次的題目不算太難（8年前的舊題目...）
在訓練前預先知道這份題目當中有一道難題（題E）
略過此題，其它的幾乎全部做了出來
今天我們 team （= Joe + Kn + Bill） solve 了 6 題
另一 team （= Chin + Danny + Hao + Jian）也不錯，同樣 solve 了 6 題
而超超到後期不肯做題... - -
飲恨是 Joe 的 題G... 我沒能幫甚麼... 他只差一點點
Problem A: ICPC 2670 Euro Efficiency
解(Joe)：簡單 DP
令 DP[X] := 完成 $X 的交易，所需最少的硬幣個數（包括「給」和「找」）
注意：需要計算 DP[1..N]，其中 N > 100
沒有仔細想 N 最 tight 的上界... 當時隨便選了 40000 便算了
Problem B: ICPC 2671 Markov Trains
解(Kn)：超暴力 DFS!!
DFS 窮舉所有 strategy（即規劃路線）
分別計算各種情況（窮舉班次 miss / arrive 的可能性）下
最後以 map<string,int>
── 每次 DFS至目的地時，遞加：map[s] += prob;
想過 DP，但題目對 strategy 的定義...
例如 路線容許 重覆經過同一個 city、班次開出與否有 uncertainty
似乎不太可能發現 strategy 的無後效性
當時 Chin 的 team 把這題 AC 了...
然後還一度以題數超越了我們
所以我們也一定把此題做出來
正當我在擔心這算法能否在時限內水過之際...
居然 0.016 sec 極速 WA（然後也極速 AC） 了...
Problem C: ICPC 2672 Hansel and Grethel
解(Kn)：簡單 2D 幾何
2010年8月7日星期六
2010-08-03 Team Training - SWERC 2005
(整理中)
這次的 SWERC 的題目
比起上兩次的 CEPC 輕鬆多了
今天我們 team （= Joe + Kn + Bill） solve 了 6 題
（Gagguy 獨力 solve 了 7 題!!）
飲恨是 Joe 的 題G... 只差一點點
題F 沒有想出算法... 這個有點過不去
題I 剛剛 AC了... 原來 problem statement 想暗示 test data 很弱
題J 也 AC 了... 算法不太難想，理論上應該也可以 AC 的...但前提是前幾題要做得足夠快
Problem A: ICPC 3502 The mysterious X network (Bill)
解：水題 ── BFS
Problem B: ICPC 3503 Bin Packing (Bill)
解：水題 ── 貪心
Problem C: ICPC 3504 On Storing Clothes (Kn)
解：簡單模擬
要小心的 Case 包括 一次過掛 N-1 件衣服
這次的 SWERC 的題目
比起上兩次的 CEPC 輕鬆多了
今天我們 team （= Joe + Kn + Bill） solve 了 6 題
（Gagguy 獨力 solve 了 7 題!!）
飲恨是 Joe 的 題G... 只差一點點
題F 沒有想出算法... 這個有點過不去
題I 剛剛 AC了... 原來 problem statement 想暗示 test data 很弱
題J 也 AC 了... 算法不太難想，理論上應該也可以 AC 的...但前提是前幾題要做得足夠快
Problem A: ICPC 3502 The mysterious X network (Bill)
解：水題 ── BFS
Problem B: ICPC 3503 Bin Packing (Bill)
解：水題 ── 貪心
Problem C: ICPC 3504 On Storing Clothes (Kn)
解：簡單模擬
要小心的 Case 包括 一次過掛 N-1 件衣服
2010年7月28日星期三
2010-07-27 Team Training - CEPC 2003
(CEPC 是當年的簡稱)
又是被折磨的一次 training
今天我們 team （= Joe + Kn + ytlau9） solve 了 3 題
呀... 還好啦
（Gagguy + Bill + Danny solve了 4題）
Joe 今顯得有點不冷靜... 是因為緊張晚上的 Google interview 吧？
然後他早走了
ytlau9 幫我在好些問題上指引正路
沒有他，我想大概不能 AC 第3題吧...
Problem A: ICPC 2922 Easy task?
解：data processing 水題... STL 減省 code length
Problem B: ICPC 2923 Bundling
沒有看...
Problem C: ICPC 2924 Shortcut
解：排序→掃描
為所有在 path 上的 grid point 記錄以下資料
又是被折磨的一次 training
今天我們 team （= Joe + Kn + ytlau9） solve 了 3 題
呀... 還好啦
（Gagguy + Bill + Danny solve了 4題）
Joe 今顯得有點不冷靜... 是因為緊張晚上的 Google interview 吧？
然後他早走了
ytlau9 幫我在好些問題上指引正路
沒有他，我想大概不能 AC 第3題吧...
Problem A: ICPC 2922 Easy task?
解：data processing 水題... STL 減省 code length
Problem B: ICPC 2923 Bundling
沒有看...
Problem C: ICPC 2924 Shortcut
解：排序→掃描
為所有在 path 上的 grid point 記錄以下資料
- x- 及 y- 座標
- 時間點
行走方向
2010年7月21日星期三
2010-07-20 Team Training - CEPC 2002
(CEPC 是當年的簡稱)
今天是久違的 team training
雖然人未齊
最後我們 team （= Joe + Kn） solve 了 4 題
超超 solve 了 5 題
（scoreboard後補）
總而言之，今天表現很差（未至極點，但差不多了...）
寫出來的 code，code length 差不多是正常版本的 2 倍
我做到的 2 道題目，分別是 standard 到不行的 BFS 和 Shortest Path...
卻總共錯了 5 棍...
雖然沒有從口裏說出來
但我確實拖累了 Joe
讓他沒有時間想／code／和我discuss 第 5 條題目...
愚以為不是 coding 能力的問題，而是不夠冷靜的問題...
今天是久違的 team training
雖然人未齊
最後我們 team （= Joe + Kn） solve 了 4 題
超超 solve 了 5 題
（scoreboard後補）
總而言之，今天表現很差（未至極點，但差不多了...）
寫出來的 code，code length 差不多是正常版本的 2 倍
我做到的 2 道題目，分別是 standard 到不行的 BFS 和 Shortest Path...
卻總共錯了 5 棍...
雖然沒有從口裏說出來
但我確實拖累了 Joe
讓他沒有時間想／code／和我discuss 第 5 條題目...
愚以為不是 coding 能力的問題，而是不夠冷靜的問題...
2010年6月9日星期三
South America 2009
Solved 10 out of 11
Penalty 輸俾 on site champion 幾十
今日表現唔錯！
題目較淺
80分鐘 KO 7題
Nope... 喺 UVa 見到啲 Statistic
人地單挑出嚟既成績都接近我地一team人做出黎既成績...
飲恨係kick喺條 F - Suffix Array...
感覺明明algo冇錯
double check 過... 武器冇打錯...
又整唔出test case戳得死佢
Penalty 輸俾 on site champion 幾十
題目較淺
80分鐘 KO 7題
Nope... 喺 UVa 見到啲 Statistic
人地單挑出嚟既成績都接近我地一team人做出黎既成績...
| # | 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 |
飲恨係kick喺條 F - Suffix Array...
感覺明明algo冇錯
double check 過... 武器冇打錯...
又整唔出test case戳得死佢
訂閱：
文章 (Atom)