2015年5月3日 星期日

New Platform & New Tutorial Material!! SPOJ + T-414-ÁFLV + 短期方向

這篇之後就剩下Google Code Jam 1B的記錄了..那真是慘痛的經驗...經一事長一智吧...
下篇再詳說了

這篇短篇只是把一些散亂的東東集中起來記一下~

SPOJ

首先是一個新發現的Programming Contest 平台~
很漂亮很boostrap的, 我真的覺得很不錯, 叫 Sphere Online Judge (SPOJ)
平台漂亮, 提交容易, 題目也很新很多
不過還是近於POJ 那種題目庫向的, 不太多contest向
contest還是CF / TC 那面較好吧~ :)
這個平台最強大的地方, 是有一個(不知道是否官方) 的 sample case tester
可以自己打input 看看官方答案的output是什麼這樣子
然後還有一個random input generator, 可以按要求random給出數據!
這2樣東西加起來要找counter example / test case就易很多了...
我也是用這兩件事才能AC下面所說的一題...

得知這個平台是從在公司用Ideone.com 打C++時右邊一些廣告發現的,
開頭以為是一些"野平台", 沒太大注意

後來偶然下, 為了解決一條在Stack Overflow的題目 (那題目就是問SPOJ的一條題目)
我就跑去玩了~ 話說在Stack Overflow答題目真的是一個學習/試試自己的好方法
快點有1000分就好了

What is wrong with this solution while solving JUICE on SPOJ?

在我威迫利誘之下, 他還是要Accept我的答案...哈哈! (誰叫他想要看AC的Code, 就要付出啊...)

話說這一題也很有學習的價值, 是一條 O(N^2) 的DP...
題目跟答案直接去看Stack Overflow 的Post就可以了

我再次覺得DP真的很彈性, 而且只要concept正確的話, 在題目的context 下
可以special handle很多東西 (甚至需要你這樣做) 才能AC...

這題來說就是要把同一個Starting Time 卻不是最後的segment 的state強制設定到負無限
其實只要有方法不使用它們update 更大的state就好了, 這只是其中一個方法
要找出這個問題, 我就是利用了 SPOJ Toolkit 這個強大的工具...這也令我更喜歡這個平台

然後針對這類interval graph的題目...其實我也很混亂的說
sort by start time還是end time, 還是sort by segment length...我印象中好像每一題都不同...
看來沒有什麼一定的rule 吧?

還有就是由於之前 (in progress)在重溫 CSC2110的notes
記得interval graph是 graph coloring problem 的其中一種特例, 是有解的
開頭以為是問那個方法, 還跑去重溫了...結果卻不是那回事
但Interval Graph還是一種很特別的東東
立志的notes也提出了一種叫 "Maximum Degree Ordering" 的theory
說了一種greedy找 minimum coloring on interval graph的方法
這種思路是絕對要學習的 (由於是特例, 直接記下也可以, 其實我還是更偏向這種學習方法)

所以結語是:  SPOJ, 好平台, 不用嗎?


T-414-ÁFLV Programming Contest Course

剛剛在某CF comment中看到有人介紹的一個好物...
不知道是什麼人寫的Course, 裡面還很正式的有評分, 功課等等
很好很強大.. 

暫時看了一下outline 和introduction, 好像很可靠的樣子
盡快學習一下好了~

這時也想了一下放在心中很久的疑慮:
其實material真的不少, 要多少有多少
演算法筆記, 這個programming course, TC 上的Tutorial....等等
問題是各家有各家的心法, 大家不論code還是學習的方法也很不同
即使是同一個技巧 / algorithm也差很遠

以前的我是想找"最好"的一個去學習的, 但慢慢發現根本沒有"最好"這回事
只有"最適合"自己的一套, 例如我很快就會說的 (我記得的...) KMP
那個複雜度的解釋,演算法筆記那個解釋看了明白卻不太能記下
Google隨便找了另一份notes的解釋是另一個合理的思路, 明白易記

所以其實根本不用強求, 也不用硬要學習那一份material
反正就都看看, 不明白就再找同一個topic的其它material, 找到自己最能明白理解的就好
Code的方面則最好在明白了之後有自己一套習慣的寫法
這是現在自己最習慣易學習的模式了...怎麼以前都不懂這些道理



最後的最後, 由於近來真的忙死了...還是一樣一樣整理下事件的先後次序吧...短期的計劃是這樣吧:

  1. 先集中準備下星期的Google Code Jam 1C...誰叫我1B差幾名才能Advance...
  2. 1C完了之後, 把1B, 1C的題目能學能做的都先搞定
  3. 繼續重溫CSC2110的Notes, 還差最後幾課了不能放棄
  4. 學習+記下說了很久的String Searching Algorithms + Trie!
  5. 開始跟住 T-414-ÁFLV 的課程學習 (重中之重)
中間的其它比賽能不打的都先不打了, 不然學習不了也沒好處
把這些都做得七七八八再繼續看演算法筆記尋尋寶吧

還有之前一直玩的Maya 2015也要找時間繼續...真的忙死了 = =

沒有留言:

張貼留言