# 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