Your approach to solve SANDWICH?

[sanket407]

so constraints were n,k <= 10^18 or the same as of subtask ,2??

[ymondelo20]

Two more links:

Combinatorics - Mathematics Stack Exchange:

https://math.stackexchange.com/questions/89417/number-of-ways-to-put-n-unlabeled-balls-in-k-bins-with-a-max-of-m-balls-inR

nCr - HackerRank:

http://m00nlight.github.io/algorithm/2015/04/11/hackerrank-ncr

[vijju123]

How did you identify that (nk−n%k+knk)(nk−n%k+knk) is the solution? I would appreciate if you can explain that as well

[c0d3h4ck3d]

Thank you ymondelo20

[equlnox]

I didn’t use lucas theorem. I just solved it using CRT and by finding Modular multiplicative inverses.

Let n=⌈^N⁄_K⌉

and x = (K × n) - N

So, as we have to distribute x vacancies in n parts, the number of ways is ^n+x-1C_x

Let the prime factorization of M = p₁^e1×p₂^e2×p₃^e3×p₄^e4 …×p_t^et

Here t is the total no of unique prime factors.

Here p_i^ei and p_j^ej are coprime for any 1 ≤ (i≠j) ≤ t

So if we find ^n+x-1C_x Mod p_i^ei for each i,
We can then combine the results to find ^n+x-1C_x Mod M using CRT

Note that if x! and (n-1)! don’t have any factors of p_i then they would have unique

modular multiplicative inverse.

The main issue that we face now is that (n-1)! and x! could have factors of p_i

Let y be the highest power of p_i which divides x!

Then let F(x,p_i^ei) = ((x!)/p_i^y) Mod p_i^ei
As F(x,p_i^ei) is not divisible by p_i, we can find its modular multiplicative inverse.

We can later on deal with the total power of p_i in ^n+x-1C_x and multiply it to our answer.

So ^n+x-1C_x Mod p_i^ei will be (p_i^z × F(x+n-1,p_i^ei))/(F(x,p_i^ei) × F(n-1,p_i^ei)) Mod p_i^ei

Here z is the highest power of p_i which divides ^n+x-1C_x

To find F(x,p_i^ei), the trick here is to take all the numbers divisible by p_i out of the factorial.

Notice that we take out precisely (⌊^x⁄_pi⌋!)×p_i^⌊x⁄pi⌋ out of the factorial.

Now let H = x!/((⌊^x⁄_pi⌋!)×p_i^⌊x⁄pi⌋) Mod p_i^ei
(Note: H is basically x! with all terms divisible by p_i ignored)

H can be found in in O(p_i^ei+ log x) using fast exponentiation as

all numbers in the factorial repeat after p_i^ei numbers Mod p_i^ei

Now we can say that F(x,p_i^ei)=H×F(⌊^x⁄_pi⌋,p_i^ei)

This is a recurrence relation, so the over all complexity is O((p_i^ei+log x)×(log x))

We now know how to find F(x,p_i^ei)

Now we need to know how to find the power of p_i in x!.

This is simply Σ ⌊^x⁄_pi^c⌋ where c is a natural number.

Here is my solution - https://www.codechef.com/viewsolution/13532849

PS:- The recursive part can be optimized by making it iterative.

That reduces the overall complexity to O(M + (log²(N+k)×(log M)))

[c0d3h4ck3d]

Thanks abdullah786

[bhavit_sharma]

Nobody seems to have shed some light on how to calculate \binom{a}{b}\ mod\ (p^k). We don’t need any research paper to calculate that just some group theory. First let us get rid of all the prime powers of p in \binom{n}{r}. Now let us consider a finite group where X = \{ x : x < p^k, gcd(x, p^k) = 1 \}. Now we can see that this is abelian group [commutative group] under multiplication. So, we can see that if we multiply all the elements of this group and take mod\ (p^k)\ i.e\ x_1.x_2.x_3...x_i.. = -1\ if\ p^k = 4\ or\ p^k\ is\ power\ of\ odd\ prime\ and\ +1\ otherwise. Now to calculate n!\ mod\ p^k[remember we’ve got rid of all the prime powers earlier], we see n!\ \equiv (\pm 1)^{\dfrac{n}{p^k}}.(1.2.3..(n\ mod\ p^k)). (n / p)!\ (mod\ p^k). This is a simple recursive equation which we can calculate in O(p^k\ log\ n) time. Similarly calculate (n - r)!\ \&\ (r!). Take their inverses using extended euclidean and apply chinese remainder theorem.

