Topcoder Open 2010 - Round 2

上一次 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)

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

PKU 3679 The Delivery of Control

題意：

給定 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 搜索

2010-06-22 Individual Training

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

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

• PKU 2417 Discrete Logging
• PKU 1284 Primitive Roots
• PKU 3696 The Luckiest number
  

貌似終於對這類課題（尤其是 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
問：給個例子說明吧...
　　
在 mod 左邊的數字值 ≤ 10000，最多 10 個
解：呃... 還未做，不過大概是統計形如 {aⁱ mod N} 的循環節長度。（鴿巢原理 ⇒ 循環節長度 ≤ 10000 ⇒ 可枚舉）實現涉及 Recursion，感覺比較噁心...

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

PKU 1952 BUY LOW, BUY LOWER

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：

[進階DP] 基於連通性狀態壓縮的動態規劃問題

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

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

---

連結：
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 用中定英好呢？
白話文定書面語好呢？