Bit Counting

// 算法 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) 效率最高。

Google Codejam 2010 - Round 1C

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
加上那時候疲累的狀態，結果起碼會打個七折吧

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

(待續)

Google Codejam 2010 - Round 1B

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

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 就這樣掛了...

PKU 3703 Intuition of Escape

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

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

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

Amritapuri 2009

今日係 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 既兩邊

(待續)

ICPC 4612 Fractal

[舊題重做]

題意：
給定 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) ...