SRM 477

250

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

500

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

超強烈既 Bipartite Matching 既感覺!!

ICPC 2929 Hang or not to hang

題意：

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

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

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

---

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

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

2010-07-27 Team Training - CEPC 2003

(CEPC 是當年的簡稱)

• 題目在這
• On Site Scoreboard
• 官網在這

又是被折磨的一次 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 記錄以下資料

1. x- 及 y- 座標
2. 時間點
3. 行走方向

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

Codeforces #24

題目在這

---

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

看自己的 scoreboard 和 submission...

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

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

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

---

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

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

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

[舊帖] PKU 2480 Longge's problem

原文位置：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 的某個因數

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

ICPC 4270 Discret Square Roots

本星期 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

PKU 3493 Chessboard Puzzle

本星期 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

2010-07-13 Individual Training

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

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

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

---

題A Adventure of Super Mario
shortest path

做兩遍 shortest path

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

---

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

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

[隨筆] 風格？

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

---

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

HDU 3208 Integer's Power

在 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)

Codeforces #23

依然不是解題報告

---

今次的題目很難呢...
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，在最後最多可以有多少人剩下來？

SRM 475 ∩ Individual Training

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

[隨筆] 修煉 I - Rotating Caliper

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

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

這陣子...

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

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

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

SPOJ 4532 String reduction

題意：

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

---

樣例：

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

---

算法：

O(N³)動態規劃

[舊帖] UVa 11275 3D Triangles

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, 貌似好多地方都用得著

PKU 2036 I Conduit!

題意：

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

---

解1：

排序→掃描 (Vector Arithmetic)

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