## Programming Problem Solution 1

February 7, 2010 3 Comments

Change of plan. I figured, giving out questions is getting boring now. ๐ฆ Above that noone has asked any doubt regarding any question. Either my blog is read only by me or the people who read my blog are too intelligent :D. Anyways, for a change I decided to solve a problem for you in this post. So, what can be a better problem/concept to provide to you than Dynamic Programming . So here is a problem which I have solved using dynamic programming and now I will show you the steps and code for the same.

The problem can be found here.

I chose this problem because it is a very good example of a problem where a Greedy Algorithm seems to be sufficient but it’s not :). Now any standard textbook will provide you a decent enough background on how to go about solving a problem using DP. Following their legacy, I first propose to you to think of a recurrence relation for this problem and confirm to yourself whether that relation is valid or not.

I hope you have tried, if you have found it, awesum, if not, don’t worry I have the solution for you. The following program which solves the problem using the recurrence relation. It’s a recursive code, so obviously it’s uber low :). You can figure out the recurrence relation easily from the program. I hope you’ve got the idea of the solution. Now, the job is not done yet, we need to improve upon the solution.

#include<stdio.h> #include<stdlib.h> int N = 0, *arr; int max(int a,int b) { return a>b?a:b; } int fun(int day, int start, int end) { if (day > N) return 0; return max(fun(day+1,start+1,end) + day*arr[start],fun(day+1,start,end-1) + day*arr[end]); } int main() { scanf("%d",&N); arr = (int *)malloc(sizeof(int)*(N+1)); int start,end,day,i; for (i=1;i<=N;scanf("%d",&arr[i]),i++); start = 1;end = N;day = 1; printf("%d\n",fun(1,1,N)); return 0; }

The next step found in any standard textbook is to use Memoization. So we’ll do the process here too. You should find a way to store the precomputed results and use them for further calculations. Hope you will code it. The program which uses memoization for this problem. Have a look at it. Hope you get the idea :).

#include<stdio.h> #include<stdlib.h> int N = 0, *arr; int **table; int max(int a,int b) { return a>b?a:b; } int fun(int day, int start, int end) { if (day > N) return 0; if (start >= end && table[end][start] != 0) return table[end][start]; if ( start+1 <= N && table[start+1][end] == 0 ) table[start+1][end] = fun(day+1,start+1,end); if (end-1 >= 0 && table[start][end-1] == 0 ) table[start][end-1] = fun(day+1,start,end-1); return max(table[start+1][end] + day*arr[start],table[start][end-1] + day*arr[end]); } int main() { scanf("%d",&N); arr = (int *)malloc(sizeof(int)*(N+1)); table = (int **)malloc(sizeof(int *)*(N+2)); int start,end,day,i,j; for (i=0;i<=N+1;i++) { *(table+i) = (int *)malloc(sizeof(int)*(N+2)); for (j=0;j<=N+1;j++) table[i][j]=0; } for (i=1;i<=N;scanf("%d",&arr[i]),i++); start = 1;end = N;day = 1; printf("%d\n",fun(1,1,N)); return 0; }

Now is the time *To Play THE GAME *. It’s DP time :). The last nail in the coffin??? We’ll see. Well by now you will have had an idea of how you are going to program this as a DP solution. Great !! go ahead. For newbies, try out. The DP code for this. Do notice the sizes of the codes I am providing, see how they change ๐

#include<stdio.h> #include<stdlib.h> int max(int a,int b) { return a>b?a:b; } int main() { int N; scanf("%d",&N); int arr[N+1],i,j, table[N+1][N+1],tmp=0; for (i=1;i<=N;scanf("%d",&arr[i]),i++); for (i=1;i<=N;i++) table[i][i] = arr[i] * N; for (i=1;i<N;i++) { tmp++; for (j=1 ;j+tmp <= N;j++) table[j][j+tmp] = max(table[j+1][j+tmp] + arr[j]*(N-tmp), table[j][j+tmp-1] + arr[j+tmp]*(N-tmp) ); } printf("%d\n",table[1][N]); return 0; }

Now what ?? Is the game over ??? Not yet, for geeks, the memoization and DP solution will get uploaded on spoj, but to get to the best timing, you still have to do something special. Think about how this code can be optimized. Notice the way the table is being filled by the DP solution and which part of the table is being used to fill an entry in the table. Take some time to think. Just a hint, it can be done in O(N) space only :). The following is my solution which is among the best which has been uploaded. It’s really fast :P. Analyze this, the pattern how the table has been filled was exploited to use only O(N) space rahter than O(N^2) space.

#include<stdio.h> #include<stdlib.h> int max(int a,int b) { return a>b?a:b; } int main() { int N; scanf("%d",&N); int arr[N+1],i,j,table[N+1],tmp=0; for (i=1;i<=N;scanf("%d",&arr[i]),i++); for (i=1;i<=N;i++) table[i] = arr[i] * N; for (i=1; i < N; i++) { tmp++; for (j=1;j <= N-i ;j++) table[j] = max(table[j+1] + arr[j]*(N-tmp), table[j] + arr[j+tmp ]*(N-tmp)); } printf("%d\n",table[1]); return 0; }

Hope you geeks had a good time.

Do post comments for anything or just compliments ๐

## Recent Activity