real

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

距離 Regional 的日子不多了...
加緊做一些幾何問題
以及整合武器庫...

http://poj.org/problem?id=2986
http://poj.org/problem?id=2074
還有更多...
(可能會參考)
http://yao428650.blog.163.com/blog/static/11223245420108163336321/

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

(在Training 記錄之中滲一篇隨筆...一篇早在 10月寫好的隨筆)

這兩個月... 腦海被 ACM 以及 Research 充斥...
好想把兩件事同時做好

（然後，又想說點很土的話）

有時閒著閒著的時候
會突然想起小時候的那件事
──嗯，小學時期，算起來都十二、三年了
至今仍瀝瀝在目...

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

250 大失敗...orz
~~(原先可以秒殺既幾何題目 turn out 做得極慢)~~
integer division / multiplication 的正負號使我頭暈了
應該一開始就用 floating point number comparison

kn

[這篇 Entry 怨言居多... 慎入]

前排 ACM ICPC Regional 忙了一排... 現在還是很忙...-_-
── 最近我才意識到... 我只剩下不到兩個半月時間完成下一份 Research Project
但有 online contest 的話，我還是會盡力抽空去打
(縱使狀態不好, 仍盡量堅持打... 要習慣在狀態不好時 code...)

近來的 Online contest 都很不順利...

先是星期六晚 (1am) 的 SRM 491...
這場賽事題目很有意思... 我意思是題目對我來說很難...
雖然很多人提交 600 跟 900，但 sample 比較弱...
最後不少人被 Cha 或 Fail System Test
System Test 時有 "Problem"，本來說約有 10% 的 submission judge 錯了
後來等了兩三小時還未完成...

至Test 終於完成時
才聞說 Challenge Phase 臨近最後幾分鐘 Server 有事故
以致某些人的 Challenge 有問題...
至今(都兩三天了) Admin 還未做更新 Rating 與否的決定
~~(看來 Un-rated 的機會較大...)~~

>The match will be rated.
GOOD!!

kn

足足十一年... 我們期盼了足足十一年...
CUHK 終於再一次獲得 ACM ICPC 區域賽的冠軍!!

我們最終解掉全部十條題目
以題數勝出賽事！

