RSS Reader

HKOJ 1136 - Advertisement

targetforfuture | March 20, 2011, 9:31 a.m. | Original

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

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

不難想到，這是一個可以貪心解決的問題，但是如何貪心才是重點。我們可以嘗試用人腦思考，當我們遇到

HKOI 2011 Mini Competition 1

targetforfuture | March 5, 2011, 9:21 a.m. | Original

哈哈，今次的mini-comp其實都是我選題目的，基本上除了一題是我自己出之外，其他都是參考一些過往的比賽的，我不會全部公開那些題目的來源，以免以後不能再用這些source，但是大家做多一些題目，總會有機會遇到類似的，有利

URAL 1252 - Sorting the Tombstones

targetforfuture | March 3, 2011, 8:31 a.m. | Original

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

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

很直觀，只需要比對sort好和未sort的array的

給所有出題者(problem setter)

targetforfuture | Feb. 19, 2011, 1:59 a.m. | Original

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

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

特別推介數個部份︰

(1) The Problem Statement - Limits

TC Marathon Match 簡介

targetforfuture | Feb. 18, 2011, 12:23 p.m. | Original

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

Marathon是一個類似OI入面open test data的問題一樣，沒

Melodi Grand Prix 2011

targetforfuture | Feb. 11, 2011, 3:42 p.m. | Original

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

(1) Helene Bøksle - Vardlokk

一首好magical的歌，本身我也不特別喜歡，但我聽完

看日出

targetforfuture | Feb. 8, 2011, 5:58 p.m. | Original

不知為何自己會這麼早還是醒來，在文林的清新空氣下，清晨來得特別美麗。鳥兒早已在天空漸光時叫，而巴士也在眾人還在睡夢中行駛了。

我很喜歡與別人單對單談天，總可以說到一些更深入的話題。用一個晚上換取的朋友，

HKOJ 1109 - A sort of Shell

targetforfuture | Feb. 7, 2011, 8:49 a.m. | Original

題目大意︰大約是每一個command以最少的swapping做partial的bubble sort，問最後做完所有command之後做了多少次swapping。

由於array的長度達100,000，因此simulation是不夠快的 Complexity: O(N ² )

Observation 1:
其實已在題目大意標明，這是一個partial的bubble sort。

Observation 2:
每一個bubble