今天是久違的 team training
雖然人未齊
最後我們 team (= Joe + Kn) solve 了 4 題
超超 solve 了 5 題
(scoreboard後補)
總而言之,今天表現很差(未至極點,但差不多了...)
寫出來的 code,code length 差不多是正常版本的 2 倍
我做到的 2 道題目,分別是 standard 到不行的 BFS 和 Shortest Path...
卻總共錯了 5 棍...
雖然沒有從口裏說出來
但我確實拖累了 Joe
讓他沒有時間想/code/和我discuss 第 5 條題目...
愚以為不是 coding 能力的問題,而是不夠冷靜的問題...
Joe 又道出一個慘痛的事實:我們敗給 8 年前的 Warsaw !!
(而超超則單挑奪得亞軍)
Problem A: ICPC 2662 Family
解:頗直接的 High precision+Topological sort
可 Live Archive 不能提交 BigInteger/BigDecimal
──講起我就扯火:
在若干年前,我幾經辛苦(1~2 hr)
如果可以用 Java BigDecimal 我絕對會上...Problem B: ICPC 2663 Intervals
解:Binary indexed tree/Greedy
被 Joe 輕鬆解決
Problem C: ICPC 2664 One-way traffic
沒有 idea...
有 flow 的感覺應該是先把所有 SCC 找出黎,然後... dunno
(2010-07-21更新: 題解是做一次DFS... 詳細未看)
Problem D: ICPC 2665 Rhombs
沒有 idea...
他們聽過超超複雜的解說以及看完了他極短的代碼以後
判定為 mission impossible(雖然這題 AC 的比率極高)
Problem E: ICPC 2666 Servers
沒有(時間)認真想...
這條題目我沒有參與閱題
後來發現光是理解 interesting 的定義已經要花點時間
Joe 在 training 時讀漏了一項 constraint - this sum does not exceed 30n
他說,若果當時有發現應該能頗輕鬆地解決
(2010-07-21更新: Joe 以 shortest path 輕鬆解決)
Problem F: ICPC 2667 Solitaire
解:Bidirectional BFS
其實我想過 64C4 ── 只是一種不同的形式 ── array of pair<int,int>
最後選擇使用 long long int 做 encoding
是因為可以減省 code length
另外,因為 range 比較小,關於運行時間上問題應該不大
coding 過程卡了很久...
- 閱讀題目漏了 step ≤ 8 ...
- 用 single source BFS 單是運行 sample 已經要花 1.0 sec
在頗後期才想到可以雙向搜 ... - Logical bug:
Incorrect:
while (h != t) { if (current > 4) break; exp(node);}
Correct:
while (h != t) { if (current >= 4) break; exp(node); }
而且還一次過出現三項...
Problem G: ICPC 2668 Timetable
解:Variation of Shortest Path
state[city][time] := 由 city 在時間 time 出發,抵達 city N 的最早時間
具體實現方法:
先把所有 <N, time> push 進 queue/priority_queue
然後用你最喜愛的 shortest path algorithm往前搜
──建議 SPFA/Dijkstra with heap,因為數據規模較大
這道題也卡了很久... 做了一個懶醒的「優化」導致 WA
(後來發現這優化在 worst case 時幾乎起不到作用)
添加了不少不必要的行數...
(2010-07-23更新: 同一算法提交至 PKU1203 → TLE)
Problem H: ICPC 2669 Voracious Steve
解:Game/DP + 打表
Joe 和 我 都沒有想出好的算法
Joe 最後用 O(1005) 時間打表提交
(打表大約花費 1.5 minute)
On-site champion 解了 7 題
1st-runner up 解了 5 題
我當時的算法錯了...
如果 CTLi 在場,或者可以更快地解決 H
(他可以解決 D 嗎?我想應該可以)
那 Joe 便有時間想 C 或 E
不過考慮到這是 8 年前的題目... 我們怎麼都是輸了...
感想:還是不夠冷靜吧...
倘若能夠把平日 Training 剩下的題目全部...
不,一半
做好,已經可以變得相當厲害了...
我要變強呀......!!
至低限度... 要能夠二人合力擊敗超超!!
完全 Offtopic:偶然間發現... 在 vision / graphics 界的 research 頻繁
~= k維 的 Segment Tree (好似係)
(2010-07-30 更新)
剛才就問起 CTLi 有關於 Problem D:
kn 說:
*is that rhombus problem intuitive to you?
Ivan the Terrible 說:
*quite
kn 說:
*i see
沒有留言:
發佈留言