10616 - Divisible Group Sums

[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

[Dmytro Chernysh]

The same question...
Nice problem, btw.

[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.

[alex[LSD]]

Does that mean that you guys see problem 10616 in the problemset?

[Dmytro Chernysh]

Well, we'll see it very soon

[boyjava]

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]

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]

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]

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]

I got accepted with only that change.

Thanks!

Herbert M. Duarte

[L I M O N]

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]

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]

EDIT :

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

[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.

[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