PROBLEM LINK:
Contest - Division 3
Contest - Division 2
Contest - Division 1
DIFFICULTY:
EASY
PREREQUISITES:
AM-GM Inequality, Binary Search
PROBLEM:
The weight of an array B is defined as \max((B_i-B_j)\cdot(B_j-B_k)) over all valid indices i,j and k.
Given a sorted array A of size N, determine the sum of the weights of all subarrays (whose length is \ge 3) of A.
EXPLANATION:
Notation: Let f(x,y,z) represent (A_x-A_y)\cdot(A_y-A_z).
The constraints’ immediately tells us that a quadratic-time solution is feasible. That is, we can compute the weight of every subarray of A separately, and then add them together.
How do we compute the weight of the subarray A[l..r]?
Claim: The weight of subarray A[l..r] is equal to f(l,k,r) for some optimal k\ (l<k<r).
Proof
Recall that array A is sorted, and therefore A_l\le \dots\le A_r.
Consider some x,y,z\ (l\le x,y,z\le r) such that f(x,y,z) is maximal over all possible triplets. Clearly, x<y<z or x>y>z (otherwise, the value of f(x,y,z) will be non-positive).
Without loss of generality, assume x<y<z.
Observe that f(x,y,z)\le f(l,y,z)\le f(l,y,r).
How?
Since A_l\le A_x, it can be easily verified that
We may similarly show that f(l,y,z)\le f(l,y,r).
Thus we have the triplet (l,k,r) where k=y, which is no worse than the optimal triplet (x,y,z). Therefore proved.
All we are left to do now is find the optimal value of k. AM-GM inequality tells us that the maximum value of (a-b)\cdot(b-c) is achieved when b=\frac{a+c}{2}, decreasing quadratically as b moves away from this value.
Therefore, we want to find a valid index k such that A_k is closest to the value \frac{A_l+A_r}{2}, which can be done efficiently using binary search (std::upper_bound
in C++
).
To summarise - for each valid subarray A[l..r], determine the optimal k\ (l<k<r) in O(\log(r-l)) using binary search, and add f(l,k,r) to the total answer.
TIME COMPLEXITY:
For each subarray, calculating optimal k takes O(\log N). Since there are \approx N^2 subarrays of A, the total time complexity is therefore
per test case.
SOLUTIONS:
Editorialist’s solution can be found here
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
- 1
- 2
- 3
- 4
- 5
0 voters