出過題目，整過system，做過judging，今次無疑TFT的工作量比想像中大。
結果方面，有點失望，那4題居然可以令各位高手失去這樣多分，更慘的是，只有兩個人可以分別在一題中得到滿分，其他的都是水回來的。如果仔細分析結果，其實我知道大家的實力不差，看過source code，知道寫得接近滿分的大有人在，就是只差一點點... 大家都盡了力，在4小時的腦力戰中不斷努力，而且其實每一題也有人想過滿分的做法(其實不是，有一題是沒有人想到的，而最慘的是出題者以為這一題是最淺的...)。
今次TFT可以看到大家對HKOI的認真程度，的確是有努力過的人，考得比預期好，加上天分(注意，我這裏是努力加天分，不是天分加努力，因為我個人認為在HKOI，尤其TFT，是努力比較重要的)，便是香港的一流代表，能出去見人。所以付出的雖然多，但是看到的結果其實是很欣慰的。
我不得不承認，中間是有不怎麼令人回味的事情，但事情過了之後，是大家增加對彼此的了解，也是好的。詳細不會再說了，但其實我必須和你說對不起。哈哈，這又完了，真的很快又一年了，上年TFT還是不懂DP，今年懂了，上年TFT還是甚麼經驗也沒有，經過一年ACM的洗禮之後，又是另一個層次了。下一年的這個時候，不知又是如何呢？大概又是另一個景況了。
不久之後，又是HKOI 2012了，很期望，很期望看到一班新的選手，也很期望看到舊的選手學到新的知識，累積更多經驗，在比賽再創高峰。
P.S. 其實我在比完賽後的一句「你地覺得HKOI senior咁易，個個滿分，所以TFT出得難D」是真心話，說實，如果我不是希望大家下一年再接再厲，繼續玩HKOI，我不會儘量把題目難度降低的。:-P
2011年5月17日星期二
HKOI TFT 2011 (2) system篇
平時mini-comp，做的server工作都只是一些latex和mysql，沒有甚麼真的很難(當然，我一開始也是甚麼也不懂的)，今次單是system的選擇已是困難的開始。
選用Linux，其實一開始我也是挺反對的，始終大家平時用的都是Windows，用command line已經少，更何況用Linux，因為我仍然很記得我一開始用Linux的不習慣，所以我很擔心參賽者可否在短時間內學懂。因此，當知道Linux是一定要用的時候，我特地在judge提大家要早一點到，而比賽中也會提供一切與system有關的協助，幸好，一切都沒有因system做成很大的影響，最少沒有人因為system而交錯題目，或是改錯名，這是比HKOI的一大進步。
然後，是judging system的難題，一向我們用的program是給Windows的，一轉用Linux，便要用HKOJ的judge。有幾樣東西judge是不支援的，因為基本上judge的模式是用ACM的，反應大多只有Accepted，WA，TLE之類，對分數的分派是比較落後的。簡單來說，它是沒有分case給分，即是每一個case佔的分數一定要一樣。另外一樣是沒有partial scoring，即今次mars所要求的評分方式。因此，我今次「有幸」可以研究judge個program的運作，並且在judge作了一些改動。以今次比賽的評分來說，又有partial scoring，又有interactive，真的不簡單。
另外，別以為一個judge便可以解決整個比賽的judging的問題，因為除了要judge之外，還要batch run同給feedback。因此還是要用那一個perl的程式。食judge的feedback的問題搞了我很久，但最後都是在Pascal的部分TLE的情況下失敗，是今次judge的一個遺憾。
最後的network問題，也是今次最無助的地方，被Hackson秒速解決，但由於那個網路實在是太可惡了，所有network都不是互通的，因此都是要回到那逐部機用手指copy的慘況，雖然遲了judge，但結果還會是一樣的...
看看有沒有時間研究一下個judge，很希望把HKOJ改得更好，以後support比賽可以更方便和更完善。
選用Linux，其實一開始我也是挺反對的，始終大家平時用的都是Windows，用command line已經少，更何況用Linux，因為我仍然很記得我一開始用Linux的不習慣，所以我很擔心參賽者可否在短時間內學懂。因此，當知道Linux是一定要用的時候，我特地在judge提大家要早一點到，而比賽中也會提供一切與system有關的協助，幸好，一切都沒有因system做成很大的影響，最少沒有人因為system而交錯題目，或是改錯名，這是比HKOI的一大進步。
然後，是judging system的難題，一向我們用的program是給Windows的，一轉用Linux，便要用HKOJ的judge。有幾樣東西judge是不支援的，因為基本上judge的模式是用ACM的，反應大多只有Accepted，WA，TLE之類，對分數的分派是比較落後的。簡單來說，它是沒有分case給分，即是每一個case佔的分數一定要一樣。另外一樣是沒有partial scoring，即今次mars所要求的評分方式。因此，我今次「有幸」可以研究judge個program的運作，並且在judge作了一些改動。以今次比賽的評分來說，又有partial scoring，又有interactive，真的不簡單。
另外，別以為一個judge便可以解決整個比賽的judging的問題，因為除了要judge之外，還要batch run同給feedback。因此還是要用那一個perl的程式。食judge的feedback的問題搞了我很久，但最後都是在Pascal的部分TLE的情況下失敗，是今次judge的一個遺憾。
最後的network問題，也是今次最無助的地方，被Hackson秒速解決，但由於那個網路實在是太可惡了，所有network都不是互通的，因此都是要回到那逐部機用手指copy的慘況，雖然遲了judge，但結果還會是一樣的...
看看有沒有時間研究一下個judge，很希望把HKOJ改得更好，以後support比賽可以更方便和更完善。
HKOI TFT 2011 (1) 題目篇
今年的TFT，第一次不是以參賽者的身分出席，感覺又是完全不同，所以今次blog想說的，主要不會是圍繞題目，而是想說說整個籌備過程的經歷。
基本上今年的TFT的籌備過程的人手不多，所以每一個人的工作量也隨之而增加。可是，今次的過程學到的技巧，卻是當初也沒有想過的多。更出乎我意枓之外的，是今次TFT中，我對自己的了解。
先說題目吧，可能大家會比較有興趣一點。今年可以選擇的題目並不多，而題目之間的變化也不多，加上大家也希望題目以優美為目標，所以其實大部分的題目並不太適合TFT。始終TFT的主要目的是選擇合適的學生作為代表香港參加IOI或NOI，這個目標已經很難達到。
要知道太難的題目又會令所有人的分數極低，即使可以強行選出8位選手，卻難以令一班trainers以至其他trainees認為這會是最合適的人選，我自己可以想像的情況是︰
(1) 一位參賽者因某一方面(不是整體的algorithm，而可能單單是combinatorics)特別強，令他在其中一條題目拋離其他選手，從而得到代表香港的資格。要知道外面的比賽考的並不一定是TFT的題目，即使他在一方面特別強，出到去其實可能甚麼也不能，結果在比賽中表現不如理想，很明顯，他未必是理想的人選。
(2) 某數位參賽者因在某一題(或者其中幾題)成功水分，令他們以些微分數，擊敗其他更有實力的選手。你可能會認為，這樣選出來的人，是經過正確的途徑去選，而落選的是因為他的發揮未夠穩定，沒有甚麼不妥的地方，可是，我希望選出來的人是具有實力的，儘量不是因比賽的小技巧而得到代表香港的資格。小技巧固然有用，但在香港的選拔體制裏面，是一次定生死，以運氣為主的方法入選，未免太不公平了。
此外，太容易的題目一樣會令原本較有實力的選手落選。如果比賽有partial feedback的話，是沒有問題的，最少每一個人的不確定性會減到最低。但因為比賽連compile和run sample也沒有，很多時會因為一些很無聊的bug而損失大量分數，同樣選出來的人並不是有實力，也不是好運，只是其他應被選的人沒有運而已。
所以，選合適的題目完全不容易，為此我們也談了很久，題目的難度是其一，類型也是考慮因素之一，總沒有可能4條都是DP吧...其實還有其他考慮，其中一樣是希望實力未達到入隊水準的也有一個很好的比賽經驗，當中最重要的是給他們成功感，但又不能因此出一條很容易的題目，令可以作為真正選人的題目只有3條，反正很多時最好與最差的選手的實力相差太遠，很難以4題分別顧及這兩種人。
最後，出來的效果並不如理想般好，但勉強都算達標。真的是一線之差，就令整個TFT的意義失去，的確，只有2個人可以在一條題目中滿分，是比我們想像中要差。幸好，參賽者也明白題目的內容，負責problem statement的我感到安慰，尤其是第一題，概念很複雜，又要用一些較實際的例子來說明，又不可令statement太長，真是修改又修改才成為最後的版本。
2011年4月22日星期五
HKOI 2011 Mini Competition 3
很久沒有寫了，今次的題目是Mini comp 3，可能你會奇怪，為何mini comp 2沒有在這裏出現，其實話說有另外一個人寫了，但很久很久還沒有upload上來，所以大家先看到的會是mini comp 3的解題。
今次的題目相對比以往的難，最少比較難得到滿分。此外，由於大家似乎對MST不很熟，特地出了一條模板題，讓大家有心理準備，這一類data structure是應該隨手可以code出來的。
分數方面，我是頗為失望的，一條模板的MST，竟然沒有人得到滿分！而出席的人當中，有不少更是有機會代表香港出賽的選手，大家似乎要加把勁了。
HKOJ1142 - Jump Across the River
第一題便是我自己的作品。一條挺明顯的DP，state是[到了第幾格][上次跳了多少步]，時間為O(NK2)。可能有人會問，既然可以向後跳，為何可以用DP？
事實上，我們可以證明最優的跳法是可以不用向後跳的。首先，如果向後跳的格數和向前跳的一樣，其中一個最優解可以是之前向前跳少一步，而所用的energy是一樣的。如果向後跳的格數和向前跳的不一樣，我們也可以很直接的推斷到在之前用1 energy跳短一點也可以做到相同效果。因此，這題會有最優的部分解。
此外，這題也可以用shortest path來解決的，方法與DP的相似，只是搜索順序不同。
仍然過不到的人，請再仔細看題目。
HKOJ1143 - Density Index
這題考的是數學基本功，基本上用中學學過的algebra，列出題目中的式子，拆開再用電腦快速計算便可以O(n)的時間解決。
HKOJ1144 - Minimum Spanning Tree
真的是基本功，一定要懂，不懂的請參考http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure，這裏不說了。注意的是文中的rank其實可以不寫，因為總的來說，用的時間也是接近O(n)。
HKOJ1145 - Lucky Bin Packing
最後一題是我找到很有趣的一題ad-hoc加少少math的題目。很多case，因此很難得滿分，所以連sample solution都錯了，但是我個人認為這題是值得思考的，而且可以訓練各位的小心程度。
下一次比賽便是APIO，再來就是TFT了，很緊張呀！注意，在寫這一篇文前，TFT的題目還沒有出好，所以大家不用有任何的揣測，這個絕不是放水的地方。但是一個永恆不變的道理，要在TFT上表現得好，不單要做題目，還要積極和認真參加比賽，得到實戰經驗，才可百戰百勝。
今次的題目相對比以往的難，最少比較難得到滿分。此外，由於大家似乎對MST不很熟，特地出了一條模板題，讓大家有心理準備，這一類data structure是應該隨手可以code出來的。
分數方面，我是頗為失望的，一條模板的MST，竟然沒有人得到滿分！而出席的人當中，有不少更是有機會代表香港出賽的選手，大家似乎要加把勁了。
HKOJ1142 - Jump Across the River
第一題便是我自己的作品。一條挺明顯的DP，state是[到了第幾格][上次跳了多少步]，時間為O(NK2)。可能有人會問，既然可以向後跳，為何可以用DP？
事實上，我們可以證明最優的跳法是可以不用向後跳的。首先，如果向後跳的格數和向前跳的一樣，其中一個最優解可以是之前向前跳少一步，而所用的energy是一樣的。如果向後跳的格數和向前跳的不一樣，我們也可以很直接的推斷到在之前用1 energy跳短一點也可以做到相同效果。因此，這題會有最優的部分解。
此外，這題也可以用shortest path來解決的，方法與DP的相似，只是搜索順序不同。
仍然過不到的人，請再仔細看題目。
HKOJ1143 - Density Index
這題考的是數學基本功，基本上用中學學過的algebra，列出題目中的式子，拆開再用電腦快速計算便可以O(n)的時間解決。
HKOJ1144 - Minimum Spanning Tree
真的是基本功，一定要懂，不懂的請參考http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure，這裏不說了。注意的是文中的rank其實可以不寫，因為總的來說，用的時間也是接近O(n)。
HKOJ1145 - Lucky Bin Packing
最後一題是我找到很有趣的一題ad-hoc加少少math的題目。很多case，因此很難得滿分，所以連sample solution都錯了，但是我個人認為這題是值得思考的，而且可以訓練各位的小心程度。
下一次比賽便是APIO，再來就是TFT了，很緊張呀！注意，在寫這一篇文前，TFT的題目還沒有出好，所以大家不用有任何的揣測，這個絕不是放水的地方。但是一個永恆不變的道理，要在TFT上表現得好，不單要做題目，還要積極和認真參加比賽，得到實戰經驗，才可百戰百勝。
2011年3月20日星期日
HKOJ 1136 - Advertisement
這是一條經典題，由往年的training中找回來的，至於原出處，我是不知道的。
我希望在此說的是如何得出algorithm，而不是algorithm本身。
不難想到，這是一個可以貪心解決的問題，但是如何貪心才是重點。我們可以嘗試用人腦思考，當我們遇到同樣問題時，如何解決呢？首先我們列出最早的時段(先不說如何定義最早)，我們知道一定要放一個廣吿進去。很明顯，不放在整數點是沒有好處的。只需考慮整數點，但想放得早，中間，還是遲？
若果這是最早的時段，當然不是放最早吧，放中間也似乎沒有甚麼好處，姑且放最後吧。這樣，我們的第一個solution出來了，由最早開始的時段開始考慮，每一個時段如果還沒有廣吿，便放一個廣吿在最後。
下一步是驗証。好像如果第一個考慮的時段T1完全包住另一個時段T2，即T2的開始比T1遲，且T2的結束比T1早，明明一個廣吿便可以，我們的solution卻用了兩個。
於是我們便想如何去改正，似乎有兩個方法，一是把廣吿放在一個時段的最後是錯的，二是考慮的次序有問題。
先說一，如果我們不應放在最後，那麼我們很難想到放中間的甚麼位置會較好，而且似這一條問題會變得很難，不是用greedy可以解決。想不到其他solution才再想吧。
再說二，用以上的反例去考慮，我們需要的是把T2排得比T1早，很自然，如果我們以結束時間來排，T2是會比T1早，再想想logic上對不對。因為早結束的時段也必須有一個廣吿，如果我們順結束時間來排，而每一個廣吿也會放在一個時段的最後，我們並不會漏放廣告，在考慮每一個時段時，也不須往回去考慮，在時間複雜度方面也是很理想的。
最後一個問題，也是最重要的，是這樣放是否最優？我們也不難說服自己，反正每一個時段都要放廣告，放最後只會惠及未來要考慮的時段，並不會使未來的時段更差，所以應該都是最優解。
總體來說，time complexity是O(N log N + N) = O(N log N)，N log N 是來自sorting，N則是再掃一次每一個時候，考慮應否放廣吿的決策。有的在judge TLE的同學是用了N2的sorting，快點記/學一個N log N的sorting吧，否則會很蝕底的！
我希望在此說的是如何得出algorithm，而不是algorithm本身。
不難想到，這是一個可以貪心解決的問題，但是如何貪心才是重點。我們可以嘗試用人腦思考，當我們遇到同樣問題時，如何解決呢？首先我們列出最早的時段(先不說如何定義最早)，我們知道一定要放一個廣吿進去。很明顯，不放在整數點是沒有好處的。只需考慮整數點，但想放得早，中間，還是遲？
若果這是最早的時段，當然不是放最早吧，放中間也似乎沒有甚麼好處，姑且放最後吧。這樣，我們的第一個solution出來了，由最早開始的時段開始考慮，每一個時段如果還沒有廣吿，便放一個廣吿在最後。
下一步是驗証。好像如果第一個考慮的時段T1完全包住另一個時段T2，即T2的開始比T1遲，且T2的結束比T1早，明明一個廣吿便可以，我們的solution卻用了兩個。
於是我們便想如何去改正，似乎有兩個方法，一是把廣吿放在一個時段的最後是錯的，二是考慮的次序有問題。
先說一，如果我們不應放在最後，那麼我們很難想到放中間的甚麼位置會較好，而且似這一條問題會變得很難，不是用greedy可以解決。想不到其他solution才再想吧。
再說二，用以上的反例去考慮，我們需要的是把T2排得比T1早，很自然，如果我們以結束時間來排，T2是會比T1早，再想想logic上對不對。因為早結束的時段也必須有一個廣吿，如果我們順結束時間來排，而每一個廣吿也會放在一個時段的最後，我們並不會漏放廣告，在考慮每一個時段時，也不須往回去考慮，在時間複雜度方面也是很理想的。
最後一個問題，也是最重要的，是這樣放是否最優？我們也不難說服自己，反正每一個時段都要放廣告，放最後只會惠及未來要考慮的時段，並不會使未來的時段更差，所以應該都是最優解。
總體來說，time complexity是O(N log N + N) = O(N log N)，N log N 是來自sorting，N則是再掃一次每一個時候，考慮應否放廣吿的決策。有的在judge TLE的同學是用了N2的sorting，快點記/學一個N log N的sorting吧，否則會很蝕底的！
2011年3月5日星期六
HKOI 2011 Mini Competition 1
哈哈，今次的mini-comp其實都是我選題目的，基本上除了一題是我自己出之外，其他都是參考一些過往的比賽的，我不會全部公開那些題目的來源，以免以後不能再用這些source，但是大家做多一些題目，總會有機會遇到類似的，有利而無一害。
難度方面，今次特地出得容易一點，尤其第一和第三題，希望每一個人也可以得分，而第五題是刻意比較煩和難的，希望大家可以練練implementation skill，做到我手寫我口的境界。
分數方面，有點可惜有些大牛沒有出席，但整體還是比我預期的高。唯一比較失望的是第四題只有一個人得滿分，其餘的更只有10分。還有一些submission是因為沒有sample input的feedback而失去大量的分數，例如MLE或是食input的問題。
HKOJ1131 - Smallest and Largest
經典題，也是送分題。
注意︰食N位的string要開最少N+1位的char array。
HKOJ1132 - Expand
其實結果比我預期好，有兩個人滿分，其餘的表現也不錯。大家普遍也可以食到string，只是不能全部處理所有case。
真的過不到的，試試下面這個case吧︰
0(9(9(9(9(9(9(9(9(9(9(9(9(9(9(9)))))))))))))))
還有，剛剛發現了其中一個case是錯的，現在已經rejudge。
HKOJ1133 - Grid Cipher
這題終於是我自己的作品 :) 。雖然簡單，但也有人因為食input錯而失分。更有人因為不記得删除debug的output而變成0分。
HKOJ1134 - Sorting Stack
這個只需要做一些實驗，便不難發現一個很重要的observation︰不用處理的element永遠是最大的數個，之後的solution也不難想到。應該20行便可以code完。
HKOJ1135 - Battleship
守門口的一題，也是最tricky的一題，考驗大家implementation的功力。題目來自URAL，一如我預料，沒有人能拿滿分，也許是大家不夠時間去做這題吧，所以我預期只有最強的大牛才可以嘗試在這題得高分。
最主要的observation是S很小，所以可以藉枚舉所有不能放的位置，再用所有可能放的位置減去這個數字，便是答案。至於具體細節，便要大家交上judge試試了，如發現在URAL答錯而HKOJ正確的人(注意，交的不是同一個program，XY是換轉了)，請吿訴我，有酬。
下一次mini-comp希望更多人參加，令氣氛更激烈。題目也會相對這次更難(因為有同學說今次太容易了)，而且會正式用到數個月以來學的東西了。
難度方面，今次特地出得容易一點，尤其第一和第三題，希望每一個人也可以得分，而第五題是刻意比較煩和難的，希望大家可以練練implementation skill，做到我手寫我口的境界。
分數方面，有點可惜有些大牛沒有出席，但整體還是比我預期的高。唯一比較失望的是第四題只有一個人得滿分，其餘的更只有10分。還有一些submission是因為沒有sample input的feedback而失去大量的分數，例如MLE或是食input的問題。
HKOJ1131 - Smallest and Largest
經典題，也是送分題。
注意︰食N位的string要開最少N+1位的char array。
HKOJ1132 - Expand
其實結果比我預期好，有兩個人滿分，其餘的表現也不錯。大家普遍也可以食到string，只是不能全部處理所有case。
真的過不到的，試試下面這個case吧︰
0(9(9(9(9(9(9(9(9(9(9(9(9(9(9(9)))))))))))))))
還有，剛剛發現了其中一個case是錯的，現在已經rejudge。
HKOJ1133 - Grid Cipher
這題終於是我自己的作品 :) 。雖然簡單，但也有人因為食input錯而失分。更有人因為不記得删除debug的output而變成0分。
HKOJ1134 - Sorting Stack
這個只需要做一些實驗，便不難發現一個很重要的observation︰不用處理的element永遠是最大的數個，之後的solution也不難想到。應該20行便可以code完。
HKOJ1135 - Battleship
守門口的一題，也是最tricky的一題，考驗大家implementation的功力。題目來自URAL，一如我預料，沒有人能拿滿分，也許是大家不夠時間去做這題吧，所以我預期只有最強的大牛才可以嘗試在這題得高分。
最主要的observation是S很小，所以可以藉枚舉所有不能放的位置，再用所有可能放的位置減去這個數字，便是答案。至於具體細節，便要大家交上judge試試了，如發現在URAL答錯而HKOJ正確的人(注意，交的不是同一個program，XY是換轉了)，請吿訴我，有酬。
下一次mini-comp希望更多人參加，令氣氛更激烈。題目也會相對這次更難(因為有同學說今次太容易了)，而且會正式用到數個月以來學的東西了。
2011年2月7日星期一
HKOJ 1109 - A sort of Shell
題目大意︰大約是每一個command以最少的swapping做partial的bubble sort，問最後做完所有command之後做了多少次swapping。
由於array的長度達100,000，因此simulation是不夠快的 Complexity: O(N2)
Observation 1:
其實已在題目大意標明，這是一個partial的bubble sort。
Observation 2:
每一個bubble sort的minimum number of swapping是number of inversion，因此我們只需快速地計inversion的數目，便可以快速地simulate整個程序。
Inversion即是
因此，我們可以逐個command去simulate，每一個command，我們可以用merge sort去數，這只需要O(N log N)的時間。具體方法請自己想想，或是上網search。
總時間是O(MN log N)。
注意︰之前test data是錯誤的，我測試sample solution之後肯定了該錯誤，現在test data已經更正。建議WA的同學可試試這個case:
正確答案是0，而sample solution出的是14。
由於array的長度達100,000，因此simulation是不夠快的 Complexity: O(N2)
Observation 1:
其實已在題目大意標明，這是一個partial的bubble sort。
Observation 2:
每一個bubble sort的minimum number of swapping是number of inversion，因此我們只需快速地計inversion的數目，便可以快速地simulate整個程序。
Inversion即是
For each i and j, where i<j If Ai>Aj, then this counts as one inversion
因此，我們可以逐個command去simulate，每一個command，我們可以用merge sort去數，這只需要O(N log N)的時間。具體方法請自己想想，或是上網search。
總時間是O(MN log N)。
注意︰之前test data是錯誤的，我測試sample solution之後肯定了該錯誤，現在test data已經更正。建議WA的同學可試試這個case:
5 3 9 9 9 9 9 4 2 1
正確答案是0，而sample solution出的是14。
訂閱：
文章 (Atom)