10616

DP · Post by DP » Wed Aug 30, 2006 7:44 pm

What algorithm have you use here?
Its a 0/1 knapsack problem.

Jan · Post by **Jan** » Wed Aug 30, 2006 8:23 pm

Kallol, your code is alright. But you are not considering negative numbers. You have used two reminder operations.

long long mod(long long a,long long b)
{
    long long c;

    if(a<b)
    {
        a=-a;
        c=a%b;
        c=b-c;
    }
    else
        c=a;
    return c%b;
}

//and use

if(mod((remainder+a[index]),d)==0)
//instead of if((remainder+a[index])%d==0)

//and use

int remainder2=mod((remainder+a[index]),d);
//instead of int remainder2=(remainder+a[index])%d;

I think you will get Accpeted. Good luck.

Kallol · Post by **Kallol** » Thu Aug 31, 2006 8:11 am

Thanx Jan !
Now I got AC.
Now, I understand the behaviour or negative numbers in modular operation. Thanx for ur help.
Actually I was a little bit confused when to memoize something which is negative. Here we have a way to change the negative modulus to a positive number comparing it to a equivalent positive modulus which in pratical serves the same pupose.
But when I need to store a negative path length or negative sum or something like that , what sould be the proceedure? Because we cant use negative index for it . Hope, I could make u understand my problem.
Infact I am new in using DP, so I am asking you these questions . Hope u will not be bothered with it.
Thank u for helping me once again

Jan · Post by **Jan** » Thu Aug 31, 2006 6:46 pm

I have sent you a pm.

arsalan_mousavian · Post by **arsalan_mousavian** » Thu Sep 14, 2006 1:16 am

i 've got WA on this problem , and my program handles all the IO above , can someone post some tricky IO ?

EDIT :i got AC , and i don't need any IO anymore

thanks in Advance
Arsalan

MajidIust · Post by **MajidIust** » Fri Sep 15, 2006 2:55 pm

my result for all test cases in this thread is true.
but i get wrong answer.
Can anyone explain me ,why?

Code: Select all

#include <iostream>
#include <algorithm>
#define maxElement 202
#define maxSelect  12
#define maxDiv     21
using namespace std;
long long treasure[maxSelect][maxDiv][maxDiv];
int in[maxDiv];

void initial(int n)
{
    for(int i=0;i<12;i++)
        for(int j=0;j<=20;j++)
            fill(treasure[i][j],treasure[i][j] + maxDiv,0);
}
int main()
{
    int N,Q;
    long long tempIn,temp;
    int D,M;
    int index=0;
    cin >> N >> Q;
    while(N!=0 || Q!=0)
    {
        cout << "SET "<<++index<<endl;
        initial(N);
        for(int q=0;q<N;q++)
        {
            cin >> tempIn;
            for(int i=1;i<=20;i++)
            {
                if(tempIn < 0)
                {
                    temp = -tempIn;
                    temp = temp%i;
                    temp = i-temp;
                }
                else
                    temp = tempIn%i;        
                in[i] = temp;
            }
            for(int i=(q+1 > 12 ? 12 : q+1);i>=2;i--)
                {
                   for(int j=1;j<=20;j++)
                   {
                       for(int k=0;k<j;k++)
                       {
                           if(treasure[i-1][j][k])
                                treasure[i][j][(k + in[j])%j]+=treasure[i-1][j][k];
                       }
                   }
                }  
             for(int i=1;i<=20;i++)
                {
                    treasure[1][i][in[i]] ++;
                }
        }
        for(int y=1;y<=Q;y++)
        {
            cin >> D >> M;
            cout << "QUERY "<<y<<": "<<treasure[M][D][0]<<endl;
        }
        cin >> N >> Q;
    }
}

So thanks.

puigy1 · Post by **puigy1** » Thu Sep 15, 2011 9:45 pm

