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(NK²)。可能有人會問，既然可以向後跳，為何可以用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上表現得好，不單要做題目，還要積極和認真參加比賽，得到實戰經驗，才可百戰百勝。

HKOJ 1136 - Advertisement

這是一條經典題，由往年的training中找回來的，至於原出處，我是不知道的。

我希望在此說的是如何得出algorithm，而不是algorithm本身。

不難想到，這是一個可以貪心解決的問題，但是如何貪心才是重點。我們可以嘗試用人腦思考，當我們遇到同樣問題時，如何解決呢？首先我們列出最早的時段(先不說如何定義最早)，我們知道一定要放一個廣吿進去。很明顯，不放在整數點是沒有好處的。只需考慮整數點，但想放得早，中間，還是遲？

若果這是最早的時段，當然不是放最早吧，放中間也似乎沒有甚麼好處，姑且放最後吧。這樣，我們的第一個solution出來了，由最早開始的時段開始考慮，每一個時段如果還沒有廣吿，便放一個廣吿在最後。

下一步是驗証。好像如果第一個考慮的時段T₁完全包住另一個時段T₂，即T₂的開始比T₁遲，且T₂的結束比T₁早，明明一個廣吿便可以，我們的solution卻用了兩個。

於是我們便想如何去改正，似乎有兩個方法，一是把廣吿放在一個時段的最後是錯的，二是考慮的次序有問題。

先說一，如果我們不應放在最後，那麼我們很難想到放中間的甚麼位置會較好，而且似這一條問題會變得很難，不是用greedy可以解決。想不到其他solution才再想吧。

再說二，用以上的反例去考慮，我們需要的是把T₂排得比T₁早，很自然，如果我們以結束時間來排，T₂是會比T₁早，再想想logic上對不對。因為早結束的時段也必須有一個廣吿，如果我們順結束時間來排，而每一個廣吿也會放在一個時段的最後，我們並不會漏放廣告，在考慮每一個時段時，也不須往回去考慮，在時間複雜度方面也是很理想的。

最後一個問題，也是最重要的，是這樣放是否最優？我們也不難說服自己，反正每一個時段都要放廣告，放最後只會惠及未來要考慮的時段，並不會使未來的時段更差，所以應該都是最優解。

總體來說，time complexity是O(N log N + N) = O(N log N)，N log N 是來自sorting，N則是再掃一次每一個時候，考慮應否放廣吿的決策。有的在judge TLE的同學是用了N²的sorting，快點記/學一個N log N的sorting吧，否則會很蝕底的！

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希望更多人參加，令氣氛更激烈。題目也會相對這次更難(因為有同學說今次太容易了)，而且會正式用到數個月以來學的東西了。

URAL 1252 - Sorting the Tombstones

連結 http://acm.timus.ru/problem.aspx?space=1&num=1252

題目大意︰一個最多130000個elements的array，利用類似shell sort的方法去sort，即是只可以對每隔K個位的element進行swapping。問K最大是多少。

很直觀，只需要比對sort好和未sort的array的index之差，再找它們的共同gcd便可。因為對於每個element，一定要去到和它相差X個位的位置，而每一個element也要附合這個條件，為要達到這個目的，必須找一個共同數K都被每一個X整除，而K便是答案。

唯一一個trick便是題目要求。這題目沒有說明sort要是ascending還是descending，被fake了一次......

給所有出題者(problem setter)

剛剛看到一個很好的link，是一班Google Code Jam的出題者所寫的。雖然有些原則未必適用於所有比賽，但希望大家也可以仔細的看看，這對出題的人幫助很大。

https://code.google.com/codejam/problem-preparation.html

特別推介數個部份︰

(1) The Problem Statement - Limits︰提到multiple case的limit是很重要的。

(2) Creating the Problem - Difficulty︰這對HKOI或是TFT的setter尤其重要，很多時錯誤估計難度會令到比賽結果不具代表性，簡單來說，是「拉唔到curve」。

TC Marathon Match 簡介

想來想去，不知應該寫甚麼，自己又懶，不做很多題目，今天忽發奇想，原來可以寫寫之前在TC打的Marathon，不但有很多經歷，好像中文的blog也甚少提及這個範疇。今次我會簡介Marathon是甚麼。

Marathon是一個類似OI入面open test data的問題一樣，沒有已知最好的答案，或是最優答案是一些指數級難度的問題。長度通常是兩個星期，有時也會是一個星期至一個月不等。提交的是一個program而已，會經過數百個test case(通常是random地循題目列明的方法generate出來的)，再以題目訂明的方法計分，最後最高分的參加者勝出。

