Page 3 of 3

recursion - memoization

Posted: Thu Jan 12, 2006 10:56 am
by smilitude
i tried to solve it using recursion and dp;
whats wrong with my code? is it my formulation , is my formulation wrong? this is a small code, i hope someone will answer soon...

Code: Select all

/* 
 * 10943 how do you add?
 * submission 1 WA
 * code finished at 2:20pm on dec25, 05
 *
 * this is a perfect example for memoization
 *
 */

#include <stdio.h>
#include <string.h>

long cache[105][105];

long sum(int N, int K) {
	int i;
	long summ=0;

	if(cache[N][K]!=-1) return cache[N][K];
	if(N==0||K==0) return 1;
	if(K==1) return N;
	if(K==2) return N+1;
	
	for(i=0;i<=N;i++) 
		summ+=sum(N-i,K-1)%1000000;
	cache[N][K]=summ;	
return summ;
}

int main() {
	int N,K;
	int i;
	for(i=0;i<101;i++)
 		memset(cache,-1,sizeof(cache[0])*101);
	while(scanf("%d %d",&N,&K)==2) {
		if(!N && !K) break;
		printf("%ld\n",sum(N,K)%1000000 );
	}
return 0;
}

Posted: Thu Jan 12, 2006 11:32 am
by misof
On the first sight, the memset part looks wrong to me.
Replace it with memset(cache, -1, sizeof(cache));

Posted: Thu Jan 12, 2006 7:50 pm
by smilitude
thanks, thanks for reply~! though i still have WA...

Re: recursion - memoization

Posted: Fri Jan 13, 2006 8:48 am
by mamun
smilitude wrote:whats wrong with my code?
Ya, what's wrong? WA or TLE? I guess WA.
What should be the output for

Code: Select all

2 1

Re: recursion - memoization

Posted: Fri Jan 20, 2006 9:04 am
by smilitude
mamun wrote:
smilitude wrote:whats wrong with my code?
Ya, what's wrong? WA or TLE? I guess WA.
What should be the output for

Code: Select all

2 1
you are so helping mamun bhai!
thanks a lott!
i got ac, though i am regreting why didnt i notice that thing before?

Posted: Sun Oct 01, 2006 7:19 am
by vinay
thanks for the i\o :D

WA

Posted: Wed Jun 27, 2007 12:48 pm
by abhiramn

Code: Select all

#include<stdio.h>
int main()
{
	int dp[202][102],i,j;
	for(i=0;i<202;dp[i][0]=1,dp[i][1]=i,i++);
	for(i=1;i<202;i++)
		for(j=2;j<102;j++)
			dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%1000000;
	while(1)
	{
		scanf("%d%d",&i,&j);
		if(!i&&!j)
			break;
		printf("%d\n",dp[i+j-1][i]);
	}
	return 0;
}
WRONG ANSWER! I have tested this for all inputs on the forum. It gives correct output. Please tell me where the problem could be.

Posted: Wed Jun 27, 2007 10:43 pm
by Jan
Test the cases.

Input:

Code: Select all

2 1
2 2
0 0
Output:

Code: Select all

1
3
Hope these help.

Re: 10943 - How do you add?

Posted: Fri Mar 25, 2011 8:08 pm
by DD
This is a DP problem, and my recurrence relation formula is way[N][K] = sigma 0<=i<=N (way[N-i][K-1])