Hello! Can anyone tell me why I am getting a runtime error with this code? I've been looking at it for a long time and I can't find any access out of memory or anything similar.

Thank you very much!

Code: Select all

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector <vector <vector <long long> > > dp;
vector <vector <vector <bool> > > bl;
long long res (vector <int>& v, int i, int d, int m, int de){
    if (m==0){
       if (d>0) dp[i][m][d]=0LL;
       else dp[i][m][d]=1LL;
       bl[i][m][d]=true;
       return dp[i][m][d];
    }
    if (i>=v.size()) return 0LL;
    if (bl[i][m][d]) return dp[i][m][d]; 
    int a=d%de;
    a+=v[i]%de; 
    dp[i][m][d]=res(v,i+1,a%de,m-1,de);
    if (v.size()-i>m) dp[i][m][d]+=res(v,i+1,d%de,m,de);
    bl[i][m][d]=true;
    return dp[i][m][d];
}
int main (){
    int n,q;
    int set=1;
    while (cin >>n>>q and n>0 ){
          cout <<"SET "<<set<<":"<<endl;
          set++;
          vector <int> v (n);
          for (int i=0; i<n; i++)  cin >>v[i];
          int m,d;
          for (int i=0; i<q; i++){
              cin >>d>>m;
              m=min(m,n);
              vector <vector <vector <long long> > > aux (n+1, vector <vector <long long> > (m+1,vector <long long> (d,0LL)));
              vector <vector <vector <bool> > > aux2 (n+1, vector <vector <bool> > (m+1,vector <bool> (d,false)));
              dp=aux;
              bl=aux2;
              cout <<"QUERY "<<i+1<<": "<<res(v,0,0,m,d)<<endl;
          }     
    
    }
}

AhmadKhatar · Post by **AhmadKhatar** » Sat Aug 11, 2012 6:08 pm

Hi!
I get Runtime Error for the problem. I don't know the reason.
Could anybody help me?
Thanks in advance!

Code: Select all

#include <iostream>

using namespace std;

int n, q;
int a [ 200 ];
int d, m;
long long int mat [ 201 ][ 20 ][ 11 ];

void constrMat();

int main()
{
	int setNo = 1;

	cin >> n >> q;
	while ( !( n == 0 && q == 0 ) )
	{
		for ( int i = 0; i < n; i++ )
		{
			cin >> a[ i ];
		}

		cout << "SET " << setNo++ << ":" << endl;
		for ( int i = 0; i < q; i++ )
		{
			cin >> d >> m;
			cout << "QUERY " << i + 1 << ": ";
			constrMat();
			cout << mat[ n ][ 0 ][ m ] << endl;
		}

		cin >> n >> q;
	}

	return 0;
}

void constrMat()
{
	for ( int i = 0; i <= n; i++ )
	{
		for ( int j = 0; j < d; j++ )
		{
			for ( int k = 0; k <= m; k++ )
			{
				mat[ i ][ j ][ k ] = 0;
			}
		}
	}

	for ( int i = 1; i <= n; i++ )
	{
		for ( int ii = 0; ii <= i - 1; ii++ )
		{
			if ( a[ ii ] >= 0 )
			{
				mat[ i ][ a[ ii ] % d ][ 1 ]++;
			}
			else
			{
				if ( a[ ii ] % d == 0 )
				{
					mat[ i ][ 0 ][ 1 ]++;
				}
				else
				{
					mat[ i ][ (a[ ii ] % d) + d ][ 1 ]++;
				}
			}
		}
		for ( int k = 2; k <= min( m, i ); k++ )
		{
			for ( int j = 0; j < d; j++ )
			{
				if ( j >= a[ i - 1 ] )
				{
					mat[ i ][ j ][ k ] = mat[ i - 1 ][ j - a[ i - 1 ] ][ k - 1 ] + mat[ i - 1 ][ j ][ k ];
				}
				else
				{
					if ( (j - a[ i - 1 ])%d == 0 )
					{
						mat[ i ][ j ][ k ] = mat[ i - 1 ][ 0 ][ k - 1 ] + mat[ i - 1 ][ j ][ k ];
					}
					else
					{
						mat[ i ][ j ][ k ] = mat[ i - 1 ][ ((j - a[ i - 1 ])%d) + d ][ k - 1 ] + mat[ i - 1 ][ j ][ k ];
					}
				}
			}
		}
	}
}

