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 的一點）有不同的距離