[shashank96]

@c0d3h4ck3d Updated the answer with resources for both.

@vijju123 It was more of an observation, after writing a brute force algorithm.

[c0d3h4ck3d]

Thanks, mathecodecian

[anupam_datta]

it is, but in a paper of Andrew Granville, it has been extended to prime powers, and after that u need to use chinese remainder theorem

[sumedhk]

For
Subtask 1:
Brute force nCr calculations would work. No overflow worry. Easy 10 points.

          Subtask 2 and 3:
 For prime M, Lucas theorem([Lucas Theorem][1])
                                                   and for non prime M, DP based method to calculate nCr will work([DP-nCr][2])

Subtask 4:
Requires complete implementation of Chinese Remainder Theorem.

[vijju123]

My brute force was too brute

[vicennial]

@shashank96,(https://discuss.codechef.com/questions/98129/your-approach-to-solve-sandwich?page=1#98152)
I derived that formula so I can shed some light on the approach.
Lets take n=13,k=4.
then one such way to distribute this is:
4|4|4|1
Now, we can move some of the value from the first 3 slots to the last slot ‘1’.
we can add a max value of 3 to the last slot since 1+3=k and we cannot have a piece with >k length.
So, by using multinomial theorem,we need to find solutions to:
x1+x2+x3<=3
which is the same as x1+x2+x3+x4=3.
Also the limits for xi can be take to be infinity since their upper bound is greater than the value on RHS.
We know that the formula for non-negative solutions of x1+x2+x3…+xm=p is:
(p+m-1)C(m-1)
Its easy to see that m=(ceil(n/k)) and p=(k-n%k).
Only two special cases:

1. When n%k=0, then there is only 1 way to cut and number of pieces =n/k.
2. when k>=n, number of pieces=1,number of ways=1.

[vicennial]

Here is how I derived the formula:

Your approach to solve SANDWICH?

[shubhamkothari]

I did it using inclusion exclusion principle here ie we distribute balls( = n-k) into boxes ( ceil(n/k) ) with maximum of k balls in each box and to calculate this I used 1. Lucas Theorem 2. Chinese Remainder Theorem. The approach for this is explained here (Q.2 - Life is Strange 4th subtask).
But sadly I could pass only 3 subtasks, I couldn’t figure out the shorter version of formula.
Link for my solution.

[ista2000]

I have used Generalized Lucas theorem and CRT to solve the problem using the same paper mentioned by some users who have already answered in this thread. I don’t know why I get WA on only 1 test case. Throughout the contest I have had 30 submissions for this problem with different changes in code to avoid overflows and all but I still could not get it. Please, can someone tell me what is wrong with my code? Thank you in advance to anyone who tries to look through my code.

Solution: https://www.codechef.com/viewsolution/13619832

[prakhariitd]

@ista2000 WA was because of overflow only!!

See this:
https://www.codechef.com/viewsolution/13632506

There was overflow happening where you calculate the value of ret in f function.
I just placed %x more cautiously.

[ista2000]

@prakhariitd Thank you. I lost 50 pts for a small bug

[anupam_datta]

sad for u @ista2000

[vasja]

Here you can find a decent explanation and code in c++ and python for the nCr (large n and r) problem which includes handling the case of prime powers :). I also found the paper by Andrew Granville which seems to explain the same but it was too complex for me to understand.

I used the code found in this link but gave the guy full credit in the code :). I learned something in this contest which is cool :).
Hope it helps.

http://m00nlight.github.io/algorithm/2015/04/11/hackerrank-ncr