Recurssion with Memoization

general
,
1

I have asked this question on editorial of problem but no one replied so I have to raise this question as a new topic on the forum.

Here is link to problem SEEDLING and its EDITORIAL

This is my recursive backtracking code for 17 points. It is giving me 17 points.
I call solve(0, 0, 0) in my main function

 
long solve(int i, int space, int profit) {

if (space > s)
return 0;

if (i == n) {
if (space <= s && profit > 0)
return 1;
else
return 0;
}

return (solve(i, space + a[i], profit + c[i] - b[i]) + solve(i + 1, space, profit));
}

I want to pass the next subtask. I thought to do with recurssion with memoization. But its giving me TLE. Can anyone help me?
Now I am calling solve(0, 0, 3500) in my main function with dp size = new long[60][60][7000];


long solve(int i, int space, int profit) {

if (space > s)
return 0;

if (i == n) {
if (space <= s && profit > 3500)
return 1;
else
return 0;
}

if (dp[i][space][profit] != 0)
return dp[i][space][profit];

return dp[i][space][profit] = (solve(i, space + a[i], profit + p[i]) + solve(i + 1, space, profit));
}

My Submission

1 Like
2

There is one major flaw which potentially costs a lot of time: 0 is a correct answer for a lot of entries in the dp array. But since you’ re checking for 0 in order to see if it’s already processed, you are calculating a lot of values multiple times.

Improvement: Initialize the dp-array with -1 and return values from dp if they are >=0.

This might be enough to pass task 2.

1 Like
3

@ceilks Thanks for your improvement to the solution. It did pass the second subtask. I didn’t know that “0” could cause soo much problem. Great Observation!

4

@ceilks I was watching your submission in this problem. There is one line in your code maxP = max(maxP, (s/a[i]+1)*(b[i]-c[i]));

Could you please explain your idea for Maximum Profit. I hope maxP stands for Maximum Profit.