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吧，否則會很蝕底的！

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了一次......

HKOJ 1109 - A sort of Shell

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

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

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。