ANUCBC - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Anudeep Nekkanti
Tester: Shiplu Hawlader and Mahbubul Hasan
Editorialist: Lalit Kundu

DIFFICULTY:

MEDIUM

PREREQUISITES:

Dynamic Programming
Precomputation

PROBLEM:

Given N numbers, and a number M, we need to find number of subsets such that sum of elements of subset is divisible by M.
1 <= N <= 100000
1 <= M <= 100
At most 3 test cases with 30 queries in each test. That is 90 queries at most.

EXPLANATION:

If you are not familiar with dynamic programming, read topcoder tutorial here first.
So, here we define a state DP[i][j] which stores the number of ways to choose subsets from A0…Ai such that subset sum modulo M is j.
Now,

 DP[i][j]= DP[i-1][j] + // we don't choose the i'th element   
           DP[i-1][(j-A[i])%M]  // we choose the i'th element

Our answer will be DP[N-1][0]. But here, complexity will be N*M for each query, which will time out.

The advantage here we have is that M<=100. A[i] doesn’t matter to us. What matters is what A[i]%M is. So,

for i=0 to M-1:
     count[i]=number of A[j] such that A[j]%m=i

The above array count, can be calculated using hashing.
Again, we have to use dynamic programming.

We define a new state DP[i][j] which stores, the number of subsets which consists of only those Aj’s whose modulo M is less than or equal to i, and subset sum modulo M is j.
choose(n,r) is number of ways to choose r elements out of n distinct elements ie. (n!)/((r!)*(n-r)!)
Now,

DP[i][j] = 
DP[i-1][(j-i*0)%M]*choose(count[i],0)+// we don't pick any one of the count[i] choices we have.
DP[i-1][(j-i*1)%M]*choose(count[i],1)+// we can pick any one of the count[i] choices we have.
DP[i-1][(j-i*2)%M]*choose(count[i],2)+// we can pick any two of the count[i] choices we have.
.
.
.
DP[i-1][(j-i*count[i])%M]*choose(count[i],count[i])// we pick all of the count[i] choices we have

But, the complexity here will still remain N*M. We can rewrite the above as:

DP[i][j] = 
DP[i-1][(j-0)%M]*summation[k=0 to count[i], where (k*i)%M==0]{choose(count[i],k)} +
DP[i-1][(j-1)%M]*summation[k=0 to count[i], where (k*i)%M==1]{choose(count[i],k)} +
.
.
.
DP[i-1][(j-(M-1))%M]*summation[k=0 to count[i], where (k*i)%M==(M-1)]{choose(count[i],k)}

We can precompute all the summation terms above for each query in O(N).
So, complexity will be O(M*M*M) for each query.

AUTHOR’S AND TESTER’S SOLUTIONS:

To be updated soon.

25 Likes
2

@anudeep2011 really a nice question followed by a equally nice editorial.

That’s what I like about codechef…:slight_smile:

2 Likes
3

Just miss the last O(mmm)trick
next time sure

4

Can someone please explain the last step where the ‘summation’ term is introduced?

1 Like
5

@wittcyeaser We can precompute all the summation terms for each query in O(N)

following code will help you understand how to do it …

summation[M] = {0};
for (int k = 0; k <= count[i]; k++) {
    summation[(k*i)%M] += choose(count[i],k);
}

For each i we need to compute this summation[] only once and
after precomputing this summation[] array we can use it for filling all dp[i][j] values in following way …

for (int j = 0; j < M; j++) {
   dp[i][j] = 0;
   for (int k = 0; k < M; k++) {
      dp[i][j] += dp[i-1][j-k]*summation[k];
   }
}

basically this procedure will take O(M*M) time for each i

5 Likes
6

here negative subset sum whose modulus is zero is not calculated.

7

who told you that ??
I suggest you to go through editorial once again …

8

for negative numbers u can use (A[j] % m) + m .Thus you can map all numbers to [0, m - 1]

9

let m = 30 and 7 occurs 1000 times. Thus by using 7 there will be 1001 ( one 0 sum) different possible sums. But we know m = 30 hence they will boil down to max of 30 different sums. Hence instead of calculating for each possible sum ( which would take O(1001 X 30) for one row). We pre-compute for all different sums less than 30 (in O(10001)) and than in O(30 * 30) we can fill a row.

1 Like
10

sorry, he takes the absolute value of subset sum i have not read the question completely.

11

yaar nishant10 why are you convincing yourself without understanding it completely

It has nothing to do with absolute value of subset sum, had it not been absolute value then also answer would have the same.

12

You have incremented i while computing summation, here k is always 0. If the loop is in terms of k, then we should have to compute summation for i=0 to M-1, so the complexity becomes O(MN), and the solution wont be accepted. I am not sure if I am correct. If I am wrong someone please point out my mistake.

13

@nishant10 Taking absolute value will not always work. For example -16%5 is 4, taking absolute value gives 1. You can use @vishfrnds approach for negative numbers or find (A[j]%m) as ((A[j]%m)+m)%m (this works fine for both positive and negative numbers)

14

oh sorry that was a mistake

now its correct …

15

Then what is the value of i while calculating summation

16

“i” will go from 1 to M-1

dp[0][0] = 2^count[0]

dp[0][j] = 0

or If you want to run “i” from 0 to M-1 then

dp[-1][0] = 1

dp[-1][j] = 0

17

The complexity of finding summation is O(N), which is done O(M) times as you said, so isn’t the overall complexity O(MN)

18

No that loop will run for count[i] time for each i

and i varying from 1 to M-1

so in total it’ll run sigma(count[i]) times

which is O(N)

1 Like
19

Ok, got it, Thanks a lot

20

What about the complexity to calculate choose(n,k)? Is there an algorithm which takes O(1) time? While solving the problem, I had the presumption that calculating it would require O(N*N)(using dynamic programming, since count[i] can be atmost N) in the worst case and hence I eliminated the option of using combinations

1 Like