Page 1 of 3

10616 - Divisible Group Sums

Posted: Sat Jan 24, 2004 7:46 pm
by boyjava
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

Posted: Sat Jan 24, 2004 8:34 pm
by Dmytro Chernysh
The same question... :-)
Nice problem, btw.

Posted: Sat Jan 24, 2004 9:09 pm
by Per
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.

Posted: Sun Jan 25, 2004 7:45 pm
by alex[LSD]
Does that mean that you guys see problem 10616 in the problemset?

Posted: Sun Jan 25, 2004 7:49 pm
by Dmytro Chernysh
Well, we'll see it very soon ;-)

Posted: Mon Jan 26, 2004 4:26 am
by boyjava
Hello, Per.

I have considered negative values and took the value of every number mod d. However, my implementation wasn't accepted :cry: . 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

Posted: Mon Jan 26, 2004 5:21 am
by subbu
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.

Posted: Mon Jan 26, 2004 8:32 am
by rotoZOOM
boyjava wrote:Hello, Per.

I have considered negative values and took the value of every number mod d. However, my implementation wasn't accepted :cry: . 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]

Posted: Mon Jan 26, 2004 7:59 pm
by boyjava
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

Posted: Tue Jan 27, 2004 7:55 pm
by boyjava
I got accepted with only that change.

Thanks!

Herbert M. Duarte

Posted: Sun Jul 25, 2004 5:50 am
by L I M O N
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

Posted: Mon Jul 26, 2004 4:41 am
by boyjava
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

Posted: Sun Aug 20, 2006 7:59 pm
by Jan
EDIT :

I had some overflows that caused the error. Thanks mf.

Posted: Sun Aug 20, 2006 10:03 pm
by mf
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.

Posted: Wed Aug 30, 2006 7:12 pm
by Kallol
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