HKG Time - 1910 to 2410
OJ提交：
這份題目頹題及難題各參一半
頹的很頹，一眼看出算法
難的我覺得很難，但都給 CTLi 早段時期秒殺了
| Rank | Name | Solved | Time | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | RoyalRoader.(KAIST) | 10 | 733 | 1/4 | 1/16 | 1/27 | 1/49 | 1/36 | 2/118 | 1/74 | 1/85 | 1/165 | 1/139 |
| 2 | ManiAC | 8 | 843 | 1/4 | 1/39 | 3/91 | 3/60 | 1/24 | -/- | -/- | 3/280 | 1/150 | 1/75 |
| 3 | nekonekosoft.(National.Taiwan.U) | 7 | 656 | 1/11 | 1/109 | 1/59 | 2/31 | 1/48 | -/- | -/- | 1/158 | -/- | 1/220 |
| 4 | reverse_iterator.(Seoul.National.U) | 7 | 748 | 1/4 | 1/12 | 1/83 | 3/117 | 1/24 | 2/225 | -/- | -/- | 1/223 | -/- |
| 5 | BurgerKing.(KAIST) | 7 | 758 | 1/3 | 1/34 | 1/25 | 2/155 | 1/66 | -/- | -/- | 1/242 | 1/213 | -/- |
| 6 | const_iterator.(Seoul.National.U) | 6 | 501 | 1/10 | 1/14 | 2/53 | 2/109 | 1/63 | -/- | -/- | -/- | 1/212 | -/- |
| 7 | d3sxp.(Kyoto.U) | 6 | 522 | 1/6 | 1/24 | 1/57 | 2/78 | 1/110 | 1/227 | -/- | -/- | -/- | -/- |
| 8 | Say.Yes.(Seoul.National.U) | 6 | 605 | 1/4 | 1/38 | 2/56 | 4/155 | 1/32 | -/- | -/- | 1/240 | -/- | -/- |
| 9 | Noname1.c.(Korea.U.) | 6 | 611 | 1/4 | 1/28 | 1/47 | 4/140 | 1/77 | -/- | -/- | -/- | 3/215 | -/- |
| 10 | PENDING.(Seoul.National.U) | 6 | 709 | 1/3 | 4/68 | 1/26 | 1/166 | 2/152 | 4/154 | -/- | -/- | -/- | -/- |
毫無疑問，我們再一次給 Judge 玩殘了...
(~按嚴重情度排列)
- Problem F - Memory 嚴重不足
當我們自滿地把 memory usage 由 19x MB → 110 MB → 51 MB，還是 MLE!!
最後 Joe 加了很多 coding technique 終於壓至 2x MB
可惜 WA (實在太多太多為節省memory而添加的無聊細節了) - Problem H - Test data 違反 assumption
CTLi 在首次提交後返回 RTE，立刻意識到 N = 1 的陰險情況
可是，對 N = 1 而言 "the two largest penalties" 是 undefined...
(就這樣看來 N > 1 理應是 implicit constraint)
CTLi 只好勉強把它理解為 "the largest penality" for N=1，提交卻返回 WA
至 training 後期，CTLi 才調試出 s_i <= c_i 的條件不滿足!
(第一個 version 的 code 本來 AC 的!!) - Problem C - Test data 太不厚度吧？
我的 O(N lg N * 5) 算法 TLE 了... (N <= 7776)
後來改為 O(N * 5) 以 2.xx 秒通過 ... 但這 Runtime 也太慢了吧?
On-site 大量隊伍很早通過，我就不相信他們都是用 O(N * 5) 或更好的算法!! - Problem G - Test data 違反 assumption
這是 post-training 做的題目
在 training 時我已經想暴力猛搞... 因為有隊伍在 7x 分鐘通過
貌似 valid 的條件相當苛刻
回家時剛剛 AC... 發現 test data violates "This graph is always a connected graph." - Problem D - Test data 不厚度
SCC 建圖 → 9.719 sec 通過... 幸好是 1Y
Champion - KAIST 很高速... 就連難題也極速 AC
最後我們做了 8題
但我堅信，如果沒有 OJ 的無聊限制... 絕對有機會全清
可，要在速度上快過 Champion，則貌似難度太高了...
是次 Training 我純粹做無聊題 (A, C, G)
做得比較差...- -
G 沒能寫出來是失敗...
(讓我給自己一個借口吧)
但這也跟之前無辜地卡 H, F 有關
算法精簡概要：
A: 水題 (Kn)
B: Memorized 暴搜 (Joe)
C: 枚舉 (Kn)
D: SCC (Joe)
E: DP / Counting (Joe)
F: Binary Search + Disjoint Set (Joe, 其後通過)
G: 暴搜 (Kn, 其後通過)
H: 貪心 (CTLi)
I: Ad-hoc (CTLi)
J: 貪心 (CTLi)
距離大家人生最後一場 ACM 比賽還有兩個月時間...
ManiAC... 努力吧!!
沒有留言:
發佈留言