(Non-ACMer 可以直接跳到最後
(或者略過本篇 entry ，閱讀即時賽後感想)

We are the CHAMPION!!!!

Final Scoreboard: http://www.iium.edu.my/acmicpc/upload/html/

(以下事件順序可能有錯誤)

(當我們想拍下PC^2 Submission page 的時候...
(我們發現 PC^2 被別人關了... Server 也停了)

(注：內含題目及算法透露)

(略過一開始的賽情延誤)

等了好久，終於開始正式比賽

題目只有一份，由 Joe 分派
我一望題目 format... UVa Contest ?
然後閱讀了某題 (好像是F)，感覺不頹
一下子安心了 (這次不是 Rush 頹題比賽)

沒久，Joe 把我趕走
原來有一道超頹題

5 min: Problem B - Extremely TUI (1Y; Joe)

與此同時，我把 Problem I 題意告訴 CTLi：
Given 一棵 Directed Tree，求 Topological Sort 的方法數

kn

我地中大等左足足十一年
總於等到今日喇!!

We are the Champion!!!

ManiAC got the Champion at ACMICPC Regional Contest - Kuala Lumpur 2010!!!

比賽遇到唔少阻濟：

尋晚訓得唔好：
午夜出面班人又打波打到好夜
打完又大大聲傾計（嘈醒左我，我冇睇鐘，但估計係3點左右）

然後... 今日又無端多左個mock contest
judge 又遇到技術問題 (team id -> team name mapping)
最後足足遲左2.5小時先開始
我當時心諗：死啦，我咁早啪左罐咖啡提神咪"啦"曬野？
(咖啡有效時間有限, 過左精神力會下跌, 加上尋晚訓得唔好...)

kn

是日節目比較頹
opening ceremony + practise section 比較頹

早上7:30am的巴士... 大遲到
我們幾乎被遺棄了

在 opening ceremony, Joe 發現科大隊伍出現CDQ的踪跡
在 practise section, 我們才得知數項事實：

題目由美國那邊出 ~~+ judge~~ (judge time 很慢)
scoreboard比較虧 (沒有 team name, 希望明天會轉好)
列印文件由 escort 幫忙拿回來, 但是他們貌似不能分辨文件是由哪 team 列印...

下午是 non-compulsory 的 city tour
因為昨晚比較累... 大家還是選擇留宿休息

kn

（因為很遲才book 機票的關係）
今次乘搭的是特早 (8:45am) 航班...
是以我被迫 4:30am 起床
乘坐頭一班 E22A 巴士...

兩老很有心的送我一程
這份支持... 實在令我（在心裏）太感動了

在進入大學 (UIA) 時遇到一些麻煩...
三人的 passport 一度被扣押在正門的 security unit
原因是我們沒有列印 invitation letter...

kn

先放 scoreboard:
1. Frozen - http://competition.binus.ac.id/icpc/result/
2. Final - http://competition.binus.ac.id/icpc/result/final.html

先說賽果: school rank 第 3, team rank 第 3

十道題目
五個小時
三個人腦 + 三十隻手指
一部電腦....... + 一個按鍵很硬的鍵盤 (超劣勢... 我們的 coding speed 下降了30％)

我們佔據一排桌子!! (一般是兩 team share 一排桌子, 這是優勢!!)

房間內... 右前方是 NTU ! (我們的主要對手!!)
過左面玻璃窗可望見上交女隊 (Joe 說, 他在比賽時看了她們很多遍)

一如以往，一開始我負責 (因為按鍵硬, 很辛苦地) 打Code Template
我在 ~1 min 後開始看題

Joe 看 A, 我看 B. Joe 又發現題C 是 game, 就讓 CTLi 看. 沒多久，CTLi 上機 code C, 未過樣例/有bug, 列印 code. 跟Joe互相交流了 A,B 的題意, 發現都是一時間未能想出算法. 然後我跟Joe說題 I, 是一道簡單Greedy, 我想跟他說明我的想法 (其實我認為我的算法正確), 但Joe說他很有信心, 便交給他弄. 我繼續看題, 發現簡單的題D. (同時, 又發現 IsolatE 很快地過題C, 後來聽他們說才知道這是 Run 1.) Joe的題I 也有點不順利. 不過卡題未算太嚴重. Joe 跟 CTLi 交錯上機/用紙筆 Debug, 然後便一塊在兩分鐘內 AC 這兩題.

24 min - Problem C - Nim Game (1Y; CTLi)

25 min - Problem I - Greedy (1Y; Joe)

然後換我上題D. 是一道簡單的模擬題. 中間也卡了一陣子, 跟著在紙上寫的 pseudo-code, 算是順利地 AC.

34 min - Problem D - Simulation (1Y; Kn)

kn

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

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

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

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

25頁武器終於做好...

大家要加油呀...!!

kn

Final Stage...
我一定堅持下去...
Tune 好 parameter
Gen 好 result

電腦 warn 我 virtual memory too low
我人腦的 virtual memory 都 too low 了...

kn

近況... 一字記之曰：忙

比當年 year 3 做 FYP 時更忙...
(year 2 core courses x N 當然很忙, 但 year 3 sem 2 做 FYP 時更忙)

Research... 接下來只剩下十天...
怒 cap data＋怒 gen result
定格 cap HDR image 很累人...
一 cap... 就是5個小時...
空著肚子 cap data 很難熬...

Generate Result 亦很辛苦...
其中 Pre-processing 要用到 Photoshop...
可恨是... ＿＿的 Photoshop 未能 Batch process 所需的工序
而 Runtime 比較長... 而 Data 又很多
只好 parallel 三部機一起 process
(Macbook ＋ Desktop ＋ Remote 到 Offical Desktop)
以及動用乘車的時間...

(苦水吐完了)

...種種原因... 令我不太想出現在剛剛昨晚的 Training
但最後還是去了...

kn

今次係 300 + 450 + 1000
又係峰迴路轉既一場 SRM

300
自問速度還可以
而且code得幾靚仔
又有隨機作大 case 調試速度

450
一打開, 睇完題目 + 考慮呢題既分數
令我覺得, google 下會搵到答案
(睇完題意, 有 linearity of expectation + DP 感覺)
點知搵黎搵去, 都只係搵到 theoratical expected number of exchanges

又研究下 Case 3 = 144 / 13 究竟有咩玄機...
又戳下, 答案同 number of inversion 有乜關係

諗下... google 下... 又諗下... 又 google 下
突然間愈見愈多人交... /_\
時間漸漸消逝

kn

250 開始得好慢
再一次是，挺快想出算法
但 code 的時間花了很久...
Rush 250 的速度居然比以前了，為甚麼呢？

不管如何，這個奇怪的算法...
是 based on 一些 observation
但後想清楚，我只是碰巧想對了：
我當初想漏了一些條件
但因為有 odd/even 的限制，我的算法才正確

500... 全間 904 都沒有人能做出來
對我而言，只能想出暴力方法
不過顯然對於 W, H <= 50 而言，暴力太慢了...

waihon 則直覺認為暴搜能過，因為 RectangleAvoiding 條件苛刻

kn

郭智亮說 ﹕ 「一個人『叻』沒
有用 ﹐ 全隊人『叻』也沒有用 ﹐ 只要有心參賽
﹐ 就要付出自己的努力 ﹐ 那只在乎本人如何配
合團隊的運作。」

在談到致勝的技巧時 ﹐ 王浩然第一句話是 ﹕
「信任。」

http://appsrv.cse.cuhk.edu.hk/~acmprog/web1999/press2000/TaKungPao.html
10年前, 立志出賽...

還有另一段文字想 quote
那是多年前其中一篇entry...
從一本小說 quote 出來的...
暫時找不到 @@

kn

2010-10-07 Thurs
HKG Time - 2300 to 2500

有時間既話, contest 會盡量打

今次又係 Codeforces Format
貌似呢 set 題目比較淺
不過我只能夠好慢咁 submit 左四條
(呢一刻狀態比較差, 好支力)

↑ Submitted...

kn

今年的 Team Formation 總算塵埃落定

經過高層（他們）的一番商討以後
我們將會破天荒，派出5支隊出戰 Regional
感覺今年的隊伍平均實力都相當強
當中大多數都是很有心玩 ACM 的

我對大家都抱有很大期望
大家要加油呀！！

研究方面
還是在趕 11月中的 Conference Deadline

kn

"期待"已久的 Rating 大跌的時機終於來了...
~~極度低落中...~~

賽情：

比賽一開始
便緊張得錯誤開啟了 500... -_-
看完 250 是一道比較直接的整數除法 (好似係)
稍為冷靜以後, 總算把 250 慢慢的 (202.xx) 搞定...

然後開 500... 想了又想, 想出了算法: DP + bit pattern

中段開了 Division Summary 看...
很多人提交了 900... 有很多甚至時 800 以一的提交...

但自己把心一橫, 堅持做 500
比賽臨終時, 才發現 Transition 錯了...
不能只 consider 上一格 array element

再看看 Division Summary 及 Room Summary
悲劇了... 大量 900 的 Submission...
現在的 Challenge Phase, 絕大部份的 900 依然屹立不倒

kn

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

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

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

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

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

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

kn

這次很用心寫故事...
(按：大家在題目當中，能找到多少個 CTLi 呢？)
翻看題目好多遍...
確保沒有 unclear / ambiguous 的地方...
感謝大家的努力...

很多人被題C 的 range 陰到了...
大家都不約而同地選用 1e9 作為 INFINTY...
是很深刻的教訓... 吧

全卷6題...
大部份做到4題...
初時還擔心題目會否太深...
結果顯示我們想錯了...

題C 和題D 的難度...
確實跟其餘 4題明顯分隔開...

kn

剛剛進行了 NEERC 2004 Team Training!!

我挺驚訝，大家都能把那道 3D Geometry 輕鬆解決！
雖然那道題目不完全是 3D：
── 只需要把問題化為 X-Z 及 Y-Z 兩個 2D Geometry 的 Subproblem
分別做一些類似 Slope 的分析解決便行

今次表現挺差... 心情有些不爽...
看罷 On-site score board..... 唉...........~

要是我們仨繼續保持不穩定的準繩...
要是我們仨繼續敗給未盡全力的超超...
後果...

自從 CTLi 回歸後，都算打了相當多場 Team Training
在 Joe 的督促下，CTLi 在短短一兩個月內的做題數目
相當於他以往全部做題數目的總和

感覺上... 在算法思考整體上我們仨其實真的很可以
不過... Coding 方便大家仍需努力努力...

我不願重蹈上屆 World Finals 的覆徹...

順帶一提近況：
最近當然還在忙著研究...
加上ACM... 我一天到晚都在 Coding / (多數是乘車時)看 Paper / 推公式...

暫時這份 Project 在理論上還未夠穩健...
仍然要進行實驗 (i.e., 拍照片→Run Algorithm) + 研究...
目標是十一月初的 Deadline
所以... 寫 Paper 的時候
剛好正是 ACM 賽季... 感覺有些吃力...

希望盡快把 Project 搞好...
好讓自己能分更多時間到 ACM...

轉眼間，已經欠下三次 Team Training 的紀錄...
(還有 Blog 的 "Tab"... Links 已加... 不過還沒加入內容...)
不過我實在沒有時間寫... orz

kn

一進房... Room3...
4個紅色 target ?!!!

難得做起 500... 極極被炒 Cha 了...
原因：overflow........!! 極灰中..............

而250... 明明算法基本上是剎那間想出...
奈何推導 + Coding 過程都很慢....
卡 sample (但這比起 Fail System Test 要好)
還好最後以 191.98 通過

是次 rating 微升19
(天... 升得好慢... 有預感很快會 "rating一舖清"...)

按：
Well, 原來 500 還有另一個地方錯了...
所以, 而家個心舒服番少少 @@
Sample 太不厚道...

code 250 時... 以為 sample 很厚道...
但原來有暗伏... parity...
不少使用 O(1) 算法的人都因此錯了...
而寫 for-loop version 的自己, 就沒有碰到這個問題

kn

題目在此

這是前幾天在 Timus OJ 的題目分類，按下 Geometry
隨機選擇的一題... (我喜歡隨機選題...)

讀完題目，感覺是經典題目... 但沒有想法...
細心一看... 原來這題還有另一個 Tag ── Hardest Problem
再一看 Accept Rate... 3%

後來跟 Joe 討論過一下，他一兩天就 AC 了...
但他說未能用 STL 的 set implement，只能徒手寫 Heap

(在 Joe 詳細地講解完算法以後)
於是便試試用 STL implement... 結果成功了 !!
不過代價是筋疲力竭
算法雖然直觀，但在處理 ordering 的過程 (見下) 是無限的 confusion + frustration...
而且，最後還要調 epsilon 才通過... (角度 radian, 1e-10)

Problem Statement：

給一個簡單 (Simple) N邊形 (N <= 500000)
在其內部放一個點光源 (Strictly inside)
問，光源照到的面積為何？

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-23 2am 更新：

兩種圓/圓公切線 (Common Tangent)，正名為
a) 「外公切線」(Common External Tangent)，及
b) 「內公切線」(Common Internal Tangent)
下面討論一律略去「公」 ("Common") 一字
....嗯... 外公切線... 以下簡稱為「外切線」及「內切線」
兩圓切線共有 5種情況 ...
我正在驗證本 Entry 所提供的 Implementation 能否覆蓋全部情況
──別被嚇到... 本人直觀地認為本 Entry 所討論的 Implementation
已能覆蓋所有情況，只是仍有待證實

