PROBLEM LINK:
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 : Invitation to IPC’s ICPC Preparatory Series Finals & Finals Mirror - Codeforces
Time Complexity: O(N)
TESTER’S SOLUTION:
Tester’s solution can be found here.