UVa 10616

From Algorithmist
Jump to navigation Jump to search

10616 - Divisible Group Sums[edit]

Summary[edit]

Count how many fixed size subset sums are divisible by a given divisor.

Explanation[edit]

We can use memoization to solve this problem. Let be the input numbers, and let be the desired divisor. The state space is current index, current sum mod d, numbers left to pick. When at index i, with mod j, and k numbers left to select, we can either take the item at index i, leaving us with at state , or we can pass on item i, leaving us at state . The total number of subsets at state i, j, k is simply the sum of the of counts at each branch.

Gotchas[edit]

  • The input is a signed integer, negative numbers will appear in the input.
  • The modulo (%) operator may not work as intended for negative numbers in your favorite langauge, try it.

Implementations[edit]

Input[edit]

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
3 1
1 -1
3 2
0 0

Output[edit]

SET 1:
QUERY 1: 2
QUERY 2: 9
SET 2:
QUERY 1: 1
SET 3:
QUERY 1: 1
SET 4:
QUERY 1: 1