如果係真相
http://codeforces.com/profile/dwelling
2013年9月20日 星期五
Codeforces Round #200 (Div. 2)
終於今日做埋條E...近日都苦腦於CF同Codechef之間, 感想係Codechef 個judge難過好多, d題目都奇怪好多.. 做完數題CF/ Codechef頹題, 發現有好幾題都係Segment tree, 有題BIT, 原來我d data structure差到咁 sosad...繼續努力
近日做d題目太散亂...所以都係寫左CF #200先...難得又係幾易既一round, 今次題目都editorial我都幾鐘意, 用科學做background, 而editorial 作者都比左好多bonus既reference參考, 有興趣再睇
今場最感受深刻既係..真係要睇清楚題目/題意 (O:
TL;DR
題目: http://codeforces.com/contest/344/problems
A:
頹題, 秒殺之
B:
頹題, 基本solve 一個equation system: 3條式, 3個variable
C:
問最少用幾多個R=1既resistors合成一個指定數值既Resistors, 真係嚇一跳。
呢個係第一個教訓...無睇清楚definition of element...
其實佢只可以一個一個咁加..所以由唔識做變成唔太難做...
in series既話就係+1 + 1 咁, in parallel既話 其實似gcd...
eg: 如果想合一個R = 11/3 既, 先將佢變番一個真分數: 3+2/3
跟住2/3 其實係可以由 (3-2)/2 = 1/2 同 1 parallel合出黎...呢步就似gcd了 (不過呢度用減法)
所以algorithm 就係until 分子或者分母 = 1
for a/b, 如果係假分數, 先將佢變番真分數, 然後recursion call (b-a,a)
performance 我估一定好快, 因為似gcd()... editorial 話係O(log(max(a,b)) 唔識prove
between 呢題既editorial 好值得睇
D:
另一題好糾結既題目...原因又係自己唔用筆諗清楚...題意就係想知2條線 total 4個endpoint fix死左, 但中間就互相交叉咁, 可唔可以分番開做2條parallel既線 (唔打結)
其實好快已經會知係似 stack check括號合法 之類既做法..唯一飲恨既係..無諗清楚(畫清楚)其實同一個sign 只可以係連續2個就可以解開, 如果連續 3個就未必得..
總之就係第一感以為連續 n 個同樣sign既可以一次過delete, 結果諗左大半日都諗唔到點樣用stack做到...後黎發現其實真係同check括號一樣, 只可以連續2個 2個咁先可以delete...所以用stack做就得了...
點解可以做到problem D = =
E:
題意係, given n個pointers, m 個track要read, 每一個pointer經過既地方就叫read左, 一步之間, n個pointers可以向左走向右走, 或者唔郁, 每個pointers互相唔影響大家移動 (可overlap), 問最少幾多步先可以read哂m 個track. pointers, tracks position input係ascending order.
嗯...血的教訓, 雖然我唔認為呢題可以做到problem E...我覺得似係problem C 咁上下..
睇完題目一定係bsearch.. 但 n log n做好似都勉強左d, 發現 n log ^2 n 好似都過到, 咁就用左n log ^2 n做... 錯左3棍!!! 其中2棍都係因為bsearch個boundary set 得太細...嗚啊..
基本上思路好簡單, bsearch 答案步數L, 跟住係greedy, 由最左邊既pointer 開始睇下用L步最盡可以COVER到最右既位, 如此類推, 最後睇下用n 個pointer 可唔可以cover哂最右邊既track
呢一步可以用n log m 做:
initial R = 0; // R = currently cover到最右既position
for 每一個pointer, 先搵下佢最左要cover既track係邊 (O(n))
lower_bound(p,p+m, R+1) (O(lg m) )
跟住只有兩個case:
track 係pointer既右邊: 咁好直接, R = pointer + L 咁遠
track係pointer既左邊: 呢個case比較tricky..錯多棍就係呢個位..
首先你要去左行, 去到track位, 再番轉頭番到原位, 呢度行左2x 步 (x = track同pointer距離)
跟住可以再去右行 L - 2x 步 所以 R = pointer + L - 2x
問題係..其實有機會係先向右行再番轉頭 而令到R再大d...!!亦即 R = pointer + (L-x)/2 <---先向右行再番轉頭cover番係左邊既track
2個take maximum 就係最遠既R
就是咁, total = O(n lg^2 m)
but..睇左editorial, 基本方法一樣, 但唔知點解作者話係n log m...anyway~
PS: 係Codechef都諗緊一題, 睇落好似題E...但完全唔可以用相同做法..因為Codechef個題係online, d track position仲可以改, 仲諗緊點做, fuck
近日做d題目太散亂...所以都係寫左CF #200先...難得又係幾易既一round, 今次題目都editorial我都幾鐘意, 用科學做background, 而editorial 作者都比左好多bonus既reference參考, 有興趣再睇
今場最感受深刻既係..真係要睇清楚題目/題意 (O:
TL;DR
題目: http://codeforces.com/contest/344/problems
A:
頹題, 秒殺之
B:
頹題, 基本solve 一個equation system: 3條式, 3個variable
int x = a+b-c, y = b+c-a, z = a+c-b; if(x < 0 || y < 0 || z < 0 || x%2 || y%2 || z%2) printf("Impossible\n"); else printf("%d %d %d\n", x>>1, y>>1, z>>1);
C:
問最少用幾多個R=1既resistors合成一個指定數值既Resistors, 真係嚇一跳。
呢個係第一個教訓...無睇清楚definition of element...
其實佢只可以一個一個咁加..所以由唔識做變成唔太難做...
in series既話就係+1 + 1 咁, in parallel既話 其實似gcd...
eg: 如果想合一個R = 11/3 既, 先將佢變番一個真分數: 3+2/3
跟住2/3 其實係可以由 (3-2)/2 = 1/2 同 1 parallel合出黎...呢步就似gcd了 (不過呢度用減法)
所以algorithm 就係until 分子或者分母 = 1
for a/b, 如果係假分數, 先將佢變番真分數, 然後recursion call (b-a,a)
performance 我估一定好快, 因為似gcd()... editorial 話係O(log(max(a,b)) 唔識prove
between 呢題既editorial 好值得睇
LL gcd(LL a, LL b){ if(a == 1) return b; if(b == 1) return a; if(a > b) return a/b + gcd(a%b, b); return gcd(b-a, a)+1; }
D:
另一題好糾結既題目...原因又係自己唔用筆諗清楚...題意就係想知2條線 total 4個endpoint fix死左, 但中間就互相交叉咁, 可唔可以分番開做2條parallel既線 (唔打結)
其實好快已經會知係似 stack check括號合法 之類既做法..唯一飲恨既係..無諗清楚(畫清楚)其實同一個sign 只可以係連續2個就可以解開, 如果連續 3個就未必得..
總之就係第一感以為連續 n 個同樣sign既可以一次過delete, 結果諗左大半日都諗唔到點樣用stack做到...後黎發現其實真係同check括號一樣, 只可以連續2個 2個咁先可以delete...所以用stack做就得了...
點解可以做到problem D = =
E:
題意係, given n個pointers, m 個track要read, 每一個pointer經過既地方就叫read左, 一步之間, n個pointers可以向左走向右走, 或者唔郁, 每個pointers互相唔影響大家移動 (可overlap), 問最少幾多步先可以read哂m 個track. pointers, tracks position input係ascending order.
嗯...血的教訓, 雖然我唔認為呢題可以做到problem E...我覺得似係problem C 咁上下..
睇完題目一定係bsearch.. 但 n log n做好似都勉強左d, 發現 n log ^2 n 好似都過到, 咁就用左n log ^2 n做... 錯左3棍!!! 其中2棍都係因為bsearch個boundary set 得太細...嗚啊..
基本上思路好簡單, bsearch 答案步數L, 跟住係greedy, 由最左邊既pointer 開始睇下用L步最盡可以COVER到最右既位, 如此類推, 最後睇下用n 個pointer 可唔可以cover哂最右邊既track
呢一步可以用n log m 做:
initial R = 0; // R = currently cover到最右既position
for 每一個pointer, 先搵下佢最左要cover既track係邊 (O(n))
lower_bound(p,p+m, R+1) (O(lg m) )
跟住只有兩個case:
track 係pointer既右邊: 咁好直接, R = pointer + L 咁遠
track係pointer既左邊: 呢個case比較tricky..錯多棍就係呢個位..
首先你要去左行, 去到track位, 再番轉頭番到原位, 呢度行左2x 步 (x = track同pointer距離)
跟住可以再去右行 L - 2x 步 所以 R = pointer + L - 2x
問題係..其實有機會係先向右行再番轉頭 而令到R再大d...!!亦即 R = pointer + (L-x)/2 <---先向右行再番轉頭cover番係左邊既track
2個take maximum 就係最遠既R
就是咁, total = O(n lg^2 m)
but..睇左editorial, 基本方法一樣, 但唔知點解作者話係n log m...anyway~
LL l = 0, r = 2*10000000000LL;// diu, 錯左2棍 LL ans = r; while(l<=r){ LL L = l+((r-l)>>1), R = 0,s = 0; for(int i=0; i<n;i++){ int in = lower_bound(p,p+m, R+1) - p; if(in == m) {s = 1; break;} LL x=p[in]; if(x < h[i]) if(h[i]-x > L)break; else{ LL R1 = max(h[i], L-h[i]+2*x); LL R2 = max(h[i], (L+h[i]+x)>>1); R = max(R1,R2); } else R = h[i]+L; } if(s || R >= p[m-1]){ r = L-1; ans = min(ans, L);} else l = L+1; }
PS: 係Codechef都諗緊一題, 睇落好似題E...但完全唔可以用相同做法..因為Codechef個題係online, d track position仲可以改, 仲諗緊點做, fuck
2013年9月5日 星期四
Codeforces Round #198 (Div. 2)
做題目真係食白粉一樣, 原本以為有排都唔會再掂, 結果都係是旦做左d
好一排無上CF, 真係愈改愈user friendly (定我以前唔識用)
唔知好運定點, 是旦抽一set d2, 最後竟然5題都做到
而且今次code前code後都叫做有proof到個方法幾肯定, 說服到自己先code
亦都係第一次(真係第一次)睇editorial 無TLDR, 由頭睇哂佢, 最開心係basically writer 個proof
同自己諗既基本一樣...
不過可能因為公司無g++ 既關係, 全部都係notepad++ dup完係CF個custom test度試 (o:
準確度大大下降 (賴地硬ing)
between, 閑時睇番之前寫開d post 每次都會心諗: 原來我做過d咁既野 :o
TL;DR
題目: http://codeforces.com/contest/340/problems
A (Ad-Hoc, Math):
Given x,y,a,b; a,b <= 2*10^9, 問有幾多 lcm(x,y)既倍數係between [a,b]
Solution:
let L = lcm(x,y) = xy/gcd(x,y)
ans = # of k s.t. a/L <= k <= b/L
B (Geom):
驚奇地出現係第2題既Basic Geom..Given 300點, 問pick 4點組成既四邊形最大可能面積
Solution:
思路是如何形成的: 數據SIZE = 300, 即order 大約為 n^3 ?
好自然會諗到計三角形...
設 d[i][j] := 第i點 經第k點 到第j點 此三角形 (i,k,j) where i,j,k distinct 最大既三角形面積
答案就係 for 所有 pair (i,j) , max (d[i][j] + d[j][i])
正確性是肯定的, 首先因題目講明唔會3點同線, d[][] 一定唔會出0 area
但眾所尻知area有正負, 而當三角形(i,k,j) 係正面積時, 三角形(j,k,i) 會係同數值既負面積
(cross product特性)
所以當有最少4點時(題目講明), d[i][j] != d[j][i] for all i,j
其次max(d[i][j]+ d[j][i]) 一定係最大可能既4邊形面積, 好易用contradiction proof到
(成個方法唔使諗self-intersect case, 因為一定唔intersect好過intersect..太self explain了)
比較會中伏位係initialization!! 雖然唔會self-intersect (你唔會簡), 但concave係可以的, 而concave 4邊形既意思就即係話either 是旦一邊既三角形係負面積...亦即係話d[][] 唔可以initialize 做 0, 因為可能最optimal既三角形面積的確係 < 0 ...
C (Combinatorics):
是咁的, 呢條都算係幾有成功感既一題...因為我覺得(FF) 以前我應該未必做到...
Given n (<=10^5) 個distinct數, 每個數代表距離O既位置, 依家你係O, 類似TSP咁由O出發, 每個點都經過一次, 去到最後一點就停
咁好明顯就有好多種path (題目用route), 2個點自己既distance就係 absolute difference, 問average 所有possible path 你行既總distances, 用不可約分數表示
Solution:
是咁的, 首先呢d題目, 基本上分母都係好頹就諗到, 呢題都唔例外
分母 = # total possible path = n!
其實亦即所有permutations
重點當然係分子, 分子又可分開兩parts
Let input n個數 --> D[]
part I:
首先由O去第一個點既總distance
當我fix死第一個點為a, 則path如下
a???????....?
我後面共有(n-1)! 可能性, 而呢group path既distance = a
而a 其實可以係N個數是旦一個 (pick 邊個做第一點都得)
所以總和係 (n-1)! * summation( D[] )
part II:
for 任意permutation "a???????..??" , 依家你就站係a,
由a 去到最後一點既distance 為該permutation既總distance
而我地想要既係所有permutation既總distance 總和 (1999)
重點來了, 當我尻pick 2點, a & b, 必需相鄰既permutations 總共有多少條?
????ab?????..?
?ba?????....???
ab???????????
....
簡單地說, 就是n個位fix死2個位, 其它(n-2)個位隨意, 即 (n-2)!
但因為我想一同考慮 ab互換的permutations (如上 ba 鄰接的都算)
所以有 2*(n-2)! 條 permutations, 是ab (或ba) 放在頭2個位置
eg:
ab????...?????
ba????...?????
接著ab (或者ba) 在一條permutation可以放在(n-1)個位置上
所以總共是有(n-1)*2(n-2)! = 2(n-1)!條 , 而每條提供了 |a-b|的distance
數法大致就是這樣了, 接著都是為了方便code已講的
首先可以sort (D), 確保for i <j, D[i] < D[j], 跟住上面part II 則可便為
2(n-1)! *(D[j] - D[i] ) for all i <j
小總結一下, 分子是 part I + part II = (n-1)! summation(D[]) + 2(n-1)!(D[j]-D[i]) for all i < j
把(n-1)! 跟分母的 n! 約掉, 分母直接剩n , 分子則變為簡單的 summation(D[]) + 2(D[j]-D[i])
煩人的是如果直接計算D[j] - D[i] 還是需要O(n^2)...會超時
於是我煩悶的在紙上亂寫, 發現寫了不錯的東西:
D[] = {1,3,5,7}
7-5 +
7-3 +5-3
7-1 +5-1 +3-1 = ?
這個問題的答案就是D[j] - D[i] for all i < j 了...
咦...打直看一下, 打橫看一下, 不是很簡單的...
(3*7 + 2*5 + 1*3) - (3*1 - 2*3 - 1*5)
Generalize一下: ((n-1)*D[n] + (n-2)*D[n-1]+...+D[2]) - ((n-1)*D[1] - (n-2)*D[2] - ... D[n-1])
啊...原來一個FOR LOOP就OK了..
sum是part I, up 是part II ...
最後print時記得分子分母再除以gcd() 一下...以免分子分母可約...
AC了 嗚啊
TL;DR : 答案 = (sum + up) / n , 記得約簡
D (DP, Bsearch):
很有趣的題目名, 很有趣的題目, 很有趣的題意
Given n (<10^5) 個數, 做bubble sort, 不過每swap 一個數, 會將該兩個數之間加條edge
所以sort好之後, 其實順路build左一個graph G 出黎, 求G上max independent set
Solution:
呢題亦都好感動, 因為之後睇番editorial, 成個諗法基本一樣!
亦學到好多以前無學到 (學唔識)既野...
先講結論: 即求input既 Longest Increasing Subsequence
Observation: for 序列中任意一個數 x, 在完成整個sorting後, 佢一定會同原本排在之後, 而且比自己小的所有數y 有edge
掉轉黎講: 亦即最後2點 之間無edge代表最初序列中該2個數次序正常 (x 比y小, 而且排在y前面)
而由於independent set 既definition為, set 中任意2點皆無edge,
亦即得出任意2個數 在最開頭已經排好次序了
而求最大的independent set, 不就是求最多(最長)在最開頭已經排好次序的子序列嗎?
(上面呢段廢話亦即 editorial 既lemma1 + lemma2)
重點來了, 數據關係, 肯定要用nlogn算法了...問題在於其實由頭到尾我都無好好了解過
LIS nlogn 算法...借此機會於是做左d功課...發現的確很聰明又很簡單..在此記一記廢事又要google過...
有短的寫法 , 也有長的寫法
短的寫法只能找出LIS的長度, 並不能找出正確的LIS...長的寫法則2種都做到
此題由於只求長度, 我用了短的寫法, 大約是咁的:
用一個data structure, array也好, stack也好, 總之要令裡面永遠都是sort好的,
而最後期望該data structure的size 就是LIS的長度, 至於裡面裝的是不是真的LIS我們不管
每一個input a, 如果a 比裡面所有數還大, 直接放入去, 原因: GREEDY
如果不是最大的, 則在裡面找一個剛剛比a 大的, 用a 取代 該數
正確性很好理解的, 首先如果a 比裡面所有數都大, 自然是可以放進去了, LIS亦可以加大
而當a 比裡面某一些數小, 代表什麼呢?
1. 首先代表LIS 起碼等於此時data structure的size
2. 我把a 取代裡面的數 不會令size (此時的LIS)有變化, 但卻會使潛力大了
用{1,7,8,3,4} 做例子
首先structure會有 {1,7,8} ,此時LIS為3
當見到3, 會用3取代7, 變為{1,3,8} LIS同樣是3, 但潛力卻大了, 因為{1,3} 是去到此刻, 長度為2的IS中最優的, 你會發現{1,3,8} 其實是不存在的, 這裡面隱藏了一個巨大意思...
就是任何時候structure裡 index 為i 的數, 就是 長度為 i 的IS去到此刻最優的尾數
that is:
去到input = "3"為止,
{1,3,8} --> 1 是 長度為1 的IS中最小的尾數
3是長度為2的IS中最小的尾數
8是長度為3的IS中最小的尾數 (存在 {x,x,8} 這樣的一條IS, 而且沒有其它長度為3的IS尾數比8小)
之前說的較長 (可找出LIS)的寫法就是用了這種概念...詳細寫法擇日再寫...
這是何等的屈機呢...
言歸正傳, 短的寫法實作我是用<set>, 因為<set>的find, insert, 都是logn的
(提交前改了<multiset>, 主要是怕當有repeat input 會出事)
E (Combinatoics, DP):
終於到E了...不過先要利申...本身是不打算看題目的了, 因為一直都不會做到D/E...
所以做之前直接去看Editorial, 故意避開了E的題解, 但還是偷看到了inclusion-exclusion principle....而最後過到之後睇番原來原意是想用DP解的...現在還不明白如何用dp做, 反正我自己是用(第一次)inclusion-exclusion principle做
題意是咁的 given n (<2000) 個distinct既數, 當中有d 係unknown, 有d given (即fix死)
如
a[] = {-1, -1, 5, 3, -1}
5 跟 3 是fix死的, 而 1, 2 ,4 即是可以填在-1的位置上
問有多少種combination s.t. 填完之後, a[i] != i for all 1<=i<=n
Solution:
其實老實講我覺得題C難數過這題..(雖然呢題都卡左陣=.=)
如果直接apply inclusion-exclusion principle
答案就是這樣的:
S - ( #at least 一個位 a[i] = i - #最少兩個位 + #最少三個位 - .... +(-1)^(i+1) * # 最少n個位 )
where S = k! , k = # of -1
來看看最少一個位中伏的數目, 設k 是 # of -1
則除fix好的中伏位之外任意排 = (k-1)!
可以fix 的位置有 kC1 個
如此類推
最少兩個位的 有 kC2 * (k-2)!
...
問題便簡化為求 nCr 和 n! , n <= 2000 了
前者可以n^2 簡單 dp 求, 後者O(n) 直接求
比較要注意的是由於題目要mod 大數, 而inclusion-exclusion principle因為有 *-1 的關係
要記得 (S - inclusion-exclusion() + M)%M 確保取餘正確性
咦, WA了...oh shit, 忘了一樣重要問題...
上面的做法是假設了所有數字都是 -1 (任意填)
即著名的帽子問題(?)
而題目是有限死某些位置已經填了某些數了...
幸好影響不大, 主要是先求出一個set P = {pos : a[pos] = -1} 和 set N = {possible number}
P intersect N 就是可以中伏的數字, 至於其它的數字則是怎填都不會中伏的...
所以思路跟上面一樣, 就是現在 kCr 的k 不是 # of -1, 是 size of P intersect N
pos[] 是P , no[] 是N, poss 是k
dp[], f[] precompute好了
終於AC了...
好一排無上CF, 真係愈改愈user friendly (定我以前唔識用)
唔知好運定點, 是旦抽一set d2, 最後竟然5題都做到
而且今次code前code後都叫做有proof到個方法幾肯定, 說服到自己先code
亦都係第一次(真係第一次)睇editorial 無TLDR, 由頭睇哂佢, 最開心係basically writer 個proof
同自己諗既基本一樣...
不過可能因為公司無g++ 既關係, 全部都係notepad++ dup完係CF個custom test度試 (o:
準確度大大下降 (賴地硬ing)
between, 閑時睇番之前寫開d post 每次都會心諗: 原來我做過d咁既野 :o
TL;DR
題目: http://codeforces.com/contest/340/problems
A (Ad-Hoc, Math):
Given x,y,a,b; a,b <= 2*10^9, 問有幾多 lcm(x,y)既倍數係between [a,b]
Solution:
let L = lcm(x,y) = xy/gcd(x,y)
ans = # of k s.t. a/L <= k <= b/L
B (Geom):
驚奇地出現係第2題既Basic Geom..Given 300點, 問pick 4點組成既四邊形最大可能面積
Solution:
思路是如何形成的: 數據SIZE = 300, 即order 大約為 n^3 ?
好自然會諗到計三角形...
設 d[i][j] := 第i點 經第k點 到第j點 此三角形 (i,k,j) where i,j,k distinct 最大既三角形面積
答案就係 for 所有 pair (i,j) , max (d[i][j] + d[j][i])
正確性是肯定的, 首先因題目講明唔會3點同線, d[][] 一定唔會出0 area
但眾所尻知area有正負, 而當三角形(i,k,j) 係正面積時, 三角形(j,k,i) 會係同數值既負面積
(cross product特性)
所以當有最少4點時(題目講明), d[i][j] != d[j][i] for all i,j
其次max(d[i][j]+ d[j][i]) 一定係最大可能既4邊形面積, 好易用contradiction proof到
(成個方法唔使諗self-intersect case, 因為一定唔intersect好過intersect..太self explain了)
比較會中伏位係initialization!! 雖然唔會self-intersect (你唔會簡), 但concave係可以的, 而concave 4邊形既意思就即係話either 是旦一邊既三角形係負面積...亦即係話d[][] 唔可以initialize 做 0, 因為可能最optimal既三角形面積的確係 < 0 ...
C (Combinatorics):
是咁的, 呢條都算係幾有成功感既一題...因為我覺得(FF) 以前我應該未必做到...
Given n (<=10^5) 個distinct數, 每個數代表距離O既位置, 依家你係O, 類似TSP咁由O出發, 每個點都經過一次, 去到最後一點就停
咁好明顯就有好多種path (題目用route), 2個點自己既distance就係 absolute difference, 問average 所有possible path 你行既總distances, 用不可約分數表示
Solution:
是咁的, 首先呢d題目, 基本上分母都係好頹就諗到, 呢題都唔例外
分母 = # total possible path = n!
其實亦即所有permutations
重點當然係分子, 分子又可分開兩parts
Let input n個數 --> D[]
part I:
首先由O去第一個點既總distance
當我fix死第一個點為a, 則path如下
a???????....?
我後面共有(n-1)! 可能性, 而呢group path既distance = a
而a 其實可以係N個數是旦一個 (pick 邊個做第一點都得)
所以總和係 (n-1)! * summation( D[] )
part II:
for 任意permutation "a???????..??" , 依家你就站係a,
由a 去到最後一點既distance 為該permutation既總distance
而我地想要既係所有permutation既總distance 總和 (1999)
重點來了, 當我尻pick 2點, a & b, 必需相鄰既permutations 總共有多少條?
????ab?????..?
?ba?????....???
ab???????????
....
簡單地說, 就是n個位fix死2個位, 其它(n-2)個位隨意, 即 (n-2)!
但因為我想一同考慮 ab互換的permutations (如上 ba 鄰接的都算)
所以有 2*(n-2)! 條 permutations, 是ab (或ba) 放在頭2個位置
eg:
ab????...?????
ba????...?????
接著ab (或者ba) 在一條permutation可以放在(n-1)個位置上
所以總共是有(n-1)*2(n-2)! = 2(n-1)!條 , 而每條提供了 |a-b|的distance
數法大致就是這樣了, 接著都是為了方便code已講的
首先可以sort (D), 確保for i <j, D[i] < D[j], 跟住上面part II 則可便為
2(n-1)! *(D[j] - D[i] ) for all i <j
小總結一下, 分子是 part I + part II = (n-1)! summation(D[]) + 2(n-1)!(D[j]-D[i]) for all i < j
把(n-1)! 跟分母的 n! 約掉, 分母直接剩n , 分子則變為簡單的 summation(D[]) + 2(D[j]-D[i])
煩人的是如果直接計算D[j] - D[i] 還是需要O(n^2)...會超時
於是我煩悶的在紙上亂寫, 發現寫了不錯的東西:
D[] = {1,3,5,7}
7-5 +
7-3 +5-3
7-1 +5-1 +3-1 = ?
這個問題的答案就是D[j] - D[i] for all i < j 了...
咦...打直看一下, 打橫看一下, 不是很簡單的...
(3*7 + 2*5 + 1*3) - (3*1 - 2*3 - 1*5)
Generalize一下: ((n-1)*D[n] + (n-2)*D[n-1]+...+D[2]) - ((n-1)*D[1] - (n-2)*D[2] - ... D[n-1])
啊...原來一個FOR LOOP就OK了..
sort(a,a+n); for(int i=0; i<n;i++){ sum+=a[i]; up+= (n-i-1)*(a[n-i-1] - a[i]); }
sum是part I, up 是part II ...
最後print時記得分子分母再除以gcd() 一下...以免分子分母可約...
AC了 嗚啊
TL;DR : 答案 = (sum + up) / n , 記得約簡
D (DP, Bsearch):
很有趣的題目名, 很有趣的題目, 很有趣的題意
Given n (<10^5) 個數, 做bubble sort, 不過每swap 一個數, 會將該兩個數之間加條edge
所以sort好之後, 其實順路build左一個graph G 出黎, 求G上max independent set
Solution:
呢題亦都好感動, 因為之後睇番editorial, 成個諗法基本一樣!
亦學到好多以前無學到 (學唔識)既野...
先講結論: 即求input既 Longest Increasing Subsequence
Observation: for 序列中任意一個數 x, 在完成整個sorting後, 佢一定會同原本排在之後, 而且比自己小的所有數y 有edge
掉轉黎講: 亦即最後2點 之間無edge代表最初序列中該2個數次序正常 (x 比y小, 而且排在y前面)
而由於independent set 既definition為, set 中任意2點皆無edge,
亦即得出任意2個數 在最開頭已經排好次序了
而求最大的independent set, 不就是求最多(最長)在最開頭已經排好次序的子序列嗎?
(上面呢段廢話亦即 editorial 既lemma1 + lemma2)
重點來了, 數據關係, 肯定要用nlogn算法了...問題在於其實由頭到尾我都無好好了解過
LIS nlogn 算法...借此機會於是做左d功課...發現的確很聰明又很簡單..在此記一記廢事又要google過...
有短的寫法 , 也有長的寫法
短的寫法只能找出LIS的長度, 並不能找出正確的LIS...長的寫法則2種都做到
此題由於只求長度, 我用了短的寫法, 大約是咁的:
用一個data structure, array也好, stack也好, 總之要令裡面永遠都是sort好的,
而最後期望該data structure的size 就是LIS的長度, 至於裡面裝的是不是真的LIS我們不管
每一個input a, 如果a 比裡面所有數還大, 直接放入去, 原因: GREEDY
如果不是最大的, 則在裡面找一個剛剛比a 大的, 用a 取代 該數
正確性很好理解的, 首先如果a 比裡面所有數都大, 自然是可以放進去了, LIS亦可以加大
而當a 比裡面某一些數小, 代表什麼呢?
1. 首先代表LIS 起碼等於此時data structure的size
2. 我把a 取代裡面的數 不會令size (此時的LIS)有變化, 但卻會使潛力大了
用{1,7,8,3,4} 做例子
首先structure會有 {1,7,8} ,此時LIS為3
當見到3, 會用3取代7, 變為{1,3,8} LIS同樣是3, 但潛力卻大了, 因為{1,3} 是去到此刻, 長度為2的IS中最優的, 你會發現{1,3,8} 其實是不存在的, 這裡面隱藏了一個巨大意思...
就是任何時候structure裡 index 為i 的數, 就是 長度為 i 的IS去到此刻最優的尾數
that is:
去到input = "3"為止,
{1,3,8} --> 1 是 長度為1 的IS中最小的尾數
3是長度為2的IS中最小的尾數
8是長度為3的IS中最小的尾數 (存在 {x,x,8} 這樣的一條IS, 而且沒有其它長度為3的IS尾數比8小)
之前說的較長 (可找出LIS)的寫法就是用了這種概念...詳細寫法擇日再寫...
這是何等的屈機呢...
言歸正傳, 短的寫法實作我是用<set>, 因為<set>的find, insert, 都是logn的
(提交前改了<multiset>, 主要是怕當有repeat input 會出事)
for(int i=0; i<n;i++) { scanf("%d", &a[i]); st.insert(a[i]); //自動會插入一個合適的位置 it = st.find(a[i]); if(++it != st.end()) //如果該數之後已經是end, 則代表該數最大; 不然便是要取代一個數了 st.erase(it); }
E (Combinatoics, DP):
終於到E了...不過先要利申...本身是不打算看題目的了, 因為一直都不會做到D/E...
所以做之前直接去看Editorial, 故意避開了E的題解, 但還是偷看到了inclusion-exclusion principle....而最後過到之後睇番原來原意是想用DP解的...現在還不明白如何用dp做, 反正我自己是用(第一次)inclusion-exclusion principle做
題意是咁的 given n (<2000) 個distinct既數, 當中有d 係unknown, 有d given (即fix死)
如
a[] = {-1, -1, 5, 3, -1}
5 跟 3 是fix死的, 而 1, 2 ,4 即是可以填在-1的位置上
問有多少種combination s.t. 填完之後, a[i] != i for all 1<=i<=n
Solution:
其實老實講我覺得題C難數過這題..(雖然呢題都卡左陣=.=)
如果直接apply inclusion-exclusion principle
答案就是這樣的:
S - ( #at least 一個位 a[i] = i - #最少兩個位 + #最少三個位 - .... +(-1)^(i+1) * # 最少n個位 )
where S = k! , k = # of -1
來看看最少一個位中伏的數目, 設k 是 # of -1
則除fix好的中伏位之外任意排 = (k-1)!
可以fix 的位置有 kC1 個
如此類推
最少兩個位的 有 kC2 * (k-2)!
...
問題便簡化為求 nCr 和 n! , n <= 2000 了
前者可以n^2 簡單 dp 求, 後者O(n) 直接求
比較要注意的是由於題目要mod 大數, 而inclusion-exclusion principle因為有 *-1 的關係
要記得 (S - inclusion-exclusion() + M)%M 確保取餘正確性
咦, WA了...oh shit, 忘了一樣重要問題...
上面的做法是假設了所有數字都是 -1 (任意填)
即著名的帽子問題(?)
而題目是有限死某些位置已經填了某些數了...
幸好影響不大, 主要是先求出一個set P = {pos : a[pos] = -1} 和 set N = {possible number}
P intersect N 就是可以中伏的數字, 至於其它的數字則是怎填都不會中伏的...
所以思路跟上面一樣, 就是現在 kCr 的k 不是 # of -1, 是 size of P intersect N
LL ans = 0, poss = 0; for(int i=1; i<=k;i++)poss += (pos[i]&no[i]); for(int i=1; i<=poss;i++){ LL p = ((dp[poss][i] * f[n-i])%M)*(i%2? 1:-1); ans = (ans + (p+M)%M)%M; } printf("%I64d\n", (f[n] - ans+M)%M);
pos[] 是P , no[] 是N, poss 是k
dp[], f[] precompute好了
終於AC了...
2013年9月2日 星期一
訂閱：
文章 (Atom)