real

kn

(以下定義/定理或者未夠嚴僅... 數學人請見諒...)

記錄一下每年 "瞬耳即忘" 的數論知識...
雖然網上有很多 material
不過還是親手記下才更深刻
亦好讓日後能循著相似的思路重溫

先來的是在往年的 Training Record 就有提過...
而且(包括算法競賽)應用極廣的：

Theorem 1 (Euler's Totient Theorem)

若 (a, n) = 1
則 a^Φ(n) ≡ 1 (mod n)

Definition 1 (Multiplicative Order)

a 的 (multiplicative) order modulo n 是最小的 h
使得 a^h ≡ 1 (mod n)

以下為 (hopefully) 較直觀的解說：

a 的 order 就是 {x_i} 的最小循環節
其中 x₁ := 1 (mod m), x_k := x_k-1 × a (mod n)

Definition 2 (Primitive Root)

kn

2011-03-23 Wed
HKG Time - 1900 to 2400

啱啱尋晚係 research deadline 後
第二次正式齊腳 training

今次做 World Finals 2004
悲劇呀！

kn

2010-12-30 Thur
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!!

kn

2010-12-28 Wed
HKG Time - 1320 to 1815

OJ提交：

ACM ICPC Live Archive

賽情：

(我們開了 scoreboard simulation) 在封 board 前一分鐘 4 條，遙遙落後於中遊隊伍
Joe 在 239 min Accept B，士氣大增!! (?)
最後一小時通過 3題!! 以題數獲得第2 !!
(詳情參下)

kn

2010-11-16 Mon
HKG Time - 1915 to 2345

空歡喜一場...
以為 champion 了...
中山一隊才沒這般弱

kn

2010-11-15 Mon
HKG Time - 1915 to 2415

HDU OJ

Deadline 過後... 終於可以好好 Training 了...

選錯題目了...
HDU 根本沒有 Tianjin 2010 的題目 -_-

狀態很一般...

首次用紙筆算不定積分： sqrt(1+x²) ...
代入：x = sinh(t)

kn

2010-10-20 Wed
HKG Time - 1915 to 2415

聞說是比較困難的一 set 題目
但做的時候，感覺只算是中上難度

嗯... 其實有很大程度是因為
那些(數學)難題全部被 CTLi 輕鬆秒殺...

所以，Training 至 2.5 小時左右
我們已經做到了 Champion 的成績
(跟 Champion 一樣解掉 8題，Penalty 比較好)

值得高興的是，我跟 Joe 合力把題B 解掉

kn

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.

kn

2010-10-04 Mon
HKG Time - 1930 to 2430

據說是一份比較難的題目 (但難度又未至歐洲賽區)
這份題目特別在的地方...
是 Number of test case 小 (<=20), 但 N,M 的規模很大(e.g., <=10^5)
當時在做的感覺是... 很暴力

今次我們 Team solve 了 7題
犯的低級錯誤比較少
算不錯吧

kn

2010-10-20 Wed
HKG Time - 1900 to 2400

是日比較沒建樹，只做了一題- -
稍為在算法方面作了零星的 suggestion

最後一題：Minimax Triangulation 居然 AC 不了...

kn

2010-08-31 Tue
HKG Time - 1900 to 2400

Official Standing

NEERC (Northeastern Europe) 勘稱全球最難的 Regional Site

(不過這是 2003年 的 NEERC，以經是 7年前...)

我們 team (Joe + CTLi + Kn) 以 7年後 的技術
解掉 11 題之中的 10題
題數與當年 onsite Champion 打和
(*若果考慮 Live Archive 對題C 不負責任的 I/O，詳情見下)
而罰時則勉強以 1x 的稍勝

是次 Training 在準繩方面相當差...接連犯了相當多個低級錯誤：

kn

2010-11-28 Sun
HKG Time - 0930 to 1330

晨早特訓
昨晚只睡了三小時今天早起就當是調整生理時鐘吧

是次 Training CTLi 狀態大勇
使我們在沒有 scoreboard 的情況下
三小時多便 AC 6題 Champ (?) 了

最後還在 247 min 做好第 8 題...

25頁武器終於做好...

大家要加油呀...!!

kn

2010-09-25Sat
HKG Time - 1330 to 1830

因為星期三中秋, 冇咁一次 training
所以星期六 (我地呢team) 約番黎打 Code!!

題目
題解
Frozen Scoreboard (我地 4 hr 時開左呢個黎睇, 雖然都冇乜理到)

Joe 話, 呢個 site 堅難
有幾難? 事前佢只係透露
出線所須題數, 同 champion 既題數相差一倍

最後, 我地喺犯下無數低級錯誤既情況下
做出出線既題數 (4題) 之中, penalty最低既一隊

照咁講, 即係出到線...
...但係... 今日表現真係太過...差

kn

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)

kn

(一些細節後補...)
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 時不會卡這麼久...

kn

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> 記錄 probability
── 每次 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 幾何

kn

(整理中)

這次的 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 件衣服

kn

(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 記錄以下資料

x- 及 y- 座標
時間點
~~行走方向~~

然後進行兩次「排序＋掃描」：

kn

(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 能力的問題，而是不夠冷靜的問題...

kn

本篇 entry 不是解題報告...

今天是 coding training
碰巧是 (非常棒的) SRM time slot
於是把 SRM 當作這次 training

大家一起在 lab SRM... 挺有氣氛的

在 SRM 開始前... tc 的 server 還是有點問題...
還好，最後大家都能順利登入

當分房完畢，按下 "Enter" 後...
發現同房有一個 target 紅色... 然後過了半秒才反應過來...

「又係 rng_58 ?!」

坐在我身旁的 those 很冷靜：「e? 入得喇？」
過了半秒，他亦驚呼：

「rng_58 ?!」

在比賽開始前 1分鐘
rng_58 突然說： "unsual point values..."

噢... 三條題目... 分數分別是 300、600、900...

網頁

2011年7月26日星期二

2011年3月24日星期四

2010年12月31日星期五

2010年11月28日星期日

2010年9月25日星期六

2010年9月3日星期五

2010年9月2日星期四

2010年8月14日星期六

2010年8月7日星期六

2010年7月28日星期三

2010年7月21日星期三

2010年7月7日星期三

追蹤者