Question

Some kinds of candy (such as Sweet Tarts and Life Savers) come in rolls. You can eat the candy from either end of the roll, but you can't access a candy in the middle without going through one of the end pieces first.

These kinds of candy often have different flavors in the roll as well, which I've given a "flavor value" from 1-C (where "C" is the number of different flavors). Higher numbers are better.

Being a fan of delayed gratification, I've decided to "score" the order in which I eat a roll of candy by giving myself a score of (candy value * order in which I eat it) for each piece. I then want to maximize my score.

So, for example, suppose I had a roll with values: 1,2,3,4,1,2,3,4,1

Then if I ate from the left end each time, I'd score 1x1 + 2x2 + 3x3 + 4x4+ 1x5 + 2x6 + 3*7 + 4x8 + 1x9 = 109 points.

If I ate from the right end each time, I'd score 1x1+4x2+3x3+2x4+1x5+4x6+3x7+2x8+1x9 = 101 points

If I alternated eating from the left and right ends (starting on the left), I'd score 1x1+1x2+2x3+4x4+3x5+3x6+4x7+2x8+1x9 = 111 points

(The best score you can get is 121 points. Can you see how?)

a. Give an example of a roll where the greedy strategy of "Eat the available candy that has the lowest score" will not give the optimal answer.

b. Design a dynamic programming recurrence to solve this problem.

c. If you implement your recurrence in part b efficiently, what is your worst-case Big-O performance?

Answer 1

1. Consider the case where the array is 4 1 2 3 4, here for the first choice you can choose either of the 4 when you are using the greedy strategy, but the catch is, when you choose the first 4 you get the maximum value. because if you chose the first 4 you will have the next choice between 1 and 4 and then you can choose 1 and proceed, but if you choose the last 4 you will have the next choice as 3 or 4 so eventually it will give the wrong answer.

Using the greedy approach the answer when you choose the first 4 is 1*4 + 1*2 + 2*3 + 3*4 + 4*5 = 44 and when you choose the last 4 the answer is: 1*4 + 2*3 + 3*2 + 4*1 + 5*4 = 40. which is wrong.

2. The recurrence relation for the Dynamic programming solution is

DPst en cnt cnt DPst+1en cmt 1, 1 cnt1) alen cnt DP stlen max ast

for a current state with the starting point as st, ending point as en and the number of selected items till now is cnt.

Let us see how the recurrence works, suppose you are at some index st from the front and en from the back and you have selected cnt elements till now, you can either select the first element and call for DP[st+1][en][cnt+1] or you could select the last element and call for DP[st][en-1][cnt+1]

3. The worst case time complexity of the recurrence relation is O(N) since we are only using one recurrence call to the next cnt. The space complexity of the code is O(N^3).

If the answer helped, please upvote and in case of any doubts post a comment.

Here is the C++ code i used to test if my recurrence works right or not.

#include<iostream> #include<math.h> using namespace std; 1 2 3 int dp[100][100][100]; int a[100]; 6 int findMaxScore ( int cnt, int st, int en){ // if the value has been previously calculated use it if(dp[st][en][cnt] != -1) return dp[st][en][cnt]; // if only one element is present if (st==en) return cnt * 9 10 11 a[st]; 12 // otherwise recur for increased cnt 13 return dp[st][en][cnt] = max(a[st]*cnt + findMaxScore(cnt+1, st+1, en), a[en]*cnt + 14 findMaxScore(cnt+1, st, en-1));|| 15 } int main() { // intialise the array used to store the answers during memoization for (int i =0;i<100 ; i++) for(int j =0;j<100;j++) 16 17 18 19 20 for(int k =0;k<100;k++) dp[i] [j][k] = -1; 21 22 //n indicates the number of elements in the array int n 23 24 cin n; 25 // input the requires array for (int i=0;i<n;i++) cin >» a[i]; int st = 0, en = n-1; cout << findMaxScore(1, st, en); 26 27 28 29 30 return 0; 31

Input

12 3 4 1 2 3 41

Output:

Output: 121

Code:

#include<iostream>
#include<math.h>
using namespace std;

int dp[100][100][100];
int a[100];

int findMaxScore(int cnt, int st, int en){
// if the value has been previously calculated use it
if(dp[st][en][cnt] != -1) return dp[st][en][cnt];
// if only one element is present
if(st==en) return cnt * a[st];
// otherwise recur for increased cnt
return dp[st][en][cnt] = max(a[st]*cnt + findMaxScore(cnt+1, st+1, en), a[en]*cnt +
                                                                   findMaxScore(cnt+1, st, en-1));
}
int main() {
// intialise the array used to store the answers during memoization
for(int i =0;i<100;i++)
for(int j =0;j<100;j++)
for(int k =0;k<100;k++)
dp[i][j][k] = -1;
// n indicates the number of elements in the array
int n;
cin >> n;
// input the requires array
for(int i=0;i<n;i++) cin >> a[i];
int st = 0, en = n-1;
cout << findMaxScore(1, st, en);
return 0;
}