10616 - Divisible Group Sums
Moderator: Board moderators
Kallol, your code is alright. But you are not considering negative numbers. You have used two reminder operations.
I think you will get Accpeted. Good luck.
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;
Ami ekhono shopno dekhi...
HomePage
HomePage
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
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
CSE,BUET
Bangladesh
- arsalan_mousavian
- Experienced poster
- Posts: 111
- Joined: Mon Jan 09, 2006 6:19 pm
- Location: Tehran, Iran
- Contact:
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
EDIT :i got AC , and i don't need any IO anymore

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.
10616
my result for all test cases in this thread is true.
but i get wrong answer.
Can anyone explain me ,why?
So thanks.
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;
}
}
Re: 10616 - Divisible Group Sums
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!
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;
}
}
}
-
- New poster
- Posts: 28
- Joined: Fri Mar 30, 2012 12:57 am
Re: 10616 - Divisible Group Sums
Hi!
I get Runtime Error for the problem. I don't know the reason.
Could anybody help me?
Thanks in advance!
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 ];
}
}
}
}
}
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10616 - Divisible Group Sums
10 4
10000000
-10000000
3
4
5
6
7
8
9
10
1 1
1 10
20 1
20 10
0 0
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!
-
- New poster
- Posts: 28
- Joined: Fri Mar 30, 2012 12:57 am
Re: 10616 - Divisible Group Sums
Thank you for your help!
I got AC!
I got AC!
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10616 - Divisible Group Sums
Input:AC output:
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
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!
Re: 10616 - Divisible Group Sums
input:
6 1
-1 -2 -3 -4 -5 -6
5 2
output:
SET 1:
QUERY 1: 3
6 1
-1 -2 -3 -4 -5 -6
5 2
output:
SET 1:
QUERY 1: 3
Life shouldn't be null.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10616 - Divisible Group Sums
Input:AC output:
Code: Select all
5 2
-1
-2
-3
-4
-5
1 1
2 1
0 0
Code: Select all
SET 1:
QUERY 1: 5
QUERY 2: 2
Check input and AC output for thousands of problems on uDebug!
-
- New poster
- Posts: 18
- Joined: Mon Jun 03, 2013 5:09 pm
Re: 10616 - Divisible Group Sums
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;
}
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10616 - Divisible Group Sums
Input:AC output:
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
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!