10616 - Divisible Group Sums

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

Moderator: Board moderators

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

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

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

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.

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.
Ami ekhono shopno dekhi...
HomePage

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

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 :)
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

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

I have sent you a pm.
Ami ekhono shopno dekhi...
HomePage

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

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 :lol:
thanks in Advance
Arsalan
Last edited by arsalan_mousavian on Fri Sep 22, 2006 12:17 am, edited 1 time in total.
In being unlucky I have the record.

MajidIust
New poster
Posts: 4
Joined: Sun Jul 10, 2005 9:19 pm
Contact:

10616

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
New poster
Posts: 2
Joined: Tue Jun 21, 2011 12:20 pm

Re: 10616 - Divisible Group Sums

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
New poster
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

Re: 10616 - Divisible Group Sums

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10616 - Divisible Group Sums

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
Check input and AC output for thousands of problems on uDebug!

AhmadKhatar
New poster
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

Re: 10616 - Divisible Group Sums

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

Thank you for your help!
I got AC!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10616 - Divisible Group Sums

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

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
Check input and AC output for thousands of problems on uDebug!

dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

Re: 10616 - Divisible Group Sums

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
Life shouldn't be null.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10616 - Divisible Group Sums

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

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
Check input and AC output for thousands of problems on uDebug!

tamim1382csedu19
New poster
Posts: 18
Joined: Mon Jun 03, 2013 5:09 pm

Re: 10616 - Divisible Group Sums

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10616 - Divisible Group Sums

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

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
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 106 (10600-10699)”