Author: Malvika Joshi
There are N towns in a line. Distance between town i and j is abs(j-i). We want to go from town 0 to town N-1. From town i, we can jump to any town j > i and that costs (j-i)*A[i] + (j2 - i2)*A[i]2, where A is given as input. We want to find the minimum cost needed. N <= 10^5.
If you write cost function for path i->j->k and compare it with the cost function for path i->k you can see that the former is better (costs less energy) if and only if either |A[j]| < |A[i]| or |A[j]| = |A[i]| with A[i]>0.
From this observation it is quite easy to see that the optimal path would be greedy jumping from 0 to first i such that |A[i]| < |A| or A[i] = -A (if A>0) or directly to n-1 if there is no such i and then doing the same for i till we reach n - 1. Jumping greedily to n-1 solves the problem with O(N) complexity.
Time Complexity: O(N)
Tester’s solution can be found here.