NPL1701F - Editorial

PROBLEM LINK:

Practice

Contest

Author: vinod10

Tester: manjunath1996

Editorialist: vinod10

DIFFICULTY:

Medium

PREREQUISITES:

Knowledge of basic DP.

PROBLEM:

Given a sequence of N numbers, at every step a number from boundary is removed and cost associated with it is added in answer. We have to minimize the total cost.

QUICK EXPLANATION:

We keep a 3-D array dp[i][j][k], where [i,j] is the range for which we are solving the problem and k denotes positions of previously selected elements. With memoization, we solve this dp recursively.

EXPLANATION:

N4 approach :
You can use 4-D array dp[i][j][k][l], where [i,j] is the range, k denotes last element selected and l denotes second last element that was selected.

Now at each step you can either select ith element or jth element, so

dp[i][j][k][l] = min( A[i] * (A[k]+1) * (A[l]+2)+ dp[i+1][j][i][k] , A[j] * (A[k]+1) * (A[l]+2)+ dp[i][j-1][j][k])

N2 approach :
We actually don’t need to use 4-D array here, as there are only four possible value that last and second last number can take.

Assume we are currently solving for the range [i,j], then 4 possible positions for previously selected elements are :

i-1 and i-2

j+1 and j+2

i-1 and j+1

j+1 and i-1

These are the only 4 positions previous two elements can take as we are removing only boundary elements each time.
Hence a 3-D array, dp[i][j][4] can be used where [i,j] is range and third number shows positions of previously selected elements.

See the solution for more explanation.

AUTHOR’S SOLUTIONS:

Author’s solution can be found here.