1213 - Sum of Different Primes

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

Moderator: Board moderators

Post Reply
dhruba07
New poster
Posts: 20
Joined: Tue May 21, 2013 9:02 pm
Location: BUET

Re: 1213 - Sum of Different Primes

Post by dhruba07 » Wed Apr 08, 2015 5:54 pm

I am getting time limit.I am doing recursive dp.Any help would be appreciated.

Code: Select all

#include <bits/stdc++.h>

using namespace std;

#define _CRT_SECURE_NO_DEPRECATE

typedef long long		ll ;
typedef vector <int> 		vi ;
typedef pair <int, int>		ii ;
typedef vector <ii>		vii;
typedef set <int>		si ;
typedef map <string,int>	msi; 

#define REP(i,a,b) \
		for (int i = int (a) ; i <= int (b) ; i++) // a to b , i is local 
#define TRvi(c,it)  \
		for (vi::iterator it = (c).begin () ; it != (c).end () ; it++)
#define TRvii(c,it)  \
		for (vii::iterator it = (c).begin () ;it !=(c).end () ;it++) 
#define TRmsi(c,it)  \
		for (msi::iterator it = (c).begin () ;it != (c).end () ; it++)

#define INF 2000000000 // 2 billion
#define MEMSET_INF 127 // about 2B 
#define MEMSET_HALF_INF 63 // about 1B
//memset (dist, MEMSET_INF , sizeof dist) ;//useful to initialise shortest path distance
////memset (dp_memo, -1 ,sizeof dp_memo) ; // useful to initialise Dp memoization  table
////memset (arr, 0 ,sizeof arr); //useful to clear array of integers
#define DFS_WHITE -1
#define DFS_BLACK 1
#define DFS_GRAY 2
// project euler : 504458-5s4ADvk3PVARbBTSz7iSgq2XlyLMjcs00BOE0Bme
ll _sieve_size;
bitset<1200> bs; // 10^7 + small extra bits should be enough for most prime related problem
vi arr; //compact list of primes in form of vector <int>

void sieve(ll upperbound) // create a list of primes in [0,....upperbound]
{
    _sieve_size=upperbound+1 ; // add 1 to include upperbound;
    bs.reset(); // set all numbers to 0
    bs.flip(); // set all numbers to 1
    bs.set(0,false) ; 
    bs.set(1,false) ; // except index 0 and 1
    for(ll i=2;i<=_sieve_size;i+=1)
    {
        if(bs.test((size_t)i))
        {
            //cross out multiples of i starting from i*i !
            for(ll j=i*i;j<=_sieve_size;j+=i)
                    bs.set((size_t)j,false);
            arr.push_back((int)i);
        }
    }
}
int n,k,dp[188][1121][15];
int knapsack(int id,int sum,int taken)
{
	if(dp[id][sum][taken]!=-1)
	{
		return dp[id][sum][taken];
	}
	else {
		if(sum==0)
		{
			if(taken==k)
				return 1;
			else return 0;
		}
		else if(taken==k)
		{
			if(sum==0)
				return 1;
			else return 0;
		}
		else if(id==(int)arr.size())
		{
			if(sum==0&&taken==k)
			{
				return 1;
			}
			else return 0;
		}
		else if(id+(k-taken)>187)
		{
			return 0;
		}
		else if(sum-arr[id]<0)
		{
			return dp[id][sum][taken]=0;
		}
		else{
			dp[id][sum][taken]=0+knapsack(id+1,sum,taken)+knapsack(id+1,sum-arr[id],taken+1);
			return dp[id][sum][taken];
		}
	}
}
 
int
main ( int argc, char *argv[] )
{	
	sieve(1120);
	while(scanf("%d%d",&n,&k)==2)
	{
		if(n==0&&k==0) break;
		memset(dp,-1,sizeof dp);
		int ans=knapsack(0,n,0);
		printf("%d\n",ans);
	}
	return EXIT_SUCCESS;
}				/* ------
Accept who you are :)

coder.tanvir
New poster
Posts: 11
Joined: Mon Mar 09, 2015 10:30 am

Re: 1213 - Sum of Different Primes

Post by coder.tanvir » Wed Jul 22, 2015 3:10 am

try to avoid memset :)

Post Reply

Return to “Volume 12 (1200-1299)”