Given N,K
Now, minimum number of partitions you can have is P = ceil(N/K),
Now what is the maximum size of sandwich can be made with P partitions ?
That is P*K, suppose initially all partitions are full, for example if N=10 and K=4, we have P=3
and partitions are like this :
|…|…|…| now we have 3 groups each is fully filled.
Now coming to the question,
we need to delete some ‘.’ from these groups in order to get a valid configuration in which total size of sandwich is N, suppose if we add a ‘X’ to any group we reduce its size by 1. Now the current size is P*K and required size is N, so we need to distribute (P * K - N) ‘X’ (s) to these P groups, if you observe R = (P * K - N) = (K - N % K), and now our problem is reduced to finding ways of distributing R things in P groups ( any group can get 0 ‘X’ ) for which you can compute the binomial coefficient C(P+R-1,P-1).
““Notice that we take out precisely (⌊x⁄pi⌋!)*pi out of the factorial””
Say x = 6. and p = 2.
(⌊x⁄pi⌋!)*pi = 12 now. But 6! has 16 as power of 2 . Am i right or wrong ??
@sanket407 The thing is we are taking out all the terms divisible by 2 out of 6!, not just the powers of 2.
These terms are 2,4 and 6. We are ignoring these terms as they have 2 as a factor.
The term that we are taking away is hence (⌊x⁄pi⌋!)×(pi^⌊x⁄pi⌋) (Sorry for the typo).
This is equal to 2×4×6 = 48 = 3! × 2^3.
So I calculate 6!/48 = 15
Note that 15 has no powers of 2.
Now as we ignored 2×4×6, it can be written as 3! * 2^3.
We remove the powers of 2 and do the same thing again for 3!
This gives us 3.
15×3=45
This is precisely 6! without any power of 2
That’s actually the generalized Lucas theorem (aka Granville theorem), seems like you were able to derive it during the contest, and that’s brilliant!
@hikarico I just read it. It really is the same. I actually didn’t derive it completely on my own. Just didn’t realize that this link that I referred to described the basic insight behind the generalized lucas’s theorem. https://goo.gl/JLyjAa
@equlnox Learnt , Coded And Passed !! Thanks !! btw your explanation was very good and code was well written too !! Easy to understand !!
Hi guys!
Here is a video editorial by @jtnydv25 on the problem.
It uses Number Theory and the Chinese Remainder Theorem to get to the solution. Feel free to leave your doubts and suggestion in the video comments.
Can you shed some light on why that identity (the product of all integers from 1 to p that are co-prime to p is either 1 or -1)is true?
I don’t understand how being an abelian group is the reason for it. Is this a known identity?
Yes. Being an abelian group helps because it tells that the group operations are commutative in nature. So, we can take all the x_i's with their inverses together and get the identity element from it. However, there will two elements in our group whose inverse element will be itself the element itself, we have to take care[which gives rise to ±1], it’ll be 1 and p^k - 1. Actually, this theorem is popularly known as Gauss’s theorem who generalized Wilson’s theorem on the finite groups. Here’s a link to that.
https://integermiscellany.wordpress.com/2015/07/23/generalizing_wilson/
There was similar problem on hackerank. And the link is editorial to that problem which gives detailed explanation about how to implement ncr % m, whether m is prime or composite;