Page 2 of 3

Posted: Wed Aug 30, 2006 7:44 pm
by DP
What algorithm have you use here?
Its a 0/1 knapsack problem.

Posted: Wed Aug 30, 2006 8:23 pm
by Jan
Kallol, your code is alright. But you are not considering negative numbers. You have used two reminder operations.

Code: Select all

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.

Posted: Thu Aug 31, 2006 8:11 am
by Kallol
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 :)

Posted: Thu Aug 31, 2006 6:46 pm
by Jan
I have sent you a pm.

Posted: Thu Sep 14, 2006 1:16 am
by arsalan_mousavian
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 :lol:
thanks in Advance
Arsalan

10616

Posted: Fri Sep 15, 2006 2:55 pm
by MajidIust
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.

Re: 10616 - Divisible Group Sums

Posted: Thu Sep 15, 2011 9:45 pm
by puigy1
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;
          }     
    
    }
}

Re: 10616 - Divisible Group Sums

Posted: Sat Aug 11, 2012 6:08 pm
by AhmadKhatar
Hi!
I get Runtime Error for the problem. I don't know the reason.
Could anybody help me?
Thanks in advance! :D

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 ];
					}
				}
			}
		}
	}
}

Re: 10616 - Divisible Group Sums

Posted: Tue Aug 14, 2012 12:12 am
by brianfry713
10 4
10000000
-10000000
3
4
5
6
7
8
9
10
1 1
1 10
20 1
20 10
0 0

Re: 10616 - Divisible Group Sums

Posted: Tue Aug 14, 2012 3:05 am
by AhmadKhatar
Thank you for your help!
I got AC!

Re: 10616 - Divisible Group Sums

Posted: Sun Sep 30, 2012 9:01 am
by brianfry713
Input:

Code: Select all

134 4
1270216262
1191391529
812669700
553475508
445349752
1344887256
730417256
1812158119
147699711
880268351
1889772843
686078705
2105754108
182546393
1949118330
220137366
1979932169
1089957932
1873226917
715669847
1486937972
1196032868
777206980
68706223
1843638549
212567592
1883488164
964776169
928126551
1301950427
1992516190
1426542624
849040635
941604920
1400427944
1994719310
2038269862
659998484
1280937363
1681643301
725914710
1729267236
2023351876
142750431
1840579929
2098560397
1910500675
1170970491
1856224190
983059344
1718458134
1876268425
1764841629
398844030
185252727
1370429126
502141743
993687334
15934104
1363674760
904629749
2047965620
451230256
2084670932
561035572
1840531613
1248402490
1518954509
614127119
683337405
1382875695
1843654049
1436430327
951656719
120033497
1669566824
1277092596
219218649
643287356
2041654184
1429623093
2035222245
1888581007
1505099306
807426509
1317442754
1853580352
292425665
944216783
589638738
401170801
1086979690
1225161330
1444887337
1339228195
131636656
1182095963
1211082011
1152299427
223840042
1287487106
593400968
735206212
1589759001
2069834510
668882480
808284658
1201886571
1014983331
2086000814
1361784847
761170564
801013197
730103625
5748438
1576460931
1267998018
1287998487
1883570151
659169187
28409913
2145324179
1148026995
1783671750
1994411750
6364913
968295562
1559931134
653962273
2011243547
241418521
699304830
261159140
1968925557
7 9
18 4
14 9
19 9
0 0
AC output:

Code: Select all

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

Re: 10616 - Divisible Group Sums

Posted: Sat Aug 03, 2013 11:25 am
by dibery
input:

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

output:
SET 1:
QUERY 1: 3

Re: 10616 - Divisible Group Sums

Posted: Wed Sep 04, 2013 3:06 am
by brianfry713
Input:

Code: Select all

5 2
-1
-2
-3
-4
-5
1 1
2 1
0 0
AC output:

Code: Select all

SET 1:
QUERY 1: 5
QUERY 2: 2

Re: 10616 - Divisible Group Sums

Posted: Mon Sep 23, 2013 6:51 pm
by tamim1382csedu19
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;
}

}

Re: 10616 - Divisible Group Sums

Posted: Fri Oct 11, 2013 2:19 am
by brianfry713
Input:

Code: Select all

36 8
768
910
-326
57
861
474
-128
-187
890
-989
248
-664
24
-450
473
-459
117
886
-936
-137
-212
-539
-585
-761
177
-40
-486
-67
720
609
447
487
518
679
-899
378
1 2
9 8
6 8
11 10
17 1
7 4
5 5
5 7
0 0
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