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

 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