Codeforces Round 352

Codeforces Round 352 screen cast by eddy1021

First of all, this contest is extremely nice! I strongly recommend to (virtual) participate in it.

A is not a difficult problem but require some careful examination. Given n points and three points A, B, C on OXY coordinate, you should move A or B to pick those points one by one and carry it to C. Find the minimum total distance traveled by A and B combined.
Actually, whenever we move A and B to C, all the other unpicked points will need 2*(distance between C and each point). Thus, we just need to find which two point p1,p2 should be picked at first by A and B. We can record which one minimize the cost and choose the best combination. But, lots of people failed system test because didn't handle the case that A or B can stay and do nothing. However, I also failed on system test with a frustrating typo.

B is an interesting problem. Given n up to 500000 people and k up to 10^9, each one has c_i dollars. And, you will perform k times operation as follow: take one dollar from richest person and give it to the poorest one. You should find the difference between richest and poorest person after performing k times operations.
We can binary search the wealth of poorest one and richest one. For poorest one, we just need to check whether we can make those with less dollar than the chosen one with k dollars. So as richest. Finally, be careful to the lowerbound of the answer which should be at least 1 if number of people can't divide total wealth otherwise lowerbound is 0.

C is also a nice problem. Given an array of 200000 distinct numbers between 1 and 200000, define f(A) on a array as the maximum g.c.d. value among each pair of number. Find the summation of f(A') where A' is obtained by removing subarray [i..j] from original array where 1<=i<=j<=n.
My solution seems to be different from the one provide by auther. My idea is to consider three case: considering the resulting array which will be a prefix or a suffix or a prefix concantenated with a suffix of original array. Thus, for prefix one, we can go from 1 to n. Define dpl[i] as f(A) of i-th prefix, then dpl[i] = max(dpl[i-1],some factor of(a[i])). Thus, we maintain another information lft[x] as leftest position where x divides a[x]. Then, considering all factors of a[i], if lft[factor of a[i]] < i, we can update dpl[i] with this factor. So as the part of sufiix.
Then, considering the case of prefix concantenated with suffix, we can go from n to 1, and maintain the sum of dpl[i] in a segment tree. Then, for i-th prefix(1..i) and j-th suffix(j..n), the answer will be max(dpl[i],dpr[j],factor between (1..i) and (j..n)). Thus, when we reach j, we can check all the factor of a[j], if lft[factor of a[j]]<j, we can update this value between [ lft[factor of a[j]] .. j-1 ]. However, we can't directly maintain this value by segment tree(summation segment tree with max lazy-tag). By observing that dpl[i] will be increasing, we can binary search which interval should be update. Then, we can easily maintain it with segment tree. Finally, to calculate the answer for all i-th prefix with fixed j-th suffix, we use the same idea, dpr[j] may dominate some interval(actually prefix). Thus, we binary seach the interval and take the value of another interval in segment tree.

D, E are also interesting problems which I can't solve so far.

Rank 36 on final standing. And reach IGM with exactly 2601.
Hope to keep climbing up the ranking of rating!