brianfry713 · Post by **brianfry713** » Tue Aug 14, 2012 12:12 am

10 4
10000000
-10000000
3
4
5
6
7
8
9
10
1 1
1 10
20 1
20 10
0 0

AhmadKhatar · Post by **AhmadKhatar** » Tue Aug 14, 2012 3:05 am

Thank you for your help!
I got AC!

brianfry713 · Post by **brianfry713** » Sun Sep 30, 2012 9:01 am

Input:

Code: Select all

AC output:

Code: Select all

SET 1:
QUERY 1: 4167330016423
QUERY 2: 713315
QUERY 3: 2083664908197
QUERY 4: 1535332101829

dibery · Post by **dibery** » Sat Aug 03, 2013 11:25 am

input:

6 1
-1 -2 -3 -4 -5 -6
5 2

output:
SET 1:
QUERY 1: 3

brianfry713 · Post by **brianfry713** » Wed Sep 04, 2013 3:06 am

Input:

Code: Select all

AC output:

Code: Select all

SET 1:
QUERY 1: 5
QUERY 2: 2

tamim1382csedu19 · Post by **tamim1382csedu19** » Mon Sep 23, 2013 6:51 pm

My code matches all the sample I/O in the forum. Why I am still getting WA?

Code: Select all

#include <iostream>
#include <string.h>
#include <stdlib.h>
using namespace std;
long long int mod(long long int a,long long int b)
{
	long long int x = (a%b);
	return abs(x);

}
long long int m,q,d,A[205],cnt,n,dp[205][15][25];
long long int bt(long long int indx,long long int taken,long long int sum)
 {
		if(abs(sum)>d)
			sum = mod(sum,d);
		if(taken == m)
		{
			if(mod(sum,d) == 0)
				return 1;
			else
				return 0;
		}
		if( indx == n ) 
			return 0;
		if(dp[indx][taken][sum]!=(-1))
			return dp[indx][taken][sum];
		
		return dp[indx][taken][sum] = bt(indx+1,taken+1,sum+A[indx]) + bt(indx+1,taken,sum) ; 
}
int main()
{
	int set = 1;
	while(cin>>n>>q&&(n||q)){
	for(int i=0;i<n;++i)
		cin>>A[i];
	cout<<"SET "<<set<<":"<<endl;
	int query = 1;
	while(q--)
	{
		cin>>d>>m;
		memset(dp,-1,sizeof dp);
		cout<<"QUERY "<<query<<": ";
		cout<<bt(0,0,0)<<endl;
		++query;
	}

	++set;
}

}

brianfry713 · Post by **brianfry713** » Fri Oct 11, 2013 2:19 am

Input:

Code: Select all

AC output:

Code: Select all

SET 1:
QUERY 1: 630
QUERY 2: 3362227
QUERY 3: 5043633
QUERY 4: 23108010
QUERY 5: 2
QUERY 6: 8399
QUERY 7: 75405
QUERY 8: 1669530

UVa OJ Board

10616 - Divisible Group Sums

Re: 10616 - Divisible Group Sums

Re: 10616 - Divisible Group Sums

Re: 10616 - Divisible Group Sums

Re: 10616 - Divisible Group Sums

Re: 10616 - Divisible Group Sums

Re: 10616 - Divisible Group Sums

Re: 10616 - Divisible Group Sums

Re: 10616 - Divisible Group Sums

Re: 10616 - Divisible Group Sums