※ 引述《smartboy (小光光)》之銘言：
: Name Solved Score A B C D E F G H att/solv
: 1 Wall 6 703 2/152 1/192 1/45 2/52 2/127 1/75 0/-- 0/-- 9/6
: 2 Better 6 1220 1/153 6/270 1/237 4/99 1/111 1/190 0/-- 1/-- 15/6
: 3 Escape 5 757 1/139 4/-- 1/71 2/43 3/166 3/238 1/-- 0/-- 15/5
: 4 NoName 4 464 2/261 1/-- 1/45 0/-- 1/58 1/80 0/-- 1/-- 7/4
: 5 ( ] 4 1119 0/-- 1/-- 4/244 2/239 1/237 2/299 0/-- 0/-- 10/4
: 6 Somi 3 734 0/-- 0/-- 1/71 5/250 0/-- 6/233 0/-- 0/-- 12/3
: 7 XDman 2 425 5/-- 0/-- 12/-- 3/271 4/-- 1/114 0/-- 0/-- 25/2
: 8 Mictor 1 180 0/-- 0/-- 2/160 0/-- 0/-- 0/-- 0/-- 0/-- 2/1
: 9 YSL 0 0 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/0
: Summary 11/139/4 23/45/7 12/58/5 1/--/9 95/31
: 13/192/2 18/43/6 15/75/7 2/--/0
這次是用 ACM ICPC 2001 Asia region, Taejon site (韓國) 練習
資料可以在網站上找到, 包括 test data, 以及當時的 standing
http://icpc.baylor.edu/past/icpc2002/regionals/Taejon01/
http://cs.kaist.ac.kr/~acmicpc/standing.html
當時最多五題, 也就是說模擬賽的隊伍跟當時比較成績還不錯
(當然不排除當時他們可能也有 rejudge 之類的事發生)
以下是我對這次模擬賽的一些 random note,
* 比賽進行
( ] 隊在比賽開始一兩個小時後才開始寫, 因此 penalty 比較高
YSL 棄賽
比賽進行到一半, C 跟 F 兩題 rejudge
pc^2 server 是地下室的 acmclub server, 比賽中因不明原因 reboot
使得 submit/judge 停擺了約三四分鐘
* 題目
詳解就請各位發揮了
B 用 greedy 解, 誰能證明一下呢
F 似乎有兩種 greedy 法, 其中一種做法跟 B 很像,
另一種據 ledia 說這題剛好符合某些條件, 剛好可以用
A, D, E, 大致上不難
G 我覺得善用 computational geometry 裡常用的
doubly-connected edge list 就不難了, 只是我看大部分人都不熟這東西
H 是 vertex covering (NP-C 問題) 的一個變形, 我不確定還是不是那麼難,
各位可以驗證一下. 我印象中我兩年前寫這題用的方法就是用遞迴窮舉做的.
不過我一時想不起來當時可有什麼比較好的寫法可供大家參考.
* 解題流程與策略
由於 C F 兩題 judge answer 有誤, 打亂了不少隊伍的解題過程,
我覺得可惜, 練習品質因此差了點. 不過反過來說讓大家練習怎麼應付不完美的比賽.
每個比賽的隊伍都很可能遇到類似的狀況 - 明明程式看起來是對的,
不知為何 judge reply wrong answer.
無論是真的有 bug 或 judge 錯了, 隊伍仍要繼續往前進,
也許是撥出一部份人力解新的題目, 或完全放下卡住的題目, 衝新的問題.
甚至你認為原來寫法的確很容易錯, 也許可以重寫.
就是不要卡住不知道該怎麼辦.
還有一個我常常提醒的是接近比賽尾聲時, 常發現一隊三人會有閒置的人力,
他可能就開始上網/打混/做其他事, 而非幫忙解題.
無論是題目快解完沒新題目, 或時間快到放棄其他題, 都不應該浪費人力.
請發揮你們的想像力, 替閒置人力找到他可以幫上忙的地方, 把最後幾題衝出來.
以我今天跟比賽同學講的例子, 一個人正在寫最後一題, 一個人幫忙看/討論,
一個人不知道幹麻, 我覺得你可以幫忙看, 若自己寫程式比較快, 也許搶過來,
或是自己獨立在紙上寫 code, 或切一小塊模組來紙上寫, 或幫忙生些 test case
若寫完馬上可以派上用場. 種種可能.
另一個例子, 有一隊在衝他們的最後一題, 在 debug, 一人 online debug,
另兩人幫不上忙. 你們也許可以考慮彼此解釋 code, 或印幾分大家幫忙看,
其他人若也會寫, 可以在紙上重寫, 寫完後再上機, 把 online debug 的人 offline.
回到這次比賽, 解出第一題簡單題的時間應該可以更快些,
這可能就要各隊自己檢討問題出在哪,
題目看太慢不懂, 判斷錯難度, 想錯解法, 不熟悉要用的算法, 還是溝通不良, 等等.
* judge
一開始由 smileshou 辛苦幫忙 judge, 後來他幫忙買大家的晚餐,
由我接手 judge 工作.
我稍微描述一下我覺得 judge 要注意的事, 供往後模擬賽的 judge 參考.
最理想狀況是題目出得很完美, 現場 judge 只要利用設定好的 autojudge 就一切 ok,
這很難發生, (我猜測)也因此 pc^2 系統從以前到現在都設計成半自動 judge.
judge 最好能在 judge 前先讀過題目, 對題目及解法有一定了解, 譬如哪幾題比較難,
哪幾題複雜容易錯, 那幾題可能會執行比較久, 哪幾題 case 比較多.
這樣 judge 過程中, 比較容易注意到問題, 舉個例子, 如發現大家全都超時,
究竟題目本身性質如此, 還是要去檢查 input format 跟題目上說的是否相同.
最好的情況當然是出題者自己擔任該題的 judge 工作.
比賽中 judge, 無論是對是錯或其他情況, 除了用 autojudge 工具,
仍應用眼睛看一看, 譬如今天 pc^2 diff 說 wrong answer, 我用眼睛看起來一樣,
才知道是 judge answer 多了空白, 與題目敘述不同.
對於不同的錯誤, judge 應盡量給與精確的回應,
譬如是 time too long, 還是 wrong answer 要分清楚.
可是反過來說, 比賽選手要有心理準備 judge reply 可能不是很精確,
至少比賽經驗有時 reply 不太可信.
judge 除了每個 submit 看, 也要注意整體狀況, 譬如某一題一直沒人對,
或簡單題很多人錯, 都有可能是 judge testdata 有問題.
若 submit queue 不會太長, 我 judge 時也喜歡隨意打開各隊程式看一看,
看看他是不是用了我預期的解法, 或他寫了什麼特別的 code, 是否掉到某陷井.
這也有一點點觀摩學習的效果.
譬如今天我就利用這樣, 知道 team Wall B 題的解法(我本來沒想出來),
也發現 F 題有我預期之外的解法, 而且 code 跟 B 題幾乎相同.
以上種種都是希望 judge 能盡早發現問題及時修正/rejudge,
雖然大家都很討厭比賽中 rejudge, 但總勝過賽後才找到/還沒找到問題
模擬賽的品質, 在決定用哪套題目後, 就完全仰賴 judge 的表現.
各位要是有機會當 judge, 希望能多注意.
--
"聲音是聲音, icon 是 icon, 用 icon 來表示聲音的結果,
就是不知道哪個是聲音, 哪個是 icon. "
小光光
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.70.142.187