10616  Divisible Group Sums
Moderator: Board moderators
10616  Divisible Group Sums
Hello, everybody.
Can anyone tell me if there is any tricky input for this problem. I solved it using DP and tested it for a lot of different inputs, even invalid ones, and to me everything seemed right. I got frustated because it wasn't accepted during the contest.
Thanks.
Herbert M. Duarte
Can anyone tell me if there is any tricky input for this problem. I solved it using DP and tested it for a lot of different inputs, even invalid ones, and to me everything seemed right. I got frustated because it wasn't accepted during the contest.
Thanks.
Herbert M. Duarte

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 am

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 am
Hello, Per.
I have considered negative values and took the value of every number mod d. However, my implementation wasn't accepted . Could you please post the answer for the following input. Thanks a lot.
I have considered negative values and took the value of every number mod d. However, my implementation wasn't accepted . Could you please post the answer for the following input. Thanks a lot.
Herbert M. Duarte10 2
1
2
3
4
5
6
7
8
9
10
5 1
5 2
5 1
2
3
4
5
6
6 2
5 3
2
3
4
5
6
7 1
7 2
7 3
3 2
3
3
4
6 2
7 2
4 1
1
2
3
4
10 5
100 10
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
3 1
1
1
1
1 5
5 3
2147483647
2147483647
2147483647
2
2147483648
5 2
5 3
5 4
10 6
12
14
41
65
34
27
84
26
99
34
2 1
2 2
2 3
3 1
3 2
3 3
0 0

 Learning poster
 Posts: 63
 Joined: Mon Dec 22, 2003 5:05 am
 Location: Russia, Chelyabinsk
 Contact:
My program output following result:boyjava wrote:Hello, Per.
I have considered negative values and took the value of every number mod d. However, my implementation wasn't accepted . Could you please post the answer for the following input. Thanks a lot.
10 2
1
2
3
4
5
6
7
8
9
10
5 1
5 2
5 1
2
3
4
5
6
6 2
5 3
2
3
4
5
6
7 1
7 2
7 3
3 2
3
3
4
6 2
7 2
4 1
1
2
3
4
10 5
100 10
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
3 1
1
1
1
1 5
5 3
2147483647
2147483647
2147483647
2
2147483648
5 2
5 3
5 4
10 6
12
14
41
65
34
27
84
26
99
34
2 1
2 2
2 3
3 1
3 2
3 3
0 0
Code: Select all
SET 1:
QUERY 1: 2
QUERY 2: 9
SET 2:
QUERY 1: 1
SET 3:
QUERY 1: 0
QUERY 2: 2
QUERY 3: 1
SET 4:
QUERY 1: 1
QUERY 2: 2
SET 5:
QUERY 1: 0
SET 6:
QUERY 1: 100
QUERY 2: 4950
QUERY 3: 161700
QUERY 4: 3921225
QUERY 5: 75287520
QUERY 6: 1192052400
QUERY 7: 16007560800
QUERY 8: 186087894300
QUERY 9: 1902231808400
QUERY 10: 17310309456440
SET 7:
QUERY 1: 0
SET 8:
QUERY 1: 0
QUERY 2: 0
QUERY 3: 0
SET 9:
QUERY 1: 6
QUERY 2: 21
QUERY 3: 56
QUERY 4: 4
QUERY 5: 14
QUERY 6: 40
rotoZOOM, thank you for posting the answer for that input. My program produces the same output, but I believe it got WA because of the modulo of negative numbers (which I didn't realize it was negative)  thanks subbu for that. When they put the problem in the online judge, I will probably get an AC.
Thanks everybody.
Herbert M. Duarte
Thanks everybody.
Herbert M. Duarte
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 D1, 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 + 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 D1, 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
Hi !
I am getting WA in this problem. My code gives the exact output to the I/O s submitted here in this thread. I am little bit confused about the negative remainder. Can anyone explain me the behaviour of negative number in modular arithmatc? I am pasting here my code. I used DP with memoization. Exactly where and how should I change to get AC?
I am getting WA in this problem. My code gives the exact output to the I/O s submitted here in this thread. I am little bit confused about the negative remainder. Can anyone explain me the behaviour of negative number in modular arithmatc? I am pasting here my code. I used DP with memoization. Exactly where and how should I change to get AC?
Code: Select all
cut after ac
Last edited by Kallol on Thu Aug 31, 2006 8:13 am, edited 1 time in total.
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh
CSE,BUET
Bangladesh