## 10943 - How do you add?

Moderator: Board moderators

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

### recursion - memoization

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
On the first sight, the memset part looks wrong to me.
Replace it with memset(cache, -1, sizeof(cache));

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am
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
Contact:

### Re: recursion - memoization

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``

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

### Re: recursion - memoization

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>

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:
thanks for the i\o
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

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
Contact:
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?

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.