昨晚隨便在 Ural Timus OJ 上選了一道幾何 ── Ural 1340 Cucaracha
想出了某 case 的算法後
發現自己不懂怎樣計算某一角度
只懂得 BSearch... 然後又發現 BSearch 不行...

再細心一想
才發現這個問題其實可以 reduce 至「點到圓切線」...

那我就想起... 原來我還沒有一份「點到圓切線」的 Code Template...

在這次之前不知道推導過這公式多少次...
雖然每次都能推出，但推導過程會花費相當長的時間
所以實在太有必要寫一份武器（要不，就把公式推導到爐火純青的熟練程度）

上回在這篇Entry 談過
「點到圓切線」是「圓到圓切線」的特例 ── 其中一圓半徑=0

而「圓到圓切線」在一般情況下共有 4條

CircleCircleTangentGeneral

分 「外切線」(External Tangent) 及 「內切線」(Internal Tangent) 兩種

~~──註：上行此兩項述語這是本文的定義，自行定義的原因一是為方便以下的說明~~
~~二是因為在 Google 暫時搜不出相關的述語...~~

而每種切線各有 2條

那 code template... 就是寫！

寫呀寫的...
突然有一個驚喜的新發現（潮左勿 WoW）：

「內切線」原來是「外切線」的特例！

kn

2010-08-16 Mon
HKG Time - 2300 to 2500

題目在這
Standings（大scoreboard）
Room 10 Scoreboard（My room）

Codeforces format：

留意標題後的括號 - Codeforces format

比賽模式跟 SRM 很相似：

難道不同的題目分數不同：
(A,B,C,D,E) = (500, 1000, 1500, 2000, 2500)
Submit 時間愈早分數愈高
比賽完結時才進行 System Test

不過亦有不同的地方：

kn

同房又見 rng_58 ...

250 是一道模擬+貪心
實踐算法花了相當長的時間（主要是卡在 index）
（眾參賽者的 submission 亦相當慢）

500 的數據範圍很大，就我而言是毫無頭緒
到中後期... 見這麼多人 (約 150 ／ 600) submit 500
看來這次要下跌了...

1000 就更不用說了... 懶得開
（最後沒有人解掉此題）

Challenge Phase 期間
發現一個複雜度 O(44777777 × 50 × 2) 的 solution
猶疑了一兩分鐘，把 code 關掉再開...
始終自己分數太低... 還是 不敢 Cha

後來這段 code 被Cha 至 TLE 了...

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

不錯!! 雖然 ratiing 只是微昇
但, 終於到達 90 percentile 了!!
(rating 亦創下新高)

只是... 過程有點悲劇...

250

看到 problem statement 的第一個字 ── Rabbit
出題者是誰... 心裏大概有個譜... 知道要小心應對...
讀完整題以後... 果然沒有平日SRM般... 算法即時浮現的感覺...

