ANUCBC - Editorial

yeah choose(n,k) % P can be calculated in O(1) with some pre computation

precomputate fact[i] array which is (i!)%P

and ifact[i] array which is Modular multiplicative inverse of i! modulo P

then choose(n,k)%P = (fact[n]*ifact[n-k]*ifact[k])%P

precomputation of these arrays can be done in in O(NlogP)

1 Like

Thanks! That seemed quite straight forward (in the sense that this is how we naturally calculate choose n,k (using the formula)). So we can compute nck with just O(n) pre-computation (with an extra logP for inverse calculation :))

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.

2 Likes

Thanks @vishfrnds

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?

@lg5293:Can you explain your solution.

Dynamic programming problems are really very hard to thinkā€¦

My solution is basically the first solution presented in the editorial (the one that should supposedly time out).

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] ?

ok.Thanks.

Can you 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

Yes, per query the complexity is O(N + MMM)

We actually do it in order. We have M classes of numbers. We start from class 0 and go till class M-1, at each class we decide on how many numbers we need to take from that class, we also need the remainder when we move to next state.
We move from state DP[i][carry] to DP[i+1][NewCarry], where i is the class and carry is the current sum modulo M

Give me link. I will see.
Also note that Modulo operator is very costly and so excessive use might have resulted in TLE.

1 Like

plz help ā€¦

http://www.codechef.com/viewsolution/3759961 (sorry for the late reply, I was traveling)

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