Paper的事... 也由不得我擔心太多
先前 Conference paper deadline 跟 ICPC World Finals 撞期了
後來 World Finals 又因為埃及政治事件需要延期...
在我來看，算是好事
最後相當多比賽
Facebook Hackercup
Bitwise
還有一個沒有參與的 Mathxxxxxx
不過... 嘛... 技術問題相當多...
先有 submission system error
後來又有出錯題目...
甚至沒有引用的抄考題目...
才發覺, 原來一個搞得正正常常的比賽是相當難得
(然後我又覺得，以往大家搞的 TFT 或者是朋友最近辦的數學馬拉松
(從某方面看，相比之下，比很多大型比賽更加成功)
最近參與比賽不太順利...
SRM 跌下藍色區域後第一戰
250做挫了... 單靠雖然 AC 卻很遲提交的 500 落得 rating 繼續下跌的下場...
Facebook Hackercup 亦落得失失下場...
有關 Facebook Hackercup Round 2...
題C，想出相當久，才得出 handle double-count 的算法
基於 observation 寫出的 Inclusion-Exclusion：
只統計 square-free factor
跟 Waihon 及 超超寫的... 三個人的版本也不太像樣...
後來再跟 超超請教
才發覺我當天寫的 dfs...
冥冥中就是在計算 Möbius function - -
原來三者的算法互相相通...
可在一個細節地方：有關處理 a,b,c,d 重計方面做差了...
最後沒能通過
我問超超在甚麼時候學會這些東西...
他回答：「果時樓天成教架囉，你都喺度架？」
『Phi function果次？』
「係呀，其實佢講個方法同樣應用緊 Möbius inversion」
orz
所以...
剛剛聽超超講解
又 revisit 了 Möbius inversion formula, Phi function, Multiplicative function 等等概念...
最重要的，是其中一個應用：Inclusion-Exclusion Principle
(e.g., Hackercup Round 2 - Problem C)
嗯... 現在似乎更加明白了...
重要公式如下：
The classic version states that if g(n) and f(n) are arithmetic functions satisfying
待以後有時間考慮寫一篇 entry ...
要繼續工作了
辦大型比賽的難度一定會高很多
回覆刪除ps 我都抽時間 revisit 一下 Möbius function 先
SERVER等等問題一定煩好多
回覆刪除但問題係, 有好多比賽連啲問題/答案都set錯...
推介：www.math.byu.edu/~forcader/11MobInc.pdf
我覺得個 PDF 講得幾清楚
Partial Sum→Mobius Function (Number Theory)
Partial Sum→Inclusion/Exclusion
順貼:
回覆刪除原來 ∑gcd(i, N) 本身是積性函數...
所以不需要用 質因數分解去求解
證明大綱：
F[MN]=∑gcd(i, MN) (1)
=∑∑gcd(i*N+j*M, M*N) (2)
=∑∑gcd(i, M)× gcd(j,N) (3)
=∑gcd(i, M)*∑gcd(j, N) (4)
=F[M]*F[N]
詳參：
http://hi.baidu.com/5l2_/blog/item/236d8c1f59e7ebc6a786693b.html