SVENGY - Editorial

PROBLEM LINK:

Practice

Contest

Author: Malvika Joshi

Tester: Sameer Gulati, Anurag Anand, Vaibhav Gosain

DIFFICULTY:

Medium

PREREQUISITES:

Greedy Algorithms

PROBLEM:

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.

EXPLANATION:

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[0]| or A[i] = -A[0] (if A[0]>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.

Credits : http://codeforces.com/blog/entry/47485?#comment-318760

Time Complexity: O(N)

TESTER’S SOLUTION:

Tester’s solution can be found here.

1 Like

Only one thing is missed here in the second condition

it should be A[i]| = |A[j]|, A[i] > 0 and A[j] < 0 because then only former is better ( costs less energy).

2 Likes