Codeforces #90

d1 & d2 一齊打既比賽。
最後因為條B official soln 出錯變成unrated...如果rated應該會升的..

只做了A,B,C

不過條B 如大部分人一樣都係比佢陰左..題目本身出得很好, 個trick好反直感。

A:
頹, simulation

B:
其實題目就係要你搵min / max of avg of given既cards, 同埋剩番落黎足夠theorems可以組成一張card (視乎min定max, 總之sort左佢一路pick就係). 陰位係: 由於題目講明卡可以重複出現, 但一題題目只會出現係一張卡上面, total係有k 張卡的, 姐係話如果你已經知道哂所有 k 張卡, 而剩番既theorems仲可以組多一張卡, 咁答案都仍然係given 個k 張卡入面搵...
唉

C:
DP...雖然人地話好standard, 但我覺得唔算太容易..所以比賽入面過到真係幾開心。
思考過程有兩個observation, 第一, sort by complexity 先再做dp, 不過做dp時仍然要check到transition時唔可以由一樣complexity既update (因為要strictly increasing)  ; 第二,  我諗好明顯, bi - ai <=100   而ai 同 bi <=10^16!!  記得ZQ講過呢d好明顯就要諗下點利用。 不過先將呢個問題放係一邊, 直接諗下state 同transition先~

state:  dp( X, i , n ) :=  max total # of homework from 0 to i lessons,  pick up n lessons, and the i-th lesson have X+a[i] homework

transition:
dp(X, i, n) =
max ( dp (X+a[i] - k - a[j],  j , n -1),    if( (X+a[i])%k==0) { dp((X+a[i])/k - a[j], j, n-1} )
for all j < i

奇妙就係度..因為bi - ai <=100 , 所以我用offset X ,  0<=X<=100 黎代表第 i 個lesson既homework 數都係得既! 咁樣table size就係 100 * 50 * 50 , 非常合理既數字, 亦都大大提升左我對呢個做法既信心

當然仲有好多野要handle.. X +a[i] <= b[i] 啦.. complexity 要strictly increasing 啦..
call答案時 試哂所有X 同 i (因為可以係簡頭個d 已唔簡後面個d, 如果直接將 i 變做m 會錯)
tX = X in argmax (dp (X , i, n) )
tI = i in argmax( dp(X , i, n) )

最後recursion trace條path出黎就ko~

ps: 記錄條path 都幾麻煩...由於無咩時間加唔識, 夾硬用pair < int, pair<int, int> > naive記住parent (o:以後可以試下用map<node , id> ... by gary