Questions about Step 7 for problem E — Wonderful Teddy Bears:
1) What does it guarantee us that we can make operation A or operation C first d times? What if array is not sorted, but we can't make operation A or C?
2) What does it guarantee us that we can make operation B or operation D every time after first d times? What if array is not sorted, but we can't make operation B or D?

Thanks! :)

Can you explain the last two senetences?
How can we "convert" king distance to manhattan distance by rotating the plane?

If we have a point with coordinates (x,y) distances from (0,0) (some ai and bi could be 0, says the problem) are king: max(x,y) and manhattan: x+y, aren't they?
By rotating them by 45 degrees coordinates will be ((x-y)/sqrt(2),(x+y)/sqrt(2)). Distances from (0,0) are king: max((x-y)/sqrt(2),(x+y)/sqrt(2)) and manhattan: x*sqrt(2).
First(before rotation) king distance is not like second(after rotation) manhattan distance. Furthermore, neither of the 4 distances are matching.

Thanks. Now I understand.

Thank you.
I understand answer for the first question (thanks again), but I have no idea what happened on the right side of equation in second answer. I have never seen something other than angle denoted as Θ. Is Θ some function? How do I calculate Θ(n^(m+1))?

I have a few questions regarding Solution 2 for Problem F.
1) "By induction we can prove that both fk(n) and Sk(n) are polynomials." How can we prove this?
2) "From the definition of Sk(n), we have q(k)=p(k)+1."
The definition of Sk(n) is sum of fk(i) for i=1 to n, isn't it? Because of that, Sk(n) is sum of polynomials with degree p(k). Sum of polynomials with degree p(k) should have the same degree (as p(k)). Supposing all of that, q(k) should be p(k). How is q(k)=p(k)+1?

Aaaaaaa... Smart! Thank you very much.

How to efficiently update all js?
Using example fl0>fr0, j>0 won't give us a more optimal i+j, but how to update all i+js? If I update all js (all f[i+j]), time will be O(n*log a*log a) again.
Even if I update just the smallest/optimal i+j, if I go through all i (so, in this scenario, I only have i for loop, I don't have two for loops for one vertice from Cartesian tree), in my code there is a loss of generality for fli>fri. Maybe fri>fli. Fl is non-incresing which means maybe there is some t, where i>t and fri>flt>=fri. And then fri and fli is not optimal i+j so I lose generality. (Although I agree there isn't a loss of generality for fli>fri when we have two nested for loops for each of vertices, because we can operate with j for loop, but, again, that is O(n*log a*log a).)