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