由那兩條詭異的算式...
只能估計是數學題...

在沒有 idea 的情況下
挑了 init = 1 的情況
暴力 simulate 頭幾個 step 的所有 configuration...
發現... e?!
這, 花了 5 分鐘左右

然後... 考慮 init 不等於 1 時讓怎麼處理...
這, 花了 5 分鐘左右

然後... 在算法基本上成形的狀況下...
寫 code... run...
然而... 運行 sample 2 和 3
跟 correct output 比較... 死活相差 1...

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

(Still refinining... this blog entry. More images will be added to aid understanding... hopefully)

Introduction:

In the following discussion, Voronoi diagram and halfplane intersection refer to the 2D case, unless otherwise specified.

I hope I can list some nice properties of as well as some relationships between the following three structures in computational geometry:

Voronoi diagram

[You need to understand what is going on on the right image.The left and the middle will be discussed below.]
Delaunay triangulation
3D convex hull

kn

250

唔知做乜事... 好慢!!
209.55

500

大約係, 要你喺一個以數字為 node 既 graph
搵最多既 edge s.t. 啲 edge 冇公共交點

超強烈既 Bipartite Matching 既感覺!!

kn

題意：

給定一個 program（LOC ≤ 16）
有 ≤ 32 個 boolean variable（值 = 0 或 1）
instruction 有以下 10 種：

每個 instruction 執行時間花費 1 cycle（包括 STOP）

variable 的起始狀態是隨機的
問，程序最早結束時間可以是多少？
是否對任何起始狀態，都會「Loop死」？

枚舉全 2³² 種 variable 的起始狀態再逐一 simulate
顯然會超出時間／memory 限制...

細心一想... 所謂 randomness 其實只是 JZ 指令

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

題目在這

剛 Accept 了 C... 比賽只剩下 10 分鐘...
橫豎已不能改變結果，便提早寫 blog 記錄

看自己的 scoreboard 和 submission...

比賽時... 完全地進入了暴走狀態 ── 「亂隊」

──沒有寧靜的打code環境是主因之一.....................

呀... 最後的 10 分鐘被不少人過頭

今次的題目比較容易...
題A 和題B 不論如何，應該要 40 minute 內搞定
可是我卻用了 60 minute... 而且還 WA 了 9 次

題C ... 起手 code 需要一點勇氣...
猜想 M_i 形成的 cycle length 很短

rating 或升或跌多少不太重要...
又是表現很差的一場...

kn

原文位置：http://www.xanga.com/private/editorx.aspx?uid=721833838

這是2010年度 CSC3270 的功課...

題意：

給定 N
計算 ∑_1≤i≤Ngcd(i, N)

算法：

Ans := 0
Foreach divisor of N, D
　　Ans += D × Phi( N / D )
EndFor

證明：

留意到 GCD(i, N) 必然是 N 的某個因數

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

本星期 Individual Training 的題目
是 Hefei 2008 的題目

聲明：以下算法仍然有漏洞... 有待修補

題意：

給定 x, r, N
求出所有 y (1 ≤ y < N) 使得
y² = x (mod N)
其中已知
r² = x (mod N)

數據範圍：

2 ≤ N < 1,000,000,000
1 ≤ x, r < N

分析：

首先，你只有以下的公式：

y² = x (mod N) ──── (1)
r² = x (mod N) ──── (2)

(1) - (2) 得
(y-r)(y+r) = 0 (mod N)
⇒ (y-r)(y+r) = aN

kn

本星期 Individual Training 的題目

聲明：以下算法的正確性有可疑...

題意：

給定一個 M×N (M, N ≤ 16) 的整數表格
每對相鄰而顏色不同的 entry，得到 score := 兩個數值的 product

現在為每一個 entry 填上黑／白色
使得 total score 最大化

分析：

依我來看，跟 Dual Core CPU 如出一轍
同樣是 binary labeling 問題：
建圖，找 minimum cut，把 node 分為兩類，使得：

S reachable 的 node 屬於 Type 0
其它的 node 屬於 Type 1

只是這題更 general，要處理 -ve cost
所以... 不能直接應用 minimum cut

kn

今天 PKU 終於復活（就香港、廣州等地而言）

晚上的 training
those 因為有事未能參與，所以由他來選題
然而其中一題未能讀入，便隨意選一道他做過的 geometry 題目取替之
（後來被這題玩殘了...）

training 暫時草草速記如下，細節後補：

題A Adventure of Super Mario
shortest path

做兩遍 shortest path

用 floyd 求出 all-pair-shotest path，避過中間節點是 castle 的情況
將每個 node（地點）分為 K 層，表示使用過 K 次 super-running

題B PKU 3429 metry with a Ruler
高精度 + 2D geom

被玩殘了...又要高精度又要分數 ⇒ 只好用 Java

kn

本來以下的文字出現在上一篇 entry 末端
後來愈寫愈長... 要自成一篇了

是在考慮關於本 blog 的風格問題：

kn

在 HDU OJ 看 problem title 隨便挑的一題...
據 AC rate 判定這題值得一做

題意：

對於正整數 x = b^e，其中 b、e 為正整數
定義 x (≥ 2) 的 integer power 為 e 的最大可能值
（81 的 integer power 是 4，不是 2）

給定正整數 2 ≤ A ≤ B ≤ 10¹⁸
求 [A, B] 區間內所有正整數的 integer power 的總和

分析：

稍為簡化問題：
令 f(Y) := [1, Y] 區間所有正整數的 integer power 總和
則答案 = f(B) - f(A - 1)

kn

依然不是解題報告

今次的題目很難呢...
rating 下跌了
但無悔參與了... 因為感覺很有得著

這場比賽題目挺奧妙的... 對算法要求比較高...
Codeforces 的性質就是
總有一兩道非常簡單的題目
題A 激簡單
題B 是簡單題... 但是 trap了 1 hr...（然而 solution 極簡單...orz）
題C 的算法很精妙（現場只有40 人AC）
題D, E... 分別是 2D幾何及樹狀dp(?)... 較難

題A... 在 2 min 提交... 貌似這是第15個submission
不少人在 0~2 min KO... 此題直接略過

題B... 挺奧妙的 graph 題目

