Please share how you approached solving SANDWICH, even if you didn’t get AC. It will help us to understand how to tackle more mathematically oriented problems.
Thank you
4 Likes
I used dp to solve it, only test case 1 passed, idea was kind of similar to rod cutting problem Link
1 Like
Basically you needed to use generalized lucas’s theorem. First covert the solution to aCb form where
a = ans1-1
b = a+(ans1*k-n)
Now, I could solve it for 50 pnts as I couldn’t understand generalized lucas’s theorem but here are some links to calculate nCr % m
www.dms.umontreal.ca/~andrew/Binomial/genlucas.html
http://codeforces.com/blog/entry/10271
You can google for more.
2 Likes
After some observation, I found that the answer would be (N/K +R)cR where N is the length of the sandwhich and R=K-(N%k). Wasn’t able to solve it for when M was not prime tho as inverse could not be found.
Here’s my code (it’s a bit messy tho):
https://www.codechef.com/viewsolution/13530263
P.S: I just noticed we have the exact same rating(before the updation of this contests ratings.). What a coincidence xD.
2 Likes
First I came up with a dynamic programming approach in O(N^3), then i test for pattern on small test. After that I realize *f[i] = 1 with i<k or i%k==0, otherwise f[i] = f[i-k] + f[i-k+1] + … + f[[i/k]k-1] which can be calculated in O(N). Still thinking for subtask 3 and 4…
1 Like
Ratings haven’t updated.
1 Like
Answer was easily reduced to N C K mod m , where m is not prime . If m would have been prime , it would be easily solvable by lucas theorem . But here m is not necessarily prime. So, there were various algorithms to do that too. I am not sure since i got 50 only. One idea was to break m into it’s prime factors. Let us say:
m = p1^k1 * p2^k2 * p3^k3…
Now we can find answer to each factor by “generalized lucas theorem” and combine answers by CRT.
source: https://discuss.codechef.com/questions/3869/best-known-algos-for-calculating-ncr-m
Another approach is discussed here :
http://m00nlight.github.io/algorithm/2015/04/11/hackerrank-ncr
1 Like
But CRT only works for square free numbers right?
Ik, just in case he read that after the ratings were updated, it would’ve been weird.
First thing which you have to see that
Answer is ^{n+n*K-N-1}C_{n-1} where n=\lceil \frac{N}{K} \rceil
Now for N as large as 10^{18} and M non-prime, you will have to use the generalization of Lucas theorem for prime powers.
And after calculating answer modulo all the prime powers present in M, you will have to use Chinese remainder theorem.
Lucas theorem for prime powers is Theorem 1(page 2) in this research paper.
10 Likes
I am not quite sure , but i think CRT works fine if N and m are co- prime.
See the link in source.
Here’s a quote from that link:
“You can find the result of nCr % m for each m = 27, 11, 13, 37. Once you have the answers, you can reconstruct the answer modulo 142857 using Chinese Remainder Theorem. These answers can be found by Naive Methods since, m is small.”
{\frac{n}{k} - {n \% k} + k} \choose {\frac{n}{k}} is the solution for the sandwich problem.
Honestly this came as an observation rather than some Mathematics.
Once this is identified, the problem becomes more of the optimization problem.
Things you need for solving this.
- Prime Factorization (Sieving and storing smallest prime factor will get this done in O(log N)
- General Lucas Theorem, Calculate {{\frac{n}{k} - {n \% k} + k} \choose {\frac{n}{k}}} \% p^k where P is prime and k is the highest of power of P in M. Calculate this for all prime factors P.
- Combine them using the Chinese Remainder Theorem
Refer https://arxiv.org/pdf/1301.0252.pdf for General Lucas Theorem.
Here is a implementation of CRT -> http://www.geeksforgeeks.org/chinese-remainder-theorem-set-2-implementation
Vote this answer, if you feel like. Karma needed for asking questions
8 Likes
Sandwich is pure math. You can easily determine number of pieces you must cut your sandwich, let’s call it T. Now imagine that you cut a sandwich of length l=k*T. That sandwich can be cut only one way and l>=n. Now to produce all ways to cut our original sandwich we must distribute (l-n) “shortenings by one” between T pieces. That is “Stars and bars” problem
https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics).
Now you only need to know how to calculate C(n0, k0) modulo M for very large n0 and k0 (not n and k from a problem, but easily derived from them). For that we need to factorise M. Now suppose that M have some prime divisor p1 and M is divisible by pow(p1, k1), but not divisible by pow(p1, k1+1). Let n0!=pow(p1, t1)*q1, where q1 and p1 are coprime. We need to calculate t1 and q1 modulo pow(p1, k1) for each prime divisor of M. (e-maxx has similar algorithm, although not exactly one needed). After that we can use Chinese Remainder Theorem and reprsent n!=pow(p1, t1)*pow(p2, t2)…*pow(pi, ti)*Qn, where Qn and M are coprime (we don’t need Qn itself, only Qn modulo M).
We must do previous part for all three factorials and then divide one by two others (subtract powers for prime divisors and divide in ring for Qn’s)
4 Likes
For 50 pts : Python users could use this inbuilt function scipy.misc.comb(N, R, exact=True) as mentioned in my solution : Python
However for 100 pts the topic involved were 1. Lucas Theorem 2. Chinese Remainder Theorem 3. Wilson Theorem which gave an AC and can be referred by link mentioned in my Java code : here
3 Likes
how do u calculate ans modulo all prime powers in M .??
Since prime power can be non prime ( i am assuming prime power means p^q)
So denominator and prime power can be non co prime too right ??
So how do you calculate modular inverse !!
1 Like
PS !! Test cases were again weak !!
Passed subtask c ( M is prime ) in O(k) using normal nCr dp and biginteger in java !!
Yes N and K are not 10^18 in that testcase.
how ?? p^q is non prime right ?? lucas theorem works for only prime modulus right ?? Correct me if wrong !!
Can you please provide some source to read about Lucas Theorem and CRT?