CodeForces Contest #30

題目
Scoreboard

---

很久沒有打 CodeForces 了, 今次見佢係新 style 又夾時間就玩下
server 還是很慢, 但至少還在可接受的程度

所謂的 CodeForces style可以看這

---

題目:

A - Accounting
解 A*Xⁿ = B, 給出 A, B 為 -1000 到 1000 之間的整數, n 為 1 至 10 之間的整數, X 也要是整數

B - Codeforces World Finals
和日期有關的data processing

C - Shooting Gallery
普通的dp

D - Kings Problem?
看起來很有趣, 不過沒有精神去想

E - Tricky and Clever Password
沒看題目..

---

戰況:

今次的題目都比較直接, 不用想很久就有整個算法的 outline
但仔細做的時侯, 發現A有不少地方要小心處理, 所以完成時間比較慢, 而且還要錯了2棍 (有一棍 submit 錯 file )

由於 B 的題目太長因此跳過, 發現 C 是比較簡單, 少 trap 的 dp, 很輕鬆地完成了
看題 B , 其實也不太難處理, 只要小心一點就可以了, 大約一小時完成了三題

由於看到題 D 和 E 比較絕望, 以前的話一早去做其它事
但 CodeForces 的特點之一便是 coding 和 hacking (即 challenge) 是同時進行!

把 3 題都 check 一次便 Lock 起它們 (即不再 resubmit )
才可看別人的 code
看了幾個 A, 都有 overflow 的情況出現, 但找不到數據去炒佢
找到一段 A handle 錯了 X 為負的情況, 見佢幾短便打落自己部電腦試, 勇敢地按下 hack

Successful hacking attempt

+100, ranking 頓升了不少, 發現 hacking 是一個分數的重要來源 (比SRM 的+50分更有影響)
在臨完場時, 又發現有人沒有處理 B%A!=0 的情況, 又多100分

最後排52

---

感想:

比起 SRM, challenging 別人的 solution 的壓力似乎比較小
因為自己的 code 已經 pass 了 pre-test, 對自己的方法有一定信心
而且也不太需要擔心別人搶先 hack 掉, 因為一間房比較多人而且別人不一定在 hack

總括來說 hack 人頗划算的
不過今次要把別人的 code 打來試, 應該更有信心 hack 才是

Team Training 15/9/2010 - NEERC 2004

今次懂做又比較的有趣的是 G 和 H

G - Gunman

其實不是第一次看到這題目, 不過 training 才認真想
turns out 可以分做 x axis 和 y axis 做

y axis 較簡單, 因為 fix 了一點, 只是處理一些 slope
x axis 則較複雜, 但其實是經典問題, 如果存在 valid 的線的話一定可以 rotate 到直至碰到兩點, 所以可以O(N³)解決

做 geom 其實幾有趣的 (如果唔使處理精度)

H - Heapsort

有容易有 idea 但又唔知點 code 那種題..
目標是每次將 1 shift down 到 label 最大的 node
做法先把 heap 的 node label, 每次再把 heap[1] map 返做 pop number

Team Training 13/9/2010 - NEERC 2007 Northern Subregion

時間不足, 只記下有意思的題目吧

C - Crosses and Crosses

game題, 應該要用 sg function, 不過還是未學懂, 遲點要研究一下

D - Domestic Networks

由於以前做過所以由whh做, WA 了很多次也找不到 bug, 最後發現是一個很小但又很容易犯的錯
trace answer 的時侯, 如果 dp[i] 已經能砌到的話則不用再試, 因為可能會 cover 了原本的 path

E - Elevator

做法: 求出 mod a 為 0,1,2..,a-1 中每個能到達的最小數層. 做法類似找 shortest path

G - Given a string

其中一部份是判斷 string A 是否 string B 的 rotation, 用 KMP

H - History of football

部份搜索法, 未過到

SRM 481

在 lab 和大家一起打.. 感覺挺好的

