10943 - How do you add?

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

recursion - memoization

Post by smilitude » Thu Jan 12, 2006 10:56 am

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;
}
fahim
#include <smile.h>

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Thu Jan 12, 2006 11:32 am

On the first sight, the memset part looks wrong to me.
Replace it with memset(cache, -1, sizeof(cache));

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Thu Jan 12, 2006 7:50 pm

thanks, thanks for reply~! though i still have WA...
fahim
#include <smile.h>

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Re: recursion - memoization

Post by mamun » Fri Jan 13, 2006 8:48 am

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

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Re: recursion - memoization

Post by smilitude » Fri Jan 20, 2006 9:04 am

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?
fahim
#include <smile.h>

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay » Sun Oct 01, 2006 7:19 am

thanks for the i\o :D
If I will myself do hashing, then who will do coding !!!

abhiramn
New poster
Posts: 29
Joined: Sat May 26, 2007 7:54 pm

WA

Post by abhiramn » Wed Jun 27, 2007 12:48 pm

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.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Jun 27, 2007 10:43 pm

Test the cases.

Input:

Code: Select all

2 1
2 2
0 0
Output:

Code: Select all

1
3
Hope these help.
Ami ekhono shopno dekhi...
HomePage

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10943 - How do you add?

Post by DD » Fri Mar 25, 2011 8:08 pm

This is a DP problem, and my recurrence relation formula is way[N][K] = sigma 0<=i<=N (way[N-i][K-1])
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Post Reply

Return to “Volume 109 (10900-10999)”