剛剛看到一個很好的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」。
2011年2月19日星期六
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，再重點提及一些重要的技巧，希望鼓勵大家參加，也給大家一些起步的建議。
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，再重點提及一些重要的技巧，希望鼓勵大家參加，也給大家一些起步的建議。
2011年2月12日星期六
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.
(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.
2011年2月9日星期三
2011年2月8日星期二
關於memset
這個題目好像重覆又重覆，但我最近發現了一些有趣的東西，想和大家分享一下，順便當作温故知新吧。(已是給一些從未用過memset的作一個簡單的introduction)
利用memset，這段code便可簡化成︰
如果很多array要initialize，memset便使整段code更為簡潔，更加易明了。
可是，很多coder非常容易誤用memset，好像下面這段code︰
該如何簡化呢？
很可惜，這是錯的。整個a[]會變成16843009，絶對不是你想要的東西吧。應該如何寫呢？
答案是memset並不可以這樣做。要知道原因，請繼續看下去 :-P
memset的原意是對character的array做整體的改變，例子可看http://www.cplusplus.com/reference/clibrary/cstring/memset/
而memset的好處是這樣做會比用for loop逐個改快。
一個character佔1 byte，所以memset幫string裏面每一個character的1 byte都改變，成為你想要assign的character。可是一個integer是4 byte，如果我們只指定一個byte的值給它，它唯有(強行)改變它的用法，變成一個重覆4次的byte。
從以上例子可看到，(0)10=(00000000)2，而(1)10=(00000001)2，因此memset的結果分別是(00000000 00000000 00000000 00000000)2和(00000001 00000001 00000001 00000001)2，在十進制分別為0和16843009。
這樣看來，memset的用處不大，但實際program的時候，我至少找到4個用處(4個常用的value)。
(1)
(2)
(3)
(4)
原理和上面講述的一模一樣。但更強的是，連long long都可以用同樣數值來initialize一個array，應用範圍更廣。
所以，以後要做shortest path，做BFS，做其他要initialize的program時，memset將會是你省時，省code length的好幫手。
int a[10]; for (int i=0; i<10; i++) a[i]=0;
利用memset，這段code便可簡化成︰
#include<cstring> int a[10]; memset(a,0,sizeof(a));
如果很多array要initialize，memset便使整段code更為簡潔，更加易明了。
可是，很多coder非常容易誤用memset，好像下面這段code︰
int a[10]; for (int i=0; i<10; i++) a[i]=1;
該如何簡化呢？
int a[10]; memset(a,1,sizeof(a));
很可惜，這是錯的。整個a[]會變成16843009，絶對不是你想要的東西吧。應該如何寫呢？
答案是memset並不可以這樣做。要知道原因，請繼續看下去 :-P
memset的原意是對character的array做整體的改變，例子可看http://www.cplusplus.com/reference/clibrary/cstring/memset/
而memset的好處是這樣做會比用for loop逐個改快。
一個character佔1 byte，所以memset幫string裏面每一個character的1 byte都改變，成為你想要assign的character。可是一個integer是4 byte，如果我們只指定一個byte的值給它，它唯有(強行)改變它的用法，變成一個重覆4次的byte。
從以上例子可看到，(0)10=(00000000)2，而(1)10=(00000001)2，因此memset的結果分別是(00000000 00000000 00000000 00000000)2和(00000001 00000001 00000001 00000001)2，在十進制分別為0和16843009。
這樣看來，memset的用處不大，但實際program的時候，我至少找到4個用處(4個常用的value)。
(1)
int a[10]; memset(a,0,sizeof(a));得出的值是0。
(2)
int a[10]; memset(a,-1,sizeof(a));得出的值是-1。
(3)
int a[10]; memset(a,127,sizeof(a));得出的值是大約是+infinity。
(4)
int a[10]; memset(a,128,sizeof(a));得出的值是大約是-infinity。
原理和上面講述的一模一樣。但更強的是，連long long都可以用同樣數值來initialize一個array，應用範圍更廣。
所以，以後要做shortest path，做BFS，做其他要initialize的program時，memset將會是你省時，省code length的好幫手。
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。
URAL 1519 - Formula 1
連結 http://acm.timus.ru/problem.aspx?space=1&num=1519
這條儘管是模板題，但我也卡了很久。
每一個狀態的表示為三進制的列，例如一個m為5的grid的表示方法為(012012)3，當中0是無插頭，1是左插頭，2是右插頭，詳見cdq的論文。
因m最大是12，即是一個state的memory可以是313這樣大，即是1594323。如果每一次都要clear memory，或者開個12x12x1594323的array，這都是不可能的，因此我用了hash的方法。而因為state的用量不高，因此可以用open addressing。我個人用的hash size是32767。
轉換方法分為三類(假設現在在第1格)︰
1. 開新插頭，例︰
0000000 -> 0120000
2. 延伸插頭，例︰
0100200 -> 0100200 或 0010200
3. 合併插頭，例︰
Case (a): 0110220 -> 0000120 (1和2是對等的)
Case (b): 1210020 -> 1000020
Case (c): 0120000 -> 0000000 (只會在最後的空格發生)
我用了好一點時間code好了以上的case，卻得到WA的回覆了。放棄了好一陣子，直至今天才去認真debug，結果錯在case 3a︰
由0111222(第一格)，我的錯誤program將它轉成0001122，正確應是0001212。完全miss了論文中12對應的特性。最後終於AC了。
這條儘管是模板題，但我也卡了很久。
每一個狀態的表示為三進制的列，例如一個m為5的grid的表示方法為(012012)3，當中0是無插頭，1是左插頭，2是右插頭，詳見cdq的論文。
因m最大是12，即是一個state的memory可以是313這樣大，即是1594323。如果每一次都要clear memory，或者開個12x12x1594323的array，這都是不可能的，因此我用了hash的方法。而因為state的用量不高，因此可以用open addressing。我個人用的hash size是32767。
轉換方法分為三類(假設現在在第1格)︰
0123456 0123456 _____ --> ____ _| __|
1. 開新插頭，例︰
0000000 -> 0120000
2. 延伸插頭，例︰
0100200 -> 0100200 或 0010200
3. 合併插頭，例︰
Case (a): 0110220 -> 0000120 (1和2是對等的)
Case (b): 1210020 -> 1000020
Case (c): 0120000 -> 0000000 (只會在最後的空格發生)
我用了好一點時間code好了以上的case，卻得到WA的回覆了。放棄了好一陣子，直至今天才去認真debug，結果錯在case 3a︰
由0111222(第一格)，我的錯誤program將它轉成0001122，正確應是0001212。完全miss了論文中12對應的特性。最後終於AC了。
訂閱：
文章 (Atom)