250, 一開頭覺得一頭霧水, 好像很複雜
但後來唔知係咪因為上完2510, 突然想到用linear equations
以一個中等的時間完成 (206.11), 總算是一個好開始..

500, 計 expected value 沒有太信心..
猜測了一個方法, 對住 sample 試了試, 覺得 work 便開始 code

900 有一點想法但時間不足

在 contest 完的時侯, 開了自己的 500 來看看
突然發現有一個位沒有用 long long !
立即「頂」了一聲..

果然在 challenging phase 被 cha 掉了..
同時找找有沒有人和我一樣錯.. 竟然沒有=[
幸好 250 的分數不錯, rank 也不是太差

最後 rating 微升 43..
又浪費了一個升 rating 的機會

---

250

最後用的方法是列方程..
首先分成四種人:

A = 得到答案是 egg 而沒有說謊的人
B = 得到答案是 egg 而說謊的人
C = 得到答案是 chicken 而沒有說謊的人
D = 得到答案是 chicken 而說謊的人

如果真的答案是 egg, 可得

A + B + C + D = n
A         + D = eggcount
        C + D = liecount
   B      + D = liarcount

只要判斷有沒有 A,B,C,D 都在 [0,n] 中的整數解便可以了

判斷答案為 chicken 的方法一樣

Team Training 31/8/2010 - NEERC 2003

據說很難的一個 site..
不過也沒有想像中難
joe+kn+ctli solve剩一題!

題目: http://acmicpc-live-archive.uva.es/nuevoportal/region.php?r=nea&year=2003

---

A - Alternative Scale of Notation

Solution: Solve by yym

---

B - Bring Them There

Solution: Binary search (optional) + Flow

當時想不到, 不過joe一說分層圖便明白了
binary search 完成時間T, 再將每個 node split 開 T 層, 第 i-1 層的連去第 i 層
做 max flow 睇下做唔做到

也可以先設 T=1, 做唔到再一層層加上去
呢個方法較快, 但感覺上較難code

---

C - Code Formatting

Solution: 同 parsing 有關, solve by danny

---

D - Data Mining
E - Entropy

當時都沒想到的2題, 聽完solution也只是半明, 題型完全不是我的type..

---

F - Farmer Bill's Problem

Solution: 不斷把正方形合併

由於每次搵有無touch/overlap要 O(N²), 而最多合併 N-1 次
所以總時間為 O(N³)

---

G - Game

Solution: 不斷刪去可能性

分析為甚麼會 "I don't know the answer", 可以知道每說一次, 就知道一定不是 sum/product 唯一的 pair
然後不斷重覆此過程就是了

---

H - Hypertransmission

Solution: Sorting + Update

先把所有距離對 sort by distance, 然後逐條加上去, 再即時 update 那些值就可以了

---

I - Illumination

Solution: 未有人識做

---

J - Jurassic Remains

Solution: 試哂所有可能性

不過都要試得有技巧, 要做到純O(2ⁿ), 要用到bitwise operation

---

K - King's Quest

Solution: SCC

Given 一個 bipartite graph, 要 output 所有在其中一個 perfect matching 的 edge
|V| = 2000
|E| = 200000
題目已 given 一個 perfect matching


首先佢 given 一個 perfect matching 一定有意思, 因為就咁做一次都要 O(VE)
應該係用佢個 perfect matching 去搵其它 perfect matching 出黎

第一個諗到方法是試一條 edge 時, 看看能不能以最小的改動去維持 perfect matching
但這個方法最差是 O(E²)

之後想到用 augmenting cycle 的概念
for 每個 node, 搵哂所有由佢出發的 cycle, 途中所走的 edge 就是可選的 edge
但這個方法是O(VE), 也過不到

最後想到, 要搵所有 cycle 出黎可以用 SCC!
首先對個圖 (只走 augmenting path) 做 SCC
然後 check 所有由左連去右的 edge, 如果佢地係同一個 SCC, 咁 implies 佢地係一個 augmenting cycle 入面, 咁即係可以用
KO!

很優美的一條:D
估唔到SCC都可以同flow類扯上關係..