題意：
有 N (≤ 10⁵) 個人參加了聚會
在 time=0 時，沒朋友的人離開
在 time=1 時，在剩下的人當中，有1個朋友的人離開
在 time=2 時，在剩下的人當中，有2個朋友的人離開
..
如此類推
問，給定 N，在最後最多可以有多少人剩下來？

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...

kn

這幾天正在忙 research
亦有一邊做題目

不過要下決心不做水題了... orz

這陣子...

Chin 經已把 Farey Sequence 弄明白
CTLi 則在攻 Game 及插頭DP 的題目
Joe 也剛剛應用 Sweep Line Algorithm 把 Chengdu 2008 的題D 幹掉

我呢...?
也許是時候開始研究旋轉卡殼(Rotating Caliper) 及凸多邊形(Convex Polygon) 了

感覺這個 topic 的資訊量挺大的 (見下) ...

kn

題意：

給定一條 ‘a’ 及 ‘b’ 的 string
長度為 N (≤ 300)
現在可重覆以下操作：
把長度為 3 的 substring “xyx” 轉換成 “y”（其中 x, y = ‘a’, ‘b’）
問 string 最多可以縮至多短

樣例：

“abaaaaaba” → “bab” → “a”
答案 = 1

算法：

O(N³)動態規劃

kn

Old Post in Xanga on 2010-02-18

Problem Statement:
Given 2 triangles in R³, check whether they share at least 1 common point.

今日 Research 有 3D 野要搞...
Google... 無意間見到一個 theorem - SAT (?)
原來 SAT = Separating Axis Theorem

發覺 ACM 可能有用喎!

應用落呢題之後... Runtime 快過以前 Ray / Plane Intersection !
而且對比之下, 呢個方法更加 mechanical, 貌似好多地方都用得著

kn

題意：

在白紙上要畫 N (≤ 10000) 條線段 (Straight line segment)，問總共最少要畫多少筆

解1：

排序→掃描 (Vector Arithmetic)

出現在同一筆的線段，必然有同樣的斜率（或角度）
對於相同斜率但不共線的線段
它們與原點（或任意 Fixed 的一點）有不同的距離

kn

今天仍然選了比較難的題

6題之中，在4小時內只把3題做出來... 感覺有點差...-_-
Parsing (題A) 及 Greedy (題F) 卡了太久... 沒有時間做剩下的題
還好最後仍然把那道 2D Geometry (PKU 2036!) 做出來...

今次的題目涵蓋了 2D Geometry、Parsing／String Processing、Simulation、DP、Integration，算是相當全面，而且比較煩。在考驗編程技巧同時，亦要求謹慎小心。值得一提的是，自己在 PKU 2065(題F) 學了一樣很多人早已知道的事實（見下）。

這一 set題目是比較難+煩... 所以表現不理想大家也不要灰心！

Problem A: PKU 2372 D++ Again
問：（講起我就扯火...）自己看！這題目就是考驗閱題！
（縱使 AC 過後我依然覺得題目寫得不夠清楚...-_-）
注：最後栽在這 Test Case...
　　"(*(**)" - YES

kn

題意：

在平面上，給定 N (≤ 10) 個圓（任何兩圓不相交／觸碰）
及 A、B 兩點

求最短 A 到 B 路徑（不得進入任何圓形內，但可以觸碰）的長度

應用知識：

此題基本上是一道 2D Geometry Exercise
只是在公式推導及處理 Boundary Cases 時要比較小心...

圓到圓切線（全４種）
點到圓切線
判斷線段／圓交點
最短路算法

2. 的計算可透過 1. 完成
── 把點看為半徑 = 0 的圓

kn

250

Bounded ⇔ 走四個循環返回起點

500

圓周上平分佈的N點中，任取三點成一直角三角形
⇔ 其中兩點連起來是直徑

所以問題轉化為統計直徑數目，M
答案 := M × (N - 2)

直接應用公式 + while-loop mark visited 選點
在最壞情況會很慢 (？)
建議實現一種類似 Linked List 的 Disjoint Set

FOR(i,0,n) parent[i] = i;
FOR(i,0,m) {
LL j = (a*i*i + b*i + c) % n;
j = find(j); // Find parent
vis[j] = 1;
parent[j] = find((j+1)%n);
}

kn

上一次 Round 1 跟 rng_58 同房
今次 Round 2 跟 ACRush 同房

比較慢地把 250 做出來

而那 500 的算法... Ad-hoc 到不得了
在完結前 2 min 才通過樣例並提交
結果被 cha

瓜了...

諷刺的是 rating 微升...
是因為本來的 rating 就很低的關係吧...

250

判定 Connecteness
Connected ⇒ Graph 是 Euler Cycle ⇒ 邊權值總和
(這裏我對於 Odd/Even degree 想了一陣子...)
Disconnected ⇒ Return -1

500

有好幾種算法... bsearch, monotonicity, by case 處理...

說一下 bsearch 的...

Generate 所有由單數 digit 組成的數字 - A[N] (N = O(5⁸))
對於 i := 0 to N-1
(二分)查找最少的 A[j]
使得 A[i] + A[j] >= X
記錄最小的 A[i] + A[j]

⇒ O(N lg N)

──自己居然連如此標準 + 簡單的算法都想不出...
實在要好好反省一下... ... ... ...

kn

題意：

給定 H x W 帶號整數二維陣列 (H, W ≤ 20)
現在要在其中走一個圈，周界 ≤ K (≤ 20)
（路線是 grid 的 edge，每走一條周界 += 1）
圈不可以 self-touch
計算被包圍的元素值的總和

求最大總和

不合法 shape 的樣例：

需要連接

◎　◎

不可以角碰角

◎◎
◎　◎
◎◎◎
剛剛才想到：角碰角 ⇒ 有洞
所以不需要另寫程序作處理

不可以有洞 1 (周界 = 16)

◎◎◎
◎　◎
◎◎◎

不可以有洞 2 (周界 = 20)

◎◎◎
◎　◎
◎　◎
◎◎◎

昨晚（強迫）Leo 及 Chin 跟我討論這條比較少人AC 的題目

然後今天下午... 和 Joe 分別起手 code...
慶幸是挑戰成功了（雖然非常懷疑自己是水過）

嗯... 看見 range 及 10秒時限便想到 Searching 吧...

