10616 - Divisible Group Sums

[tamim1382csedu19]

thank u brianfry. AC

[d3nd0h]

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]

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

[nbacool2]

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;
}
void read()
{
    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;
        read();
    }
    return 0;
}

[lighted]

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.

[nbacool2]

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]

I think learning can be done in many other ways.
It will be spoiler. Its my opinion.

[richatibrewal]

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

[lighted]

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

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

[richatibrewal]

Thanx lighted