隨筆 2010-09-30

今年的 Team Formation 總算塵埃落定

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

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

---

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

SRM 483 - 0分 悲劇

 "期待"已久的 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 依然屹立不倒

2010-09-25 Team Training - Shanghai 2009

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

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

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

---

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

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

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

Team Formation Test

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

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

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

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

隨筆 2010-09-16

剛剛進行了 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

SRM 481

一進房... 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 的自己, 就沒有碰到這個問題

[Hard 2D Geometry] Ural 1464 Light

• 題目在此 

---

這是前幾天在 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)
問，光源照到的面積為何？

2010-08-25 Team Training - Kanazawa 2002

2010-08-24 Tue
HKG Time - 1915 to 2415

• 題目在這
• On Site Scoreboard (Just summary)

是 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-08-17 Team Training - Ehime 2004

(一些細節後補...)  
2010-08-17 Tue
HKG Time - 1915 to 2415

• 題目在這
• On Site Scoreboard (Just summary)

---

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 時不會卡這麼久...