不過起初我還妄想能否用狀態 DP 解決
然後被一大堆不知怎麼處理的狀況解決了... orz
（當然，我不排除 DP 的可行性...）

所以只好 code 搜索

kn

上星期二發現大家的 Number Theory 比較弱...
即使一些當中 Take 過 Number Theory 課的
似乎亦未能將知識比較皮毛的部份運用自如...

上星期四 Chin 講一下 Phi Function，Primitive Root 及 Discrete Logarithm 的一些應用及題目
再加上做過幾道題目以後：

貌似終於對這類課題（尤其是 Phi Function）比較有感覺

所以... 在今天的個人Training 特意挑了 (比較多) Number Theory 的題目，大家一起做
不過... 呃... 感覺大家做的時候比較絕望，所以更加要練習！

Problem A: PKU 3766 Hexagon Coin Toss
問：給定一些類似下圖所示，由邊長為 1 的正六邊形組成的 "M x N" 棋盤。現有一單位圓（直徑 < 1）隨機出現，其圓心必定在棋盤內，求該圓覆蓋 1, 2, 3 格的概率

解：畫圖直接分析... 可以參考 Roba 的 blog

Problem B: PKU 1061 青蛙的约会
問：求最小的 x 使得 vx = d (mod n)
解：擴展歐基里德算法（Extended Euclidean Algorithm）

Problem C: PKU 3358 Period of an Infinite Binary Expansion
問：求當 a/b 表示為2進制時，最短循環節的長度，及循環開始的位置
解：Phi Function。推導出來的式子跟 PKU 3696 The Luckiest number 那時幾乎一樣，可以參考舊文... (有時間再寫一下推導過程...)
按1：所有情況下，即使是 1/8，循環節依然 ≥ 1！
按2：呃... 這道題在 ICPC Live Archive 上面也有，不過數據很水。今次 Training 沒選 PKU 的，然後不少人以 O(答案) 的算法水過，失去了某些意義... ~_~

Problem D: UVa 10692 Huge Mod
問：給個例子說明吧...
　　 2^3^4^5 mod 10 = ?

在 mod 左邊的數字值 ≤ 10000，最多 10 個
解：呃... 還未做，不過大概是統計形如 {aⁱ mod N} 的循環節長度。（鴿巢原理 ⇒ 循環節長度 ≤ 10000 ⇒ 可枚舉）實現涉及 Recursion，感覺比較噁心...

Problem E: PKU 1997 Word Puzzle
問：題目有點長... 自己看吧
解：以 Trie 記錄 pattern。對表格每個位置，分別朝上下左右 etc八個方位掃描，檢查能否找到任何 pattern。
Joe 說能用 AC自動機加快，但本人對這東西不了解

kn

Problem Statement:
給定陣列 A[N], 其中 1 ≤ A[i] ≤ 2¹⁵-1
求最長嚴格下降序列 (Strictly Longest Decreasing Subsequence) 的長度及方法數

當序列元素完全相同，則兩個方法視為一樣（見樣例）

Sample Input:

12
68 69 54 64 68 64 70 67 78 62 98 87
1   1  2  2  2  3  1  3  1  4  1  2 // Explaination
69       68 64          62
69       68       67    62

Sample Output:

4 2

題目最難之處就是要避免重計
其中一個有效方法就是以元素的值作為狀態

為此，自己的第一個 AC Submission 就加入了三項預處理...
寫的很累贅...

後來 Google 了一下
發現自己沒有用到一項已經發現的 Observation：

kn

看完男人八題的題C：Tony's Tour 以後
[I like the title: "做男人不容易系列:是男人就过8题--LouTiancheng题"]

即時想起：
ICPC World Fianls 2010 - Problem I : Robots on Ice

$\epsfbox{p4793.eps}$

連結：
1) 《基于连通性状态压缩的动态规划问题》 By Cdq（陈丹琦）

插頭 DP
括號表示法（好似係）
Hamiltonian Path

似乎就係 exactly 老細想我地學既野...?

2) 【动态规划】Ural1519 Formula 1 - By ccy1991911
這是Google 返回的 Blog 文...
感覺寫的挺用心（未詳閱）

3) 【专辑】插头DP
NotOnlySuccess 寫的

插個花：
雖然自己都幾鐘意之前呢個黑底白字既 theme
而且感覺亦幾 Professional =v=
不過望落去時對眼真係有啲辛苦... 所以都係轉番白底黑字好啲

呀... 另外一個原因係 LaTeX 冇黑底白字（好似係）

呃... 暫時黎講個 blog 都仲係寫得冇乜系統
究竟寫 Technical Term 用中定英好呢？
白話文定書面語好呢？

kn

題意：
給定 L
求集合 { 8, 88, 888, ... ,888888, ... } 當中能整除 L 的最小的一個數字
列印該數的長度

算法 ── 思路：
設該數為 88....8，則有方程：
　　8 × 11....1 ≡ 0 (mod L) -----------(1)

設 g := (8, L)，得：
　　8/g × 11....1 ≡ 0 (mod L/g) -----------(2)

Case 0: L/g = 1
...

Case 1: L/g 整除 2 或/和整除 5
11....1 顯然不能整除 2 或/和整除 5 ⇒ 無解

Case 2: 其他情況
由於 (8/g, L/g) = 1，(2) 可以化簡為：
　　11....1 ≡ 0 (mod L/g) -----------(3)

以下為最關鍵的一步！

kn

Solved 10 out of 11
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戳得死佢

kn

Ural 1280 Topological Sort
對拓撲順序的理解

Ural 1282 Game Tree
不錯的 Mini-Max 入門題目
（自己是第一次做這種題目）

Ural 1296 Hyperjump
基本DP

PKU 3316 Snakes on a Plane
模擬；個人認為挺多陰險的 Case

PKU 2418 Hardwood Species
字典樹
注：數據不符合描術，字符不限於字母及空格！
測試證實字符的ASCII code 小於 128

kn

60.	Hussar	21	2465	A1 A2* B1 B2 C1* C2 D1**** F1* F2* I1*** I2 J1 J2 K1 L1

Hussar 在完全不知道比賽規則
及遲了 30+ 分鐘開始的情況
得到第60名... 算是不錯吧

值得一提的是，在最後2分鐘找到 Bug：