基本的program結構跟平時SRM的一樣，但Marathon提供更多測試的機會，可以大致分為四種︰
(1) 自己的offline testing︰和SRM或平時OI一樣，可以自己run自己的program，然後看看自己的表現。不同的是，通常Marathon提供一個Visualizer，可以用它來generate不同的random test case，大部份更可以有GUI的版面，把program的output化成一些動畫，迅速看到要改善的地方。我自己通常花大部份時間觀賞自己program的成果，的確是件很享受的事情。

(2) Example test︰和SRM一樣，Marathon會有一些seed(用來generate test data的random種子)來作一個簡單的測試。可以每15分鐘submit一次上去，出來的結果會是你program的每一個case的分數、運行時間、和一些debug的output之類。注意，這不是真的提交，不會用作真正的計分。

(3) Full submission︰這等同於SRM的submit，不過submit的時間不重要(即是越快submit不會越高分)。你的program會經過更多test case，不過你不能知道每個test case的表現，只知道最後得分的總和，以及相對其他參賽者的排名。

(4) System test︰顧名思義，是以你最後一個full submission作一個比較大型的testing。會run好多個case，而這個表現才是唯一會影響你最終排名的因素。

以上的僅是簡介，詳細可看Topcoder的規則。

之後我會說說我以往參賽的經驗，模式應該是這樣︰我會說說我的approach，然後再討論前幾名的approach，再重點提及一些重要的技巧，希望鼓勵大家參加，也給大家一些起步的建議。

Melodi Grand Prix 2011

每一年都有留意這個比賽，今年差點不記得！幸好也在final前留意，可以聽得完所有歌，我現在說說我比較喜歡的幾首歌吧。趁正式final之前，為這幾首歌打打氣。

(1) Helene Bøksle - Vardlokk

一首好magical的歌，本身我也不特別喜歡，但我聽完其他歌之後，再翻聽這首歌，便毫不猶豫的選了它。一首很典型的ESC歌，女歌手的實力很強。


Ah... ah...

No kalle kvinnene saman te sang
(Now the women are coming together to sing)
Dei ber meg sende mine gander
(They ask me to call for the spirits)
Krafta i kvadet eg lærde ein gang
(The power of the song I learned once)
Spinne tråd, lokke så ander gjer klang
(Spin a thread, entice the spirits to respond)

Frykte sangen vil fløyma min sans
(I fear that the song will flood my senses)
Kvie for makta i kvar tone
(I shy away from the power of each note)
Dei seie lokken kan danna ein krans
(They say the chant can form a wreath)
Der me to atter forsone te dans
(Where the two of us again can reconcile with dance)

Ah... ah...
Ah... ah...

Drøyme. Vinde deg inn
(Dreaming. Winding you in)
Tia fer sitt spinn
(The time gets its web)

Volva vente i innerste ring
(The sorceress is waiting in the innermost circle)
Krev at eg varde ho med gander
(Demanding me to protect the spirits)
Eg ska kvea og festa mitt sting
(I will sing and fasten my stiches)
Finna deg blant ander
(Find you among spirits)

Ah... ah...
Ah... ah...
Ah...


(2) Stella Mwangi - Haba Haba

很不像挪威的風格，但罕有地活力得來也不失節奏感，而且舞蹈也配合得非常好，人氣非常高，很有機會勝出，代表挪威參加在德國舉行的總決賽。

最後送上一首不是mgp的歌，但也很有機會參加總決賽的冰島參賽歌。

(3) Yohanna - Nótt

Yohanna是2009年代表冰島出賽的歌手，她憑Is it true?奪得總決賽的第二位，一個非常了不起的成績。今年她憑這首冰島文的歌再度參賽，希望也取得好成績吧。

Ef ég aðeins gæti sagt 
að það er sem í hjarta brennur 
ef ég ætti svar.
Allt mitt líf er skipulagt og það framhjá mér rennur. 
Horfið allt sem var. 
Ef ég gæti séð, hvað svo bíður mín.

Þú ert sú minning, 
sem lýsir myrkur hugans 
ég man þig oft um nætur. 
Nóttin er svo dimm. 
Þú ert sú minning 

Oft ég hef mig að því spurt
að það er sem í mig togar 
horfi í sólarátt...
Lífið bara hreif mig burt 
Hjartað slær og sál mín logar 
samt ég veit svo fátt.

Þú ert sú minning,
sem lýsir myrkur hugans
ég man þig oft um nætur.
Nóttin er svo dimm. 

Ef aðeins ég vissi hvað verður án þín
ég man þessa nótt sem var mín og þín
hvað bíður mín? 
Þú ert minning, sem lýsir myrkur hugans
ég sé þig oft um nætur. 
Og nóttin er svo dimm. 

Þú ert sú minning,
sem lýsir myrkur hugans 
ég sé þig oft um nætur. 
Svo margt sem minnir á.. 
Þú ert nóttin.