網頁

Thursday 30 September 2010

Team Training 29/9/2010 - SEERC 2005

其實打係度好大一個原因係想做返未做到/隊友做的題目.. 不過都積左一大堆了..

Team Training 27/9/2010 - SEERC 2004

Team Training 20/9/2010 - NEERC 2005 Northern Subregion

SRM 483

今次的SRM十分刺激, 過程峰廻路轉


Coding Phase


一入房, 沒見到甚麼勁人
分數的分佈是 250 500 900

看完250, 由於 maxDen 十分小, 因此立即想到窮舉 A,B
搞左一輪, 慢慢的解決掉 (203)

之後不知為甚麼想先開 900, 看完題目後感覺不難
但有想過 900 不會這麼簡單, 懷疑佢 valid 的 range 並不是 [x,INF) 的 form, 於是寫左個 program generate test case 試, 得出來的結果又好像 work
又見很多人 submit 了 900, 於是便開始 code, 過程十分順利, 幾乎沒有錯, 過sample便submit了 (636)

由於做到900 心情很好, 便滿有希望地開 500
看完題目第一件想到的是 greedy 唔 work !
呃..
之後朝著 dp 的方向諗, 又真係好似可以用 dp

Define dp[i][left][right] = 第i個有left influence傳去左面和right influence 傳去右面
由於 500+500/2+500/4+... <1000, 所以大約是 N*10002
看起來很合理, 剩下15-20分鐘, 便很興奮地揼.. 啪啪啪
很順利的把 sample 都通過了, 在完場前3mins submit

Challenging Phase


做500的時侯已經想到很多人會用greedy做500!
所以 intermission 時已經出定 greedy 的 exceptional case
一開
果然有不少一看便知道不正確的方法, 不過估唔到連greedy都有好多種.. 有對 influence greedy 的, 有對影響人數 greedy 的, 有雙重 greedy 的.. 真係諗得出都有

看到一個用"double greedy"的, 睇明佢段 code 再諗左個反例, 由於做左3題, 因此當時很勇敢的 cha 下去

Challenge success

+50! 還想如果3題全過再加上 challenge 的分數就是一場完美的 SRM 了
可是, 突然發現自己的500被cha掉了, 灰哂
不過仍然無阻繼續嘗試cha別人的 code
差不多夠鐘時看到一個肯定錯的, 但又不太明白他在幹甚麼, 於是gen左一個大數據去cha佢, 可惜失敗, -25
最後以剩加分25結束

System test


看divison summary, 很多人都提交了500級900, 其中900的submission比500還要多
而且自己也莫明奇妙的入了頭100(好似係)

system test 開始後不久, 就發覺唔係好妥.. 900果行放眼盡是 failed system test
再看看自己也是同一命運, 但很幸運地有+25 的優勢 (突然變得非常重要, 因為突然大剖份參賽者只pass了250), 居然還可擠進頭100
Rating 的升幅也是近數月來最大的, 而且創了新高

很莫明奇妙的一次SRM

Saturday 25 September 2010

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 才是

Wednesday 22 September 2010

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(N3)解決

做 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

部份搜索法, 未過到

Friday 10 September 2010

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 的方法一樣

Sunday 5 September 2010

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(N2), 而最多合併 N-1 次
所以總時間為 O(N3)


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(2n), 要用到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(E2)

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

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

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