我把一句的 feq (floating point ==) 打錯為 flt (floating point <) 改正後用了1分鐘提交 I1

然後用了1分鐘下載 I2 的 input
最後在完結前18秒提交 I2

通過!!

這個 bug 足足花了接近一小時去發現...

有時間再打一下我懂的題目...

kn

當天剛剛從日本飛回香港
有點累
開機的時間大約是10:20pm

這次比賽... 炒粉了

身體及精神狀態都很差
不過表現未免太差了吧...

感覺 A 和 B 應該是 DP（我還沒有看題解或其它人的解）
D 沒有看
C 是能力範圍以外的題目 -_-

kn

// 算法 1) - O(number of bits)
int countBit_1(int x) {
int ret = 0;
while (x) ret += x&1, x >>= 1;
return ret;
}

// 算法 2) - O(number of 1's)
int countBit_2(int x) {
int ret = 0;
while (x) ret++, x -= x&-x;
return ret;
}

// 算法 3) - O(number of 1's)
int countBit_3(int x) {
int ret = 0;
while (x) ret++, x &= x-1;
return ret;
}

不過，根據統計及分析，最簡單的算法1) 效率最高。

kn

289

real

76

2:35:58

8:53

11:00

1:57:36
2 wrong tries

2:27:58

1:48:04

--

有了昨天 Round 1B 的體驗
看完題目以後預期競爭勢必非常激烈
（雖然沒有昨天的嚴重）

比賽中途名次一度滑落至 800+ ...
中途超級絕望

慶幸還是很險地通過了

值得一提的是，題 B 的算法，我是分開兩個寫的：
Small input - 暴力 Exhaustion
Large input - 在最後 5 分鐘才想出算法，在最後 2分鐘 Submit...

在結果公佈的一刻... 終於放鬆下來...

再一次印證，能否堅持到最後一分鐘，結果可以非常不同
亦再次發現自己修練不足

題 A 是 Sub-Round 1A, 1B, 1C 之中最簡單，先傻了一會兒打 2DPoint 的 struct（汗），過了幾分鐘才發現不需，十多行 code 解決
看完題B, C後決定先攻題B
對於題 B，作了 Greedy+Search 的思維進路，但實踐後 "small set" 未能通過；然而相信自己的直觀：算法跟 "geometric ratio" 有關係；然後一直想了大約一個小時... ...
此時發現自己的排名滑落至 800+，難道今年的 GCJ 就此結束？
看見朋友們開始提交 C 的 "small set"；於是先寫 C 的 "small set"，寫代碼時卡了一會兒，憑藉題目提供的 Illustration debug，提交並通過
深信 C 的 "large set" 不是自己能力範圍以內（不熟悉 data structure - Binary Indexed Tree... 汗），繼續向 searching 方向攻題B
──後來發覺，利用 "small set" 的程序稍作修改（一句 staement），"large set" 可以在 130 sec 跑完
決定完全地暴力猛攻題 B，才發現對於 "small set" 而言，運行時間充足
題B 的真正算法... 時間一分一秒地過去... 依然想不出
至最後 5min，突然悟出題B 的算法！（心跳加速，感覺腎上腺指數極速颮昇）
算法的方向大概是對了，大約是 log( log(L/P) /log(C) ) / log(2) ... ...不過有關 while loop 內應該用 < 還是 <= 很不清楚... 沒有時間冷靜下來想了... 心裏想著如果多給我 15min... 啊... 沒時間間了...！只好暴試！
在 cmd 狂打 I/O redirection 及 vimdiff... 調了一會... 終於通過了 small set... 在最後 2min 提交！

總觀今年 Round 1的題目
多數是不煩 code 的題
但考核的知識範圍挺廣

Binary Indexed Tree、DP + Counting、Nim、對數字的直觀感覺...

接下來的 Round 2... 將會是一場龍爭虎鬥
coding 一定要快（往年自己也是輸在間上...）
而且... 今次的比賽的場地，不是自己家或者是 Lab 或 Office
加上那時候疲累的狀態，結果起碼會打個七折吧

所以，我決定先來一場預演...

(待續)

kn

雖然很不情願去記下今場賽事的慘況
未能入圍！

1242

real

56

2:06:19

16:22

--
1 wrong try

--

1:35:29
1 wrong try

2:02:19

但，這年度的賽事還是應該記下來...

今場比賽－粗心 + 疲累

回顧整場比賽
0) 對，這場比賽的題目不太難
1) 如果 C 的 recurrence 沒有犯那個錯誤，多數能夠空出 >1 小時的時間去解決 B
（不過，以今場的狀態，大有可能在 Large case 栽在 overflow 手上...）
2) 如果 A 沒有犯那個低級錯誤，那這次比賽我就水過了...
（死了的原因，可能是 Submission Time 是 20:36 吧... 哈哈...）

1) + 2) 的「如果」都沒有發生... 可想而之今次的粗心或狀態都太差了...
就是題目都懂做，偏偏要犯的錯誤都犯了...

題A 做得比較笨
居然走去寫了樹
不過也不是寫了很久...
而且 small input 也通過了...

然後就趕快去下載 large input
在本機跑了一下... Runtime error ?
原來是 node 數目的上限想錯了...
debug了一下，消除了 RTE
看了頭 3 set data，貌似沒有問題
就 submit，趕快往下一題

── 但是，在 debug 時，我忘了在另一個相應的位置更改變數的值...
所以 large data set 就這樣掛了...

kn

題意：
二維場景內
給定一個半徑 = R，位置 = (0,0) 的圓
及 N 個多邊形障礙物
問，是否在存一個移動方向，使得當圓形以直線前進時
不會觸碰這些障礙物

分析：
算法大約都是枚舉（離散的）移動方向/角度 - angle[M]
然後逐一判斷是否可行

有關「觸碰」的限制
雖然可以 ± Epsilon 處理
但這會令代碼變得噁心

kn

今日係 Hussar (仲係成日唔記得點串) 第一次 training
(終於 sem 尾, 終於有時間 training!!)

turns out 結果唔錯 !!
喺俾題目「陰」
~~同埋冇武器 (其實今次唔洗用武器)~~
既情況下
做到 8 題
題數多過 on site champion (7 題)

約略講下 training
(我地冇詳細紀錄)

