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

boyjava
New poster
Posts: 6
Joined: Mon Oct 06, 2003 7:29 pm

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

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am
The same question...
Nice problem, btw.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
Have you considered that values can be negative? Also, if a value is 2^31-1, you'll have to take the value mod d before adding anything in order not to get overflow. Other than that, I can't think of anything tricky.

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:
Does that mean that you guys see problem 10616 in the problemset?
The more contests are held, the happier I am.

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am
Well, we'll see it very soon

boyjava
New poster
Posts: 6
Joined: Mon Oct 06, 2003 7:29 pm
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
Herbert M. Duarte

subbu
New poster
Posts: 28
Joined: Fri May 30, 2003 12:47 am
hey
Did u consider that modulo of a negative number is negative.

I made this mistake, using modulo of a negative number in
a array index.

good luk.

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:
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
My program output following result:

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
``````
[/code]

boyjava
New poster
Posts: 6
Joined: Mon Oct 06, 2003 7:29 pm
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

boyjava
New poster
Posts: 6
Joined: Mon Oct 06, 2003 7:29 pm
I got accepted with only that change.

Thanks!

Herbert M. Duarte

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:
boyjava wrote:I got accepted with only that change.
Hi boyjava,
do you pls explain your dynamic approach???
i tried, but failed.

L I M O N

boyjava
New poster
Posts: 6
Joined: Mon Oct 06, 2003 7:29 pm
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

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

I had some overflows that caused the error. Thanks mf.
Last edited by Jan on Mon Aug 21, 2006 4:08 am, edited 2 times in total.
Ami ekhono shopno dekhi...
HomePage

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
I disagree. In the first query of 8th test case, D=5, M=2, and list of numbers is {2147483647, 2147483647, 2147483647, 2, -2147483648}.
All these numbers are congruent to 2 (mod 5), so sum of any two of them must be congruent to 4 (mod 5) and can't be divisible by 5. So 0 is the correct answer.

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
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?

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