nil96
October 17, 2014, 8:29pm
1
qstn:COINS Problem - CodeChef
qstn look much simpler with recurrence relation
recurrence relation
lli oprtn(lli n)
{
if(n<2)
return 0;
lli ans=max(n, oprtn(n/2) + oprtn(n/3) +oprtn(n/4));// recurrence relation
if(ans>n)
return ans;
else
return n;
}
it can be converted into DP easily by saving the following function
void work()
{
lli i;
learn[0]=0;
learn[1]=1;
learn[2]=2;
learn[3]=3;
for(i=4;i<=1000000000;i++)
{
learn[4]=max(i,learn[i/2]+learn[i/3]+learn[i/4]);
}
}
however size of array is too large(10^9) to accommodate all solution now how to tackle this problem please help
An array of 10^5 to 10^6 will suffice…u dont need to store the higher values…they will not repeat as much…lower values will be encountered larger number of times…if u are unable to understand what i m trying to convey…then u can have a look at a few AC solns…
mm1991
October 17, 2014, 11:45pm
3
use the recursive solution with a map<int,int> instead of an array
nj96
June 2, 2015, 12:10am
4
I wrote this -
#include<stdio.h>
long divide (long x)
{
if ((x/2+x/3+x/4) >= x) return (divide (x/2) +divide (x/3) +divide (x/4)) ;
else return x;
}
int main()
{
long a;
while(scanf("%d",&a)!=EOF)
{
printf("%d\n",divide(a));
}
}
Even though it runs perfectly in my laptop it shows SIGSEGV in codechef
Use map if u know how to use them that will save u the memory problem