一開始 Joe (5 minute) 快速地解決 F

佢 code 起後
我將三條題目講俾佢地聽
我又聽左 chin 一兩條題目

感覺題目大部份都 do-able

(略吧.... 太支力了)

做到中途覺得題目既 range 好怪...
尤其係喺 Joe 提交 I 時返回 Runtime Error...
嗯... N <= 105... Radius <= 109... 當 array 開大好多時... 冇更奇怪既係... 當你唔 assume radius <= 109 時, 先至過到 sample... 然後 Chin 做果條 H 又係咁... Answer must be <>= 1015...
甚至 >= 1000000...

好怪...

去到中段... 做左兩三左右...
卡左好耐...

對住 set 咁既題目... 又唔可以信佢啲 range...
好氣餒...

跟住無奈之下... 幫手 debug I...
ee? 搵到一個 bug : 三點共線, 但係兩點喺 center 既兩邊

(待續)

kn

[舊題重做]

題意：
給定 N 點定義 (上例 N = 4) 一條 polygonal line sequence
以此圖形作基礎作 D 層的分形
由起點至開始遍歷 d ( 0 <= d <= 1) 的部份 (d = 0: 起點; d = 1: 終點)

求終點座標

算法：
直接分治：
Point2D f(double d, int depth)

f ( d, depth ) --> f( d, depth + 1) ...

kn

這篇寫了很多天...

本來還想仔細 "執一執" 才發佈
可 World Finals 正日事過已經超過10天... 所以還是先發佈吧~

（此 Entry 會不定期更新
（Last Update： 2:07am, 17/02/2010）
（Last Update： 5:05pm, 06/03/2010）

比賽現況：

起初：在 0~172分鐘 AC 4題, 位居第10：
62 - Problem G AC (ctli, DP)
80 - Problem D AC (whh, DFS+Greedy)
103 - Problem C RTE
110 - Problem C AC (Kn, Discretization+DFS)
170 - Problem J TLE
172 - Problem J AC (Kn, 狀態DP+Cut)

（特別一提的是： CT Li 在大約 100 分時開始做 F）

kn

VIM:
:gg -G Indent all lines of codes
:%s/from/to/g Replace All

Shell:
wc -l filename Count # lines of text files

kn

18/02/2010 - Separating Axis Theorem
24/02/2010 - Randomized 2D-LP - Expected O(N)
PKU 3130 How I Mathematician Wonder What You Are! (Existence of Kernel)
27/02/2010 - Dinic - O(NM^2) [+Opt]
PKU 3649 Dual Core CPU (Binary Labeling, Min-Cut)
13/03/2010 - Maximum Weight Closure by Min-Cut(N, M)
PKU 2987 Firing (Min-Cut)
21/03/2010 - Nim Game [Revisited]
PKU 3537 Crosses and Crosses
20/05/2010 - DP on Tree + Counting / Leftmost-Child-Right-Sibling / Knapsack
ICPC 4685 Succession
17/06/2010 - Discrete Logarithm - Baby Step and Giant Step Algorithm
PKU 2417 Discrete Logging
29/06/2010 - Half-Plane Intersection - O(N lg N) (ZZY)

kn

立志：見你地頭四題solve得咁順，我仲諗住你地會做到六題。如果第五同六題都順啲，如果whh諗到漏左check呢個case，如果ctli條f都搞掂埋，咁就有六題lu。

ctli：冇咁多「如果」。。。

話遺憾
我又唔係真係覺得極度遺憾

今日既表現
如果同過去training去比較
都差唔多係平時水準

講下戰況

一開始我開機set野 (VIM, INDENT of gedit...)
然後大家發散睇題
whh：A，D，G，J
kn：B，E，H
ctli：C，F，I

發現 G 有grid，疑似 Geom，就用 H 同 whh　swap

kn

ICPC 4455 Suffix-Replacement Grammars

[World Finals 2009 - Problem K]

題意：
現給定 N (<=100) 項規則，每項
形式為： X→Y（其中 X 和 Y 等長）
意義是：若字串的後綴為 X，則可花費用 1 ，將後綴替換成 Y。

求由字串 S 轉換至 T 最短路*。（其中 S 和 T 等長）

所有字串長度最多為 20。

[* 即最小費用，使用 "最短路" 此詞是因為描術更直觀]

樣例：
規則：
BC → CD
BC → CA
BCD → CCZ
A → C

S = BBA
T = CCZ

　 BBA
→ BBC (應用 "A → C")
→ BCD (應用 "BC → CD")
→ CCZ (應用 "BCD → CCZ")

Answer: 3

網頁

2010年12月31日星期五

2010年12月29日星期三

2010年12月21日星期二

2010年12月11日星期六

2010年12月9日星期四

2010年12月8日星期三

2010年12月2日星期四

2010年11月28日星期日

2010年11月10日星期三

2010年11月2日星期二

2010年10月27日星期三

2010年10月24日星期日

2010年10月23日星期六

2010年10月8日星期五

2010年9月30日星期四

2010年9月26日星期日

賽情：

2010年9月25日星期六

2010年9月18日星期六

2010年9月16日星期四

2010年9月9日星期四

2010年9月5日星期日

Problem Statement：

2010年9月3日星期五

2010年9月2日星期四

2010年8月21日星期六

2010年8月20日星期五

Codeforces format：

2010年8月15日星期日

2010年8月14日星期六

2010年8月7日星期六

250

2010年8月1日星期日

Introduction:

2010年7月29日星期四

250

500

2010年7月28日星期三

題意：

2010年7月26日星期一

2010年7月25日星期日

題意：

算法：

證明：

2010年7月21日星期三

2010年7月17日星期六

題意：

分析：

題意：

分析：

2010年7月14日星期三

2010年7月13日星期二

題意：

分析：

2010年7月10日星期六

2010年7月7日星期三

2010年7月4日星期日

2010年7月3日星期六

題意：

樣例：

算法：

2010年7月2日星期五

題意：

解1：

2010年6月30日星期三

2010年6月28日星期一

題意：

應用知識：

2010年6月27日星期日

250

500

250

500

2010年6月25日星期五

題意：

不合法 shape 的樣例：

2010年6月23日星期三

2010年6月19日星期六

2010年6月16日星期三