這是一條經典題，由往年的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吧，否則會很蝕底的！
2011年3月20日星期日
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年3月3日星期四
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了一次......
題目大意︰一個最多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了一次......
訂閱：
文章 (Atom)