## 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

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

### Re: 10616 - Divisible Group Sums

thank u brianfry. AC

d3nd0h
New poster
Posts: 8
Joined: Sun Nov 03, 2013 3:39 am

### Re: 10616 - Divisible Group Sums

Can someone help me what's wrong with my code?

Code: Select all

``````#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;

int n,d,m,q,x=0;
long long in[250],memo[250][25][15];

long long div(int i,int rem,int sum){
//printf("%d %d %d\n",i,rem,sum);
if(i==n+1||rem==-1)return 0;
if(sum==0&&rem==0)return 1;
if(memo[i][sum][rem]!=-1)return memo[i][sum][rem];
else return memo[i][sum][rem]=div(i+1,rem,sum)+div(i+1,rem-1,(sum+in[i])%d);
}

int main(){
while(scanf("%d%d",&n,&q),x++,n&&q){
for(int i=0;i<n;i++)scanf("%lld",&in[i]);

printf("SET %d:\n",x);
for(int i=1;i<=q;i++){
memset(memo,-1,sizeof memo);
scanf("%d%d",&d,&m);
printf("QUERY %d: %lld\n",i,div(0,m,0));
}
}
return 0;
}``````
I've tried all tc in the post, thanks in advance

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

### Re: 10616 - Divisible Group Sums

Input:

Code: Select all

``````6 7
299
-837
563
-985
316
380
13 1
18 1
14 2
17 6
18 3
1 6
7 5
12 3
-646
-801
-664
-856
307
-618
-267
-768
-341
589
954
-779
2 4
2 4
2 4
19 5
387
-833
-865
837
109
874
-979
-600
794
-35
-249
-853
164
-356
849
-972
26
-419
818
17 7
16 10
4 2
4 9
2 9
2 4
135
675
7 2
16 2
1 1
7 2
8 1
-764
692
-288
-736
-726
294
639
959
8 8
15 7
564
600
203
-425
349
-290
-625
-517
942
869
12
-719
235
-995
22
17 6
8 6
20 3
7 10
19 10
9 3
20 4
3 1
303
244
-48
5 2
7 2
-810
160
679
202
442
-530
-236
8 1
20 6
7 7
-35
205
846
-442
-975
-825
224
7 4
20 5
11 3
7 5
20 5
20 5
20 6
5 3
281
532
965
702
-70
7 3
19 3
8 2
0 0
``````
AC output:

Code: Select all

``````SET 1:
QUERY 1: 1
QUERY 2: 0
QUERY 3: 1
QUERY 4: 0
QUERY 5: 2
QUERY 6: 1
QUERY 7: 2
SET 2:
QUERY 1: 255
QUERY 2: 255
QUERY 3: 255
SET 3:
QUERY 1: 3076
QUERY 2: 5738
QUERY 3: 42
QUERY 4: 23056
QUERY 5: 46112
SET 4:
QUERY 1: 0
QUERY 2: 0
QUERY 3: 2
QUERY 4: 0
SET 5:
QUERY 1: 0
SET 6:
QUERY 1: 285
QUERY 2: 633
QUERY 3: 27
QUERY 4: 414
QUERY 5: 172
QUERY 6: 56
QUERY 7: 65
SET 7:
QUERY 1: 1
SET 8:
QUERY 1: 1
QUERY 2: 0
SET 9:
QUERY 1: 7
QUERY 2: 0
QUERY 3: 4
QUERY 4: 5
QUERY 5: 0
QUERY 6: 0
QUERY 7: 1
SET 10:
QUERY 1: 2
QUERY 2: 0
QUERY 3: 1
``````
Check input and AC output for thousands of problems on uDebug!

nbacool2
New poster
Posts: 24
Joined: Fri Jul 25, 2014 4:31 pm

### Re: 10616 - Divisible Group Sums

Can someone tell me why I'm getting WA?
I compared my output to the others' and 90% of the queris are the same but for some reason the others differ when I'm using the right reccurence
f(pos, used, reminder) = f(pos+1, used, reminder) + f(pos+1, used-1, (reminder + numbers[pos]) % D) where I use the mod function suggested by a pervious post.
CODE:

Code: Select all

``````#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long int i64;
int N, Q, D, M;
i64 DP[300][20][45];
i64 numbers[300];
i64 mod(i64 number, int mod)
{
if(number >= 0) return number % mod;
return (mod + (number % mod)) % mod;
}
i64 rec(int pos, int M, int remD)
{
if(M == 0 && remD == 0) return 1;
if(pos == N || M == 0) return 0;
i64 &ans = DP[pos][M][remD];
if(ans != -1) return ans;
ans = rec(pos+1, M-1, mod(remD + numbers[pos], D)) + rec(pos+1, M, remD);
return ans;
}
{
memset(DP, -1, sizeof DP);
for(int i = 0; i < N; ++i) cin >> numbers[i];
for(int i = 0; i < Q; ++i)
{
cin >> D >> M;
i64 res = rec(0, M, 0);
cout<<"QUERY: "<<i+1<<": "<<res<<'\n';
}
}
int main()
{
ios::sync_with_stdio(false);
int counter = 1;
while(true)
{
cin >> N >> Q;
if(N == 0 && Q == 0) break;
cout<<"SET: "<<counter<<'\n';
++counter;
}
return 0;
}``````

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10616 - Divisible Group Sums

You forget to memset array DP after each query. It must be

Code: Select all

``````void read()
{
for(int i = 0; i < N; ++i) cin >> numbers[i];
for(int i = 0; i < Q; ++i)
{
memset(DP, -1, sizeof DP);
cin >> D >> M;
i64 res = rec(0, M, 0);
cout<<"QUERY: "<<i+1<<": "<<res<<'\n';
}
}``````
My advice to you -> always copy/paste output format from sample. Look at colons in sample's output .

Code: Select all

``````SET 1:
QUERY 1: 2``````
And colons in your output format

Code: Select all

``````cout<<"SET: "<<counter<<'\n';
..
cout<<"QUERY: "<<i+1<<": "<<res<<'\n';``````
Don't forget to remove your code after getting accepted.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

nbacool2
New poster
Posts: 24
Joined: Fri Jul 25, 2014 4:31 pm

### Re: 10616 - Divisible Group Sums

Thanks, man! Got AC . Damn, so stupid by me not to memset after every query and to mess up the output format Advice taken. But I just don't think I have to delete my solution because people can learn from it or find mistakes in their code. And there are other sites where you can copy/paste code just to get AC if that's your concern.

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10616 - Divisible Group Sums

I think learning can be done in many other ways.
It will be spoiler. Its my opinion.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

### Re: 10616 - Divisible Group Sums

Can someone plz tell me the algorithm for this problem ? Thanx in advance

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re:

DP wrote:What algorithm have you use here?
Its a 0/1 knapsack problem.
boyjava wrote:My approach was based on modular arithmetic property:
(a + b) mod m = a mod m + b mod m
After that, I only used the DP algorithm for the knapsack problem to calculate in how many ways one can build the sums of at most D-1, counting how many numbers I used in each sum. The answer is the number of sums 0 (mod D) with M numbers.

Herbert M. Duarte
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

Thanx lighted