A while back I solved the problem wxhtzdy ORO Tree and I had some problems with the time limit, but I managed to squeeze it below the 5s mark by, instead of calculating for each important node the value of the function, calculating the contribution of each important node to the original answer (link to AC submission). I thought that calculating the value of the function each time has a large constant factor and it turned out to be true. However, a few days ago I was helping a friend solve the problem and noticed that his code, with the same idea that would not work for me (link to the TLE submission), passed comfortably. Now, I am confused as to why my code is so inefficent. Could anyone help me point out the bottlenecks in my code?

The second task from day 1 of CEOI 2016 is a task with a solution that confuses me, not because it is hard to understand, but because of the fact that I cannot understand how someone could come up with it. When I read the official solution, it just looks like they shuffled some formulas around until they got an expression with an invariant with no real motivation for the process. Is there any, more intuitive approach for solving this problem? Thanks in advance.

The task in question is as follows: given N points on a coordinate plane, for some point A find the furthest point (manhattan disrtance) from A in the given set of N points. I know that one of the solutions to this problem is to consider only 4 points, the one with maximal (x + y) value, maximal (x — y) value, maximal (-x — y) value, maximal (y — x) value. It is guaranteed that one of these 4 points will be the furthest point from A. I can see that by doing this we maximize all of the 4 cases of the manhattan distance formula, but when we insert these 4 points into the formula it is not guaranteed that the corresponding cases we want to maximize will hold. Can anyone help me understand why this solution works?

After havin read this great blogpost https://mirror.codeforces.com/blog/entry/68953. I was left a bit confused. In a lot of the problems, it is assumed that any vector that is a linear combination of the basis can also be represented by a linear combination of the vectors from the vector space? Is this true? If so how to prove it. If not, why does the solution of 2a work?

Does anyone have mathematical proof for the solution of CF #614 Div. 2 B. The tutorial says that it: "It is easy to see that we will want each question to eliminate one opponent only, since after each elimination, the ratio t/s will be more and more rewarding ". But that doesnt say much. https://mirror.codeforces.com/contest/1293/problem/B