如果係真相
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日 星期一
2013年4月25日 星期四
Croc Champ 2013 - Round 2 (Div. 2 Edition)
好似係final round, 正式比賽既A,B,C = d2 既C,D,E
剩係做到4題, 但後來對照番正式比賽, 其實200名內(有T-shirt)既好多都剩係做到題A(即d2 C)..
嗚呀
http://codeforces.com/contest/299 <--題目
A:
題意係N個數, 想知有無一個數係大家既common factor
B:
題意係比N個char你, 每個可以係行得/唔行得(石頭)
你可以由原地跳前 1<=i<=k 格, given N,k 同N個char, 問可唔可以由最左去到最右
永遠都可以最近石頭既空格跳, 即detect有無連續k個石頭
C:
就係正式比賽既A, 如果可以15分鐘內1棍過就有200名內 = 有T-shirt =[
係一題所謂既game, 但其實簡單greedy就ok
基本就係定好每個人最好既pick次序:
1. 兩個都係1一定最大價值, 自己多1對面少1
2. 自己係1 對面係0
3. 自己係0 對面係1
4. 兩個都係0
2同3 唔可以掉轉, 利己 > 損人, 因為自己pick 1 對面下一步只可以pick 番1 (打和) 或者ban 你1 (少你1) 黎對抗, 貪心地諗一定係最好, 反之如果ban 人行先, 去到極端可以出現你咩都無(因為你全部都ban人), 對面有少數1
另外注意下行先個個可以pick先...不過數據好細, 其實照simulate就ok
E:
其實過左都唔覺得特別難..係我數學特別差(所以從來都好憎見到咩number theory個d)
題意大約就係given n (<= 10^14),
solve ordered tuple(a,b,c) for
(a+b)^3 - (a^3 + b^3 + c^3) = n
a,b,c are positive integers
是咁的, 由於數據太大, 基本一定係sqrt(N) / lg(N) 甚至更少去做..當然先試下factorize條式等佢靚仔
呢度就係我覺得自己廢既原因, 我fac極都係出左d 極樣衰既form
結果問左偉大既chin爺, 之後再親身fac多次 無錯
LHS 係 3(a+b)(a+c)(b+c) 黎
其實呢度已經end of story...因為我覺得最難個part都比佢一下講完, adore
之後就係coding 上既問題..
首先 if(n%3)就無解, 跟住先了解一件事...我數底再差都知每一個component都係 <= cubicroot(N)
所以, 就先用O(cubicroot(N)) 黎搵哂合格既factors先
(小插曲, 其實我印象中唔知邊個講過total # of factors of integer N 係O(lg N), 但點諗都唔似係,結果問chin爺, 好似未有確定既Order?)
anyway, fac[] <-- 所有 <= cubicroot(N) 既factors, ~O(10^3)
咁就可以let (a+b) = fac[i] , (a+c)(b+c) = N/fac[i]
咁樣set係好合理, 因為fac[i] <= N/fac[i] && (a+b) <= (a+c)(b+c)
由, 我唔想數到重複count左一樣既組合, 所以我希望先搵哂所有(a',b',c') where a<=b<=c
用多一個loop j , fix死 a = j, b = fac[i] - j, 跟住計c出黎 (solve quadratic equation)
最後睇情況,
如果 a,b,c 一樣既就 +1, 如果是旦2個1樣既就+3, 3個都唔同既就+6
處理好唔同order既數目
LL fac[1000005];
LL solve(LL a, LL b,LL t){
LL c = 0;
LL delta = (a+b)*(a+b) - 4*(a*b-t);
LL sq = (LL)sqrt(delta)*(LL)sqrt(delta);
//血的教訓, 想test delta是否perfect square, 一定要parse做LL type先..
if(delta < 0 || sq != delta) return 0;
LL up = -(a+b)+sqrt(delta);
if(up > 0 && up%2 == 0) c = up/2;
//只拎 -b + sq(delta) 就得, 因為另一個一定係負數(如果有)
//c 已計, 下面處理重點問題
if(!c) return 0;
if(a == b && b==c)return 1;
if(a==b || b==c || a==c) return 3;
//如果c係正數, 先check下有無3個一樣或2個一樣既情況
//注意呢2個情況一定唔會repeat counting, 唔識用字面解釋, 總之唔會
if(c <= b) return 0;
//呢句一定要加, 就係減走d 當3個數唔同時repeat count既tuple
//當c <= b, 咁c 曾經係之前某次數既a或者b黎, 所以唔使再計
return 6;
}
int main(){
LL n,p=0,a,b,c,ans = 0;
scanf("%I64d", &n);
if(n%3){printf("0\n"); return 0;}
n/=3;
for(LL i=1; i*i*i<=n;i++) if(n%i == 0)fac[p++] = i;
for(int i=0; i<p;i++){
for(int j=1; j+j <= fac[i]; j++){
a = j; b = fac[i]-j;
ans+=solve(a,b,n/fac[i]);
}
}
printf("%I64d\n", ans);
return 0;
}
D: (唔識做)
終極變態題..話說開頭睇錯題目..以為係半頹半唔頹既COMBINATORICS..
後尾發現係要<紅色超大>所有</紅色超大>path都唔撞色...
如果問題係成個grid都係吉既任我填, 而且d 色係唔會多過你需要既(即n+m-1種)咁好易數
因為非正式prove左咁既情況所有path既排列一定要一樣, 唔係會影響到某d其它path令佢地撞色
答案係 kP(n+m-1), 由於k == n+m-1, 所以答案即係k!, 例子係example 3,答案係10!
好啦,問題是咁的,
1. 顏色係可以多過你需要既
2. 某d格係已填色, fix死左, 唔可以轉
嗚..
暫時諗到既只有
1. 真正既grid好細 (n+m 大約10之內) 所以做法可以暴力d
2. 似dp + combinatoric
3. 由最左邊"L"型條PATH開始填, 跟住一個個"L"型既path咁填落去
4. 每一個"L"型既某一格, 可以用番上一個"L"型相對應個格既色, 或者一d so far未用過既色
....
唉頭都爆, 放棄鳥 /.\
2013年4月22日 星期一
Some codeforces (Div 2 only) & Croc Champ 2013 q-round & round 1
仲有一個月就完成一年既internship...究竟有無簡錯我都唔知
除左一月至三月好chur之外其實都幾hea 既
唔知點解結果都係搵番d 題目做, 掉低左咁耐結果都係番左黎 =[
的起心肝屋企裝番cygwin set番好environment,
無打一排, 好多野唔記得, 但又有d野以前點都唔明依家好似易明左
例如segment tree...
B:
所以code法簡單同standard, 重點就係你點決定個node裝咩, 跟住相對地改番update / query 咁
順路做左2題poj 入門題一棍AC, 更加有番信心
隨後我見到幾樣都有必要記下既野:
1. BIT 未必做到Segment tree 做到既野, 但Seg Tree基本上咩都做得哂
2. 總之係一d 連續性array 上做統計既題目, 外加要O(lg N) 既好大機會係Seg tree
3. tree array要開N 既4倍 , 我唔知點解, GOOGLE左陣d人話Tree node數的確係2N-1, 但係會有機會搵 current >> 1, 1+(current >> 1)時out of range, 但睇code好似唔會? (因為l == r 時已經return 左, 去到leaf 應該唔會再落..) 請路過人士都可以解釋下
總之, 就係咁, 我就好有自信地番黎做E, 當然又唔係想像中咁易...
題意大約是咁的: 有2條array, 每次query 可以update (a_i, b_j, length), 意思係由b_j 開始計共length咁多格都加上a_i 開始計length咁多格 (相對應既1-1 mapping); 又或者可以問你某一個位置 j 既b_j value.
苦腦左一陣, 究竟一個tree node應該store咩先可以唔使update到leaf呢 ? (因為query 一定要到leaf, 如上面所講, update唔可以次次都去到leaf) 諗住一陣, 我整左個好複雜既structure (o:
除左一月至三月好chur之外其實都幾hea 既
唔知點解結果都係搵番d 題目做, 掉低左咁耐結果都係番左黎 =[
的起心肝屋企裝番cygwin set番好environment,
公司機裝唔到cygwin (o: 直接裝左vim 係Windows cmd
是旦搵左幾場d2 CF 玩, 果然差d 連vim 都唔識用, 慢慢打下google下先好番少少
CF都變左好多, 愈黎愈大型, 我覺得可能大型過Topcoder了
亦都算係一個問contest trick既social platform
某幾場D2 既CF 遲d先補番..反正都係熱身用
主要都係想留念Croc Champ 2013
是旦搵左幾場d2 CF 玩, 果然差d 連vim 都唔識用, 慢慢打下google下先好番少少
CF都變左好多, 愈黎愈大型, 我覺得可能大型過Topcoder了
亦都算係一個問contest trick既social platform
某幾場D2 既CF 遲d先補番..反正都係熱身用
主要都係想留念Croc Champ 2013
無打一排, 好多野唔記得, 但又有d野以前點都唔明依家好似易明左
例如segment tree...
Croc Champ 2013 Qualification Round
話說通常Q-round d題目應該都易d既, 所以我熱完身就做Q-round先 B-)
果然, TLE / RE 一堆on9 error 出哂黎 :D
最後solve左A-D
A:
頹題, 就是做 : - /
果然, TLE / RE 一堆on9 error 出哂黎 :D
最後solve左A-D
A:
頹題, 就是做 : - /
B:
頹廢string parsing, 就是做x2 :/
C:
第一題學番d野既題目。明顯就係brute force, 問題係d code得有技巧又快。有睇過下偶像d code, 立即就知道(其實以前一路都係) bitwise manipulation 完全無sense, 亦都諗得慢, code得唔熟, 呢題叫做可以做番相關方面, 只要熟悉 bitwise operators syntax, 呢題好直接無陷阱
C:
第一題學番d野既題目。明顯就係brute force, 問題係d code得有技巧又快。有睇過下偶像d code, 立即就知道(其實以前一路都係) bitwise manipulation 完全無sense, 亦都諗得慢, code得唔熟, 呢題叫做可以做番相關方面, 只要熟悉 bitwise operators syntax, 呢題好直接無陷阱
D:
一題IQ題, 題意大約如下: 有一條length n 既array { a_i = 1 for 1 <= i < n , a_n = 0}
One move := a_i = a_i + a_c for all i and any c, 1 <= i,c <= n
目標係用required 咁多move 令所有a_i = n-i
i.e : ;由{1,1,1,1,1,0}--> {5,4,3,2,1,0} for n = 6
明顯就係可以greedy地做, 使每個number 每move 愈接近target愈好, 因為咁樣可以minimum move就reach target, 如果仲有得行, 就可以將已到target既number + a_n (i.e: 0)
所以algorithm 大約就係for each a_i, find maximum a_c such that a_i + a_c <= n-i
而由於其實每行一個move, 愈左邊既number一定大於等於右邊既number, 所以其實搵到第一個附合上式既a_c就已經係maximum a_c, 可以cut走d cases
E:
心理恐懼加我懶, TLDR(A.K.A TOO LONG DIDN'T READ)
所以無做到亦唔知題目問埋...似係tree 類問題..唔係graph就應該係dp了 (我估)
咁就做完Q-round, 又唔係真係易到咩咁, 難又未至於, 起碼全部都幾ad-hoc既...
所以我就開始做round 1
round 1 好煩膠, 但真係學到勁多野, 係煩左我幾日之後, 終於久違地5條都AC哂 (感動)
而且亦都直接令我搞明左以前一直唔識既segment tree basic concept (感動x 2036)
(不過每題基本都係錯到九彩先AC, 實戰應該比人hack死左 :=[ )
C:
One move := a_i = a_i + a_c for all i and any c, 1 <= i,c <= n
目標係用required 咁多move 令所有a_i = n-i
i.e : ;由{1,1,1,1,1,0}--> {5,4,3,2,1,0} for n = 6
明顯就係可以greedy地做, 使每個number 每move 愈接近target愈好, 因為咁樣可以minimum move就reach target, 如果仲有得行, 就可以將已到target既number + a_n (i.e: 0)
所以algorithm 大約就係for each a_i, find maximum a_c such that a_i + a_c <= n-i
而由於其實每行一個move, 愈左邊既number一定大於等於右邊既number, 所以其實搵到第一個附合上式既a_c就已經係maximum a_c, 可以cut走d cases
E:
心理恐懼加我懶, TLDR(A.K.A TOO LONG DIDN'T READ)
所以無做到亦唔知題目問埋...似係tree 類問題..唔係graph就應該係dp了 (我估)
咁就做完Q-round, 又唔係真係易到咩咁, 難又未至於, 起碼全部都幾ad-hoc既...
所以我就開始做round 1
round 1 好煩膠, 但真係學到勁多野, 係煩左我幾日之後, 終於久違地5條都AC哂 (感動)
而且亦都直接令我搞明左以前一直唔識既segment tree basic concept (感動x 2036)
(不過每題基本都係錯到九彩先AC, 實戰應該比人hack死左 :=[ )
Croc Champ 2013 Round 1
A:
頹題, 加下減下咁, 就是做
B:
B:
一開頭比3幅圖嚇死左，諗深一層原來仲頹過A...
直接check 每個node既degree就好, 好似係year 1 csc2100 教d野?
直接check 每個node既degree就好, 好似係year 1 csc2100 教d野?
C:
又係IP, 心諗唔係又玩bitwise野...好彩唔係
原來係玩d再煩膠d既野 (o:
題意是咁的
given n 個digit , n <= 10,
你要用哂(重點) 所有digit at least once, build 一個ip address, such that 呢個ip address 係palindrome
原來係玩d再煩膠d既野 (o:
題意是咁的
given n 個digit , n <= 10,
你要用哂(重點) 所有digit at least once, build 一個ip address, such that 呢個ip address 係palindrome
叫你唔使順次序, print哂所有possible既ip address出黎
真係好煩..難怪大家都唔做呢題住
FUCK!
真係好煩..難怪大家都唔做呢題住
首先, 因為IP最多得12位, 你又一定要用哂given 既digit, 又要palindrome, 所以 n > 6 係無解。
好明顯係暴力試...都係個句, 點樣暴力試先會run得快, code得快就係水平既分別
無意中又諗起唔知幾時Joe 爺講過 「唔好以為d暴力試個d煩膠題就唔使做」
so pure so true.
so...每個人都有唔同做法既, 我既做法相當之笨
首先諗辦法 generate 所有"possible"既string, 所謂"possible"既string 就係 length 4 ~ 12
而且given digit 一定出現過哂既palindrome.
generate 方法是咁的, 例如given, 0,1,2,9,
let tmp = "0129",
好明顯係暴力試...都係個句, 點樣暴力試先會run得快, code得快就係水平既分別
無意中又諗起唔知幾時Joe 爺講過 「唔好以為d暴力試個d煩膠題就唔使做」
so pure so true.
so...每個人都有唔同做法既, 我既做法相當之笨
首先諗辦法 generate 所有"possible"既string, 所謂"possible"既string 就係 length 4 ~ 12
而且given digit 一定出現過哂既palindrome.
generate 方法是咁的, 例如given, 0,1,2,9,
let tmp = "0129",
我地可以expand tmp, tmp = "0129x" where x belongs to {0,1,2,9}
最多我地可以expand 到 6個位 i.e : tmp = "0129xx"
咁呢d x, xx 其實就係all combination of given digit for certain length ( length <= 6)
可以用dfs backtrack precompute哂先
所以我地就可以generate 哂 由最少2個位至最多6個位既tmp,
最多我地可以expand 到 6個位 i.e : tmp = "0129xx"
咁呢d x, xx 其實就係all combination of given digit for certain length ( length <= 6)
可以用dfs backtrack precompute哂先
所以我地就可以generate 哂 由最少2個位至最多6個位既tmp,
(好煩, 做左/ 識做/ 有更好方法請教我 orz !!)
繼續, 搵個vector 裝住d tmp string, 之後每個possible string sort左佢再用next_permutation()
for 每個permutation, 我地可以generate 相對應既2條possible string:
例如 tmp = "1209" in this permutation loop,
possible = tmp + reverse(tmp) or tmp + reverse(tmp - last char of tmp)
終於我地就會有哂d possible既string, 最後每條possible string check() 一次, 睇下ip 個3點放邊個位, 放完之後符唔符合ip 既rule (每一節唔可以0開頭, 唔可以 > 255 etc)
將所有ok 既string (即ip) 放去一個set
繼續, 搵個vector 裝住d tmp string, 之後每個possible string sort左佢再用next_permutation()
for 每個permutation, 我地可以generate 相對應既2條possible string:
例如 tmp = "1209" in this permutation loop,
possible = tmp + reverse(tmp) or tmp + reverse(tmp - last char of tmp)
終於我地就會有哂d possible既string, 最後每條possible string check() 一次, 睇下ip 個3點放邊個位, 放完之後符唔符合ip 既rule (每一節唔可以0開頭, 唔可以 > 255 etc)
將所有ok 既string (即ip) 放去一個set
一定要set, 因為有重覆..亦都係我覺得其實唔使咁煩既原因, somehome應該有方法直接搵哂d答案出黎
output set 入面所有string , done.
再次請如果有路過人士識做又唔使咁煩既, 請教一教小弟=[
E:
次序上我係做左E先既..所以就寫E先。
無錯, 一題就知係我唔識做既(當時)
但係我又知係SEGMENT TREE, 又見好多人AC, 又見d人code好短, 把心一橫, 我就去搵segment tree既source學去, 結果搵到一番幾好幾易明既 重好有信心既tutorial:
http://poj.org/summerschool/1_interval_tree.pdf
畫兩畫之後...其實發現, 其實唔難(basic) 其實build tree, 應該好standard,
至於query 同 update, 我發現重點其實係2個
1. 每個node 裝咩信息
2. depends on 1, such that at least query / update唔會次次都要search到去node, 因為好似會有機會變左O(N) (唔識prove)
再次請如果有路過人士識做又唔使咁煩既, 請教一教小弟=[
E:
次序上我係做左E先既..所以就寫E先。
無錯, 一題就知係我唔識做既(當時)
但係我又知係SEGMENT TREE, 又見好多人AC, 又見d人code好短, 把心一橫, 我就去搵segment tree既source學去, 結果搵到一番幾好幾易明既 重好有信心既tutorial:
http://poj.org/summerschool/1_interval_tree.pdf
畫兩畫之後...其實發現, 其實唔難(basic) 其實build tree, 應該好standard,
至於query 同 update, 我發現重點其實係2個
1. 每個node 裝咩信息
2. depends on 1, such that at least query / update唔會次次都要search到去node, 因為好似會有機會變左O(N) (唔識prove)
所以code法簡單同standard, 重點就係你點決定個node裝咩, 跟住相對地改番update / query 咁
順路做左2題poj 入門題一棍AC, 更加有番信心
隨後我見到幾樣都有必要記下既野:
1. BIT 未必做到Segment tree 做到既野, 但Seg Tree基本上咩都做得哂
2. 總之係一d 連續性array 上做統計既題目, 外加要O(lg N) 既好大機會係Seg tree
3. tree array要開N 既4倍 , 我唔知點解, GOOGLE左陣d人話Tree node數的確係2N-1, 但係會有機會搵 current >> 1, 1+(current >> 1)時out of range, 但睇code好似唔會? (因為l == r 時已經return 左, 去到leaf 應該唔會再落..) 請路過人士都可以解釋下
4. 有好幾題都幾出名 (隱約記得training有人講過)都係用到離散化+Seg tree做, 遲d繼續研究, code熟哂d 基本野先
總之, 就係咁, 我就好有自信地番黎做E, 當然又唔係想像中咁易...
題意大約是咁的: 有2條array, 每次query 可以update (a_i, b_j, length), 意思係由b_j 開始計共length咁多格都加上a_i 開始計length咁多格 (相對應既1-1 mapping); 又或者可以問你某一個位置 j 既b_j value.
苦腦左一陣, 究竟一個tree node應該store咩先可以唔使update到leaf呢 ? (因為query 一定要到leaf, 如上面所講, update唔可以次次都去到leaf) 諗住一陣, 我整左個好複雜既structure (o:
struct node{ int l,r,as,bs,t; }T[N<<2];
l,r 係range啦, as, bs 係array a或者b 既起始位置, t 係最新update時間
於是我每次update, 發現該interval 有更新既update, 我就可以直接update 該interval 既as,bs,t
而唔使去到leaf node.
於是query時, 我由tree root開始一路落, 發現有更新既 update t , 就取該interval既as, bs
最後就可以用as, bs, 計番b_j 係該時間點相對應既a_i 。
(有機會無被update過, special handle左好多行...就直接output番b_j)
最後好慢好慢地, AC左!
再睇人地D CODE, fuck, 人地node structure簡單, code又短又快, 究竟點做到...
D:
2個鐘前又MLE 又TLE (都係自己白痴) 終於AC左...
一路唔知點做, GG 比左提示, 就咁disjoint set 都可以做到, 而唔使用到咩link cut tree / dynamic tree 一d我唔識既野 (o:
於是我每次update, 發現該interval 有更新既update, 我就可以直接update 該interval 既as,bs,t
而唔使去到leaf node.
於是query時, 我由tree root開始一路落, 發現有更新既 update t , 就取該interval既as, bs
最後就可以用as, bs, 計番b_j 係該時間點相對應既a_i 。
(有機會無被update過, special handle左好多行...就直接output番b_j)
最後好慢好慢地, AC左!
再睇人地D CODE, fuck, 人地node structure簡單, code又短又快, 究竟點做到...
D:
2個鐘前又MLE 又TLE (都係自己白痴) 終於AC左...
一路唔知點做, GG 比左提示, 就咁disjoint set 都可以做到, 而唔使用到咩link cut tree / dynamic tree 一d我唔識既野 (o:
題目是咁的
given n 個node及m條edge, n<=500, m <= 10^4
given k 個query , k <= 2*10^4
每個query係delete 連續某個range既edge (根據input 次序)
問有幾多個connected component
given n 個node及m條edge, n<=500, m <= 10^4
given k 個query , k <= 2*10^4
每個query係delete 連續某個range既edge (根據input 次序)
問有幾多個connected component
好可怕好可怕..
但根據GG既提示同埋題目講到明要連續地delete, 好明顯"連續"係有d意思的...
尋晚沖涼諗諗下, 又覺得好似partial sum , 即係可以用a[i] 代表 由0加到i 既sum
咁a[i] - a[j-1] 就係由j 加到i 既sum...之類
確認左呢個方向再諗左好一陣, 就諗到大概方向 (仲未sure code唔code得出)
但根據GG既提示同埋題目講到明要連續地delete, 好明顯"連續"係有d意思的...
尋晚沖涼諗諗下, 又覺得好似partial sum , 即係可以用a[i] 代表 由0加到i 既sum
咁a[i] - a[j-1] 就係由j 加到i 既sum...之類
確認左呢個方向再諗左好一陣, 就諗到大概方向 (仲未sure code唔code得出)
是咁的, 其實, 首先, d edge由第0條加到第n 條, 或者掉轉由第n條友到第0條
個graph 都係一樣, 我就諗 其實delete 第i 到第j 條edge 個graph 咪姐係
第0條edge 加到第 i - 1 條edge <---graph 1
第n條edge 加到第 j +1條edge <---graph 2
兩個合體?
又, 其實我有辦法可以union左呢2個graph, 叫做G' 先好, G' 既 connected component # 就係答案
個graph 都係一樣, 我就諗 其實delete 第i 到第j 條edge 個graph 咪姐係
第0條edge 加到第 i - 1 條edge <---graph 1
第n條edge 加到第 j +1條edge <---graph 2
兩個合體?
又, 其實我有辦法可以union左呢2個graph, 叫做G' 先好, G' 既 connected component # 就係答案
於是我先precompute 2個"partial disjoint set"
s1[i][j] = 由0加到第j 條邊時既disjoint set
s2[i][j] = 由n 加到第 n-i-1條邊時既disjoint set
之後for 每個query , 我用左少少trick, 用第3個 array 叫merge []
我將 相對應既s1[i][j] 放係merge [0 --> n-1]
相對應既s2[i][j] 放係merge[ n-->2*n-1]
s1[i][j] = 由0加到第j 條邊時既disjoint set
s2[i][j] = 由n 加到第 n-i-1條邊時既disjoint set
之後for 每個query , 我用左少少trick, 用第3個 array 叫merge []
我將 相對應既s1[i][j] 放係merge [0 --> n-1]
相對應既s2[i][j] 放係merge[ n-->2*n-1]
依家merge array 既第 i 格同第i +n 格其實就係refer緊同一個node
所以, 我for all i < n, union (i, i+n) on merge[] ,
最後數下 merge [] 有幾多個唔同既connected component, done.
奇怪既係, 我最後一個step用set 數, 會TLE, 轉番用array數反而無事
不過都係好慢 X(
嗚啊, 好想快d pick up番啊, 老細可唔可以唔好比野我做 :(
所以, 我for all i < n, union (i, i+n) on merge[] ,
最後數下 merge [] 有幾多個唔同既connected component, done.
奇怪既係, 我最後一個step用set 數, 會TLE, 轉番用array數反而無事
不過都係好慢 X(
嗚啊, 好想快d pick up番啊, 老細可唔可以唔好比野我做 :(
訂閱：
文章 (Atom)