ANUCBC - Editorial

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.

29 Likes

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

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

4 Likes

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

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

3 Likes

@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

8 Likes

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

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

My O(NM) solution barely passes (in Java) Probably should have made TL a bit more strict; I didn’t even realize I needed to optimize further. At least there is a lot to be learned from this editorial.

3 Likes

Ok, so basically:

  1. count[i] is pre-computed in O(N).
  2. Each query is answered in O(M*M):

    i. If i'th element is chosen, we can choose M different modular sums - O(M)
    ii. The number of ways of choosing the k'th modular sum has to be found, for which we have to scan all 'M' values in the count[ ] array - O(M)
    

Hence, overall complexity is O(N + MMM).

Is that correct?

Dynamic programming problems are really very hard to think…

Can someone please explain this. As choose(count[i],k1) and choose(count[i],k2) can go to indices in the summation array and later on get added up while filling up the dp[I][J] array. So how can we make sure that k1 + k2 has a size less than the total size of count[i] ?

Did the O(mmm) thing, but used top-down (recursive) DP. Got TLE and got stuck…

can anybody please explain why i am getting tle in this …could not get it accepted though i had almost same dp state as mentioned in the tutorial

http://ideone.com/jE7LlL

hey guys.I am not able to understand why count[] and summation[] arrays are used??

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

1 Like

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

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

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

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.

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.