睇番自己以前d post..真係好傷心, 原來個時係咁比心機...
Anyway..係打番好幾場codeforce既practice之後, 最近做番2場div2既比賽
真係十年人事幾番新, codeforce已經轉埋做dynamic scoring..題目又難左
#130 (Div 2)
Problem List: http://codeforces.com/contest/208回流第一場比賽, 奇差無比。
題目難度應該係 A < D < B~C <<< E
比賽中只過到A同D...
C idea係岩..implementation大錯特錯..嗚呀
B 係事後其它人多番hints下發現係一個dp..果然dp就係有趣 =]
A:
頹題, 但我都糾結左一陣...最後用好笨既substr() 解決..
賽後偷睇GG / kn code, 再諗過一個更易implement既做法:
將 "wub" 變哂做space, 跟住用strtok() 輕鬆解決之...
D:
普通除數題...唯一傻左既地方係, 唔使sort多次..題目講明input已sort好..C:
Graph 題...回想當時大大聲話自己負責做graph真係笑話..如今連呢題都code唔出...
題意如下:
Given point s,t in simple graph, 係所有s 去 t 既shortest path 入面, 簡一個node M s.t. 佢cover得最多edge E where E belongs to some shortest path. Output max avg. number of covered edge of all shortest path
node數 n <=100.
題意其實好1999, 直接睇sample 先明, 好明顯係要計兩樣野:
total # of s-t shortest path + find node with max s-t shortest path pass through
算法如下:
1. d <- s-t shortest path length
2. cnt <- # of s-t shotest path length = d
3. cover_no <- # of shortest path pass through * (1 if the node is 1 or n, else 2)
4. output [cover_no / cnt]
一步步解剖
1. 由於graph 係unweigthed, 所以用bfs即可, 雖然我直copy網上dijkstra..(連dijkstra都唔識code了..)
2. 用dp 即可數到 : dp[s] = # of dp[i] if d[i] + 1 == d[s] && w[i][s]
3. 令我錯既一步..亦都係最難既...
首先要observe到某node cover到既edge 一係1, 一係2,
視乎係咪shortest path既中間
再黎係rephrase 題目: 其實姐係搵最多shortest path 由0 去到node i, 同埋由n 去到node i
---> 可以用番step 3 既dp!
4. output!
B:
題意如下:given 最多52張card (represent by 數字+英文字), 最右邊個疊卡可以放係右二或者右四
既卡上面, 條件係兩疊卡既面卡數字或英文字一樣, 問可唔可以最終令所有卡疊起成為一疊
唔知點解一開頭睇直頭覺得係頹做 依家連SENSE條題目係難定易既能力都無..
賽後知道係dp, 盡力諗dp既做法, 最少都要三維, 四維亦合理
不久後諗到個三維既dp state, 但最後fail左...因為只係store左一張卡既information...
kn 一句「store一張唔夠ga」看穿世事, 四維, 用三維store最右面三張牌, 剩番一維做index i
Perfect!
map 卡做一個數字既方法好古老, 都係 card = (數字 * 4 + [0,3])
咁card / 4 就係數字, card%4 就係花
跟住其實做dp 同 bfs都可以了..
#130 (Div 2)
Problem List: http://codeforces.com/contest/214
一場我reg左但真係太sleepy無打既比賽..而且好似都幾難..
第二日半睡狀態夾硬solve左A同B...
B真係血的教訓...CORE IDEA好快諗到, 但太太太太唔小心....唉
A:
solve equation, 頹做, O( n )B:
血的教訓!題意為輕鬆趣味數學題 : given n<=100,000 個digit, 最大possible砌到既數字 M s.t M | {2,3,5}
有d數字可以唔用
well...開頭的確Ｒ哂頭, 無idea...只係知道M | {2,3,5} 等價於 M | 30
but n = 100,000 , 可想而知都只可能係O(n) 或者O(n lgn)
n 既部分99%都係每一個digit 掃一次, 有greedy味
所以就開始回憶有無類似既經驗.....
係有既!!! CUCS ACM contest !!
個次題目係盡量pair up 兩個數字, such that 除得盡3 !又係3 ! 3 真係MAGIC NUMBER黎
(30 同 3 係一樣, 只要夾硬先放一個0係最後..)
Idea突然就有鳥, 先諗下greedy既method..姐係話極有可能其實大既digit 一定排先過細既
落手寫兩寫, 不難發現
如果一個 n 位數 c1c2....cn | 3 , 咁 sum of (c_i) | 3
正確黎講係: M = sum of digits of M (mod 3)
咁姐係話我somehow掉亂 c_i 次序, 係唔影響結果的, 當然大既digit 有幾前放幾前!
好啦 呢個就係CORE IDEA, 血的教訓開始啦...有d digit係可以唔用的...
first sight好似都唔難解決..先由大至細排好digit, 取餘數 r , 然後搵一個最細既digit such that
餘數等於 r , del左佢就係啦!
伏1: 該數可以唔exist
伏2: 可以del 2個digit 先達到效果 <---幸好唔會多過3個, 易證
伏3: del完, 剩番既digit 可以全0
伏4: 其實全0 都係有答案的 (就係 0 !!) sosad!!!
總歸以上各點...可以得出最後AC既算法..
1. 活用COUNTING SORT方法, STORE哂 cnt[0..9], 並計sum_digit
2. check cnt[0], 如果無0, 則皮已收, 否則係一定有答案!!!! (最少都係0 !!!)
3. 取sum_digit % 3, 分case考慮 :
3a 如果 r = 0 , 則只可能為全 0 (答案為0) 或 可以用哂全digit, 則由大至小output cnt[i] 個 i
3b 如果 r = 1 or 2, greedy + hardcode 地check最小可以delete走邊一個 (兩個) digit
4. 最後check多一次del完後是否全0, 是則答案為0, 否則大至小output cnt[i] 個 i
全算法為O(N) (計SUM, 取餘, 分case check 全部都係linear)
C: (Updated on 2/8/2012)
一題望上去同tag感覺差好遠既題目...題意好難解清楚 唔重複鳥 總之第一下係諗到關t-sort事..
但tag係brute force..嗯..
graph就一定係graph啦, 首先將d task 分3組..當3個大node...
3個大node之間又有transfer cost... (1 or 2)
無咩idea..brute force姐..唔通dfs search (o:
隨便問GG, 竟然係頹做 而且係易證頹做方法CORRECTNESS
真係爆頭...對望紙上既graph...
咦好似有d奇怪...
點解 transfer cost 為 1 既係同一方向 (anti clockwise) 同樣 2 既都係同一方向(clockwise)
咦咁其實 假設我係room 1, 下一步我可以去room2 或3 做task都得, 問題係去邊個先會minimum
但其實係無分別的!!!
room1 --> room2 --> room3 係 1+1 = 2
但如果room2 無task既, 我直接去room3 其實都係1+1 = 2 或者直接去都係2...
換句話講其實我不論下一個task係邊, 我順住 cost係1咁轉房一定唔會差過行cost 係2..
再加埋簡單一個道理: 同一間房既task 可以做既當然一次過做哂先, 剩番做唔到既一定係depends on 其它房既task, 咁只要轉房, repeat, repeat 直到做哂所有task為止..
唯一變數係一開頭係邊個房開始...咁咪試哂佢囉 (brute force!)
so...最後1棍AC既算法係咁的:
1. for i = 1 to 3, 當一開頭係room i 開始, 並設cost = n (最少都係n)
2. 直到做哂所有task之前, repeat以下事件:
- 做哂所有當前房間可做既task, 直到無得做
- 移去下一間房, 同時cost + 1
(以上都係用多d flag, 同埋用in edge 黎判斷就可以)
3. take i = 1 to 3 之間cost既minimum, outout
總結...繼續努力..一路睇演算法筆記+MIT algo lecture, 一路實戰做題目..假以時日係pick up到既!!
目標係codeforce / topcoder 轉色!!
沒有留言:
張貼留言