ANUCBC - Editorial

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.

@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)

oh sorry that was a mistake

now its correct …