PRDTPAIN - Editorial

editorial
, , , , ,
1

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

f(x,y,z)=(A_x-A_y)\cdot(A_y-A_z)\\ \qquad \le (A_l-A_y)\cdot(A_y-A_z) = f(l,y,z)

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

O(N^2\log N)

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

2

Also we can do ternary search to find the optimal value of k

2 Likes
3

can be done in O(N^2)
https://www.codechef.com/viewsolution/54149672

2 Likes
4

maximum value of (a-b).(b-c) is achieved when c = (a+c)/2

I think it should be when b = (a+c)/2

7 Likes
5

I was doing this way too and my code is almost kinda same but got WA…maybe missed something

6

The complexity is definitely more than O(N^2) but less than O(N^3)

When idx is incremented, it will meet the max value somewhere in middle of i → j and thats why the loop will never run for O(N) which makes the complexity less than O(N^3)

Nice solution though

7

for something like [1,2,2,2,11,21], your k won’t move further than the first occurrence of 2, so put in an extra condition such that it’ll skip all the duplicated elements.

1 Like
8

I don’t think it runs worse than quadratic time, or am I missing something?

9

gotcha thanx

1 Like
10

Can anyone share why is maximal value for (a−b)⋅(b−c) is at c = (a + b)/2. Is there any proof of it being convex? Could understand why these properties will hold true for all cases

1 Like
11

I don’t know if this proof is valid or not, but I get this intuition
(a-b)*(b-c) = ab + bc - b²
which can be written as
b(a+c-b)
and since a and c is constant for a given set that is first and last value of that subset
suppose
a+b = x
we can write the above equation as
b(x-b)
now we’ve to maximze this equation for our answer
and as we know that the product of two numbers the maximum value exist near their square or we can say when both the numbers are equal
then
b must be equal or closest to (x-b)
b = x-b
b = x/2
b = (a+b)/2
or b tends to (a+b)/2

2 Likes
12

Can someone plz explain how for n=6000,n^2logn will work. Won’t it give TLE?

13

You can try a visualization like this to get the basic idea plot (1-x) * (x-10) - Wolfram|Alpha

2 Likes
14

(a-b)*(b-c) is (ab - ac +bc - b^2)

15

Yeah ,what yo said is right ,in the editorial also they have mentioned the same thing , see the para f(l,k,r) , there they said said that the condition is put on Ak , so it can be understood

16

I tried to solve it using dp and i am getting right answer for a lot of sample cases but the judge is showing me wrong answer. Can anyone tell me a few corner cases or maybe if something is wrong with my approach?
Link to my solution:
my submission
Even this is giving wrong answer
Solution 2:
My submission2

17

My code was right with n^2 time complexity.
But language was Python. TLE - 5.1 sec.
I just changed to Pypy AC - 0.3 second.

Learning: Never submit your python code with python submit it using the pypy.

Link of solution

18

Consider the function f(x)=(a-x)(x-b) It is understood that when x is between a and b, f>0. Now f can be rearranged as - f(x) = \left (\dfrac{a-b}{2}\right)^2-\left(x-\left(\dfrac{a+b}{2}\right)\right)^2. Now you can see that, closer x is from \left(\dfrac{a+b}{2}\right), the larger is the value of f.

19

Can you please share your approach with ternary search.
Isn’t ternary search applicable only to unimodal functions (that is first strictly increasing and then maxima and then strictly decreasing OR first strictly decreasing and then minima and then strictly increasing)?
Here this condition is not satisfied because of duplicate entries.

22

Did anyone manage to do this problem in python? My submissions are always getting time limit exceeded even with binary search
my solution: www.codechef.com/viewsolution/54154238