You are not logged in. Please login at www.codechef.com to post your questions!

×

Your approach to solve SANDWICH?

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

asked 18 May, 15:47

c0d3h4ck3d's gravatar image

5★c0d3h4ck3d
10916
accept rate: 0%


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.

link

answered 18 May, 16:14

prakhariitd's gravatar image

6★prakhariitd
1.1k19
accept rate: 10%

edited 18 May, 17:01

1

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 !!

(18 May, 16:56) sanket4075★

@sanket407 nCr % p^q has to be calculated using Lucas theorem for prime powers

(18 May, 17:01) prakhariitd6★

how ?? p^q is non prime right ?? lucas theorem works for only prime modulus right ?? Correct me if wrong !!

(18 May, 17:05) sanket4075★

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

(18 May, 18:06) anupam_datta4★
14

I didn't use lucas theorem. I just solved it using CRT and by finding Modular multiplicative inverses.
Let n=⌈NK
and x = (K × n) - N
So, as we have to distribute x vacancies in n parts, the number of ways is n+x-1Cx
Let the prime factorization of M = p1e1×p2e2×p3e3×p4e4 .....×ptet
Here t is the total no of unique prime factors.
Here piei and pjej are coprime for any 1 ≤ (i≠j) ≤ t

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

Note that if x! and (n-1)! don't have any factors of pi 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 pi
Let y be the highest power of pi which divides x!
Then let F(x,piei) = ((x!)/piy) Mod piei
As F(x,piei) is not divisible by pi, we can find its modular multiplicative inverse.
We can later on deal with the total power of pi in n+x-1Cx and multiply it to our answer.
So n+x-1Cx Mod piei will be (piz × F(x+n-1,piei))/(F(x,piei) × F(n-1,piei)) Mod piei
Here z is the highest power of pi which divides n+x-1Cx

To find F(x,piei), the trick here is to take all the numbers divisible by pi out of the factorial.
Notice that we take out precisely (⌊xpi⌋!)×pi⌊x⁄pi⌋ out of the factorial.
Now let H = x!/((⌊xpi⌋!)×pi⌊x⁄pi⌋) Mod piei
(Note: H is basically x! with all terms divisible by pi ignored)
H can be found in in O(piei+ log x) using fast exponentiation as
all numbers in the factorial repeat after piei numbers Mod piei
Now we can say that F(x,piei)=H×F(⌊xpi⌋,piei)
This is a recurrence relation, so the over all complexity is O((piei+log x)×(log x))

We now know how to find F(x,piei)
Now we need to know how to find the power of pi in x!.
This is simply Σ ⌊xpic 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 + (log2(N+k)×(log M)))

link

answered 18 May, 17:38

equlnox's gravatar image

5★equlnox
1806
accept rate: 0%

edited 19 May, 18:47

@equlnox

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

(19 May, 16:54) sanket4075★
1

@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

(19 May, 18:14) equlnox5★
1

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!

(19 May, 21:50) hikarico6★
1

@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

(19 May, 23:35) equlnox5★

@equlnox Learnt , Coded And Passed !! Thanks !! btw your explanation was very good and code was well written too !! Easy to understand !!

(20 May, 12:24) sanket4075★

${\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.

  1. Prime Factorization (Sieving and storing smallest prime factor will get this done in O(log N)
  2. 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.
  3. 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

link

answered 18 May, 16:19

shashank96's gravatar image

4★shashank96
1774
accept rate: 0%

edited 18 May, 17:47

Can you please provide some source to read about Lucas Theorem and CRT?

(18 May, 17:14) c0d3h4ck3d5★
1

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 :)

(18 May, 17:30) vijju1234★
1

@c0d3h4ck3d Updated the answer with resources for both.

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

(18 May, 17:48) shashank964★

My brute force was too brute :/

(18 May, 18:15) vijju1234★

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.

link

answered 18 May, 17:46

bhavit_sharma's gravatar image

5★bhavit_sharma
1063
accept rate: 16%

1

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?

(29 May, 22:49) rushilpaul5★
1

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/

(31 May, 08:33) bhavit_sharma5★

@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.

link

answered 18 May, 18:49

vicennial's gravatar image

6★vicennial
2494
accept rate: 0%

edited 19 May, 02:00

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)

link

answered 18 May, 16:19

brainfreeze's gravatar image

4★brainfreeze
512
accept rate: 0%

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

link

answered 18 May, 16:36

ssaxena36's gravatar image

5★ssaxena36
7315
accept rate: 26%

link

answered 18 May, 17:29

ymondelo20's gravatar image

4★ymondelo20
2857
accept rate: 5%

Thank you ymondelo20

(18 May, 17:37) c0d3h4ck3d5★

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.

Video Editorial - SANDWICH

link

answered 29 May, 01:01

gkcs's gravatar image

5★gkcs
2.3k11025
accept rate: 10%

edited 29 May, 01:26

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

https://discuss.codechef.com/questions/3869/best-known-algos-for-calculating-ncr-m
www.dms.umontreal.ca/~andrew/Binomial/genlucas.html
http://codeforces.com/blog/entry/10271

You can google for more.

link

answered 18 May, 15:56

mathecodician's gravatar image

5★mathecodician
2.4k219
accept rate: 8%

(18 May, 17:53) c0d3h4ck3d5★

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.

link

answered 18 May, 15:57

abdullah768's gravatar image

4★abdullah768
1.1k10
accept rate: 12%

edited 18 May, 16:06

1

Ratings haven't updated.

(18 May, 16:02) mathecodician5★

Ik, just in case he read that after the ratings were updated, it would've been weird.

(18 May, 16:09) abdullah7684★

Thanks abdullah786 :D

(18 May, 17:44) c0d3h4ck3d5★

I used dp to solve it, only test case 1 passed, idea was kind of similar to rod cutting problem Link

link

answered 18 May, 15:52

neilit1992's gravatar image

3★neilit1992
1.1k11
accept rate: 20%

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...

link

answered 18 May, 16:00

tamditiensinh's gravatar image

5★tamditiensinh
461
accept rate: 25%

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

link

answered 18 May, 16:04

gagan86nagpal's gravatar image

4★gagan86nagpal
4114
accept rate: 0%

But CRT only works for square free numbers right?

(18 May, 16:07) abdullah7684★

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."

(18 May, 16:18) gagan86nagpal4★

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)
and for non prime M, DP based method to calculate nCr will work(DP-nCr)

Subtask 4: Requires complete implementation of Chinese Remainder Theorem.

link

answered 18 May, 18:13

sumedhk's gravatar image

5★sumedhk
1336
accept rate: 0%

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.

link

answered 18 May, 23:41

shubhamkothari's gravatar image

5★shubhamkothari
11
accept rate: 0%

@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.

link

answered 19 May, 01:20

prakhariitd's gravatar image

6★prakhariitd
1.1k19
accept rate: 10%

edited 19 May, 01:22

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

link

answered 19 May, 08:11

vasja's gravatar image

5★vasja
3174
accept rate: 0%

link

answered 19 May, 13:11

t1g0f8b8sgresu's gravatar image

2★t1g0f8b8sgresu
111
accept rate: 0%

PS !! Test cases were again weak !! Passed subtask c ( M is prime ) in O(k) using normal nCr dp and biginteger in java !!

link

answered 18 May, 16:57

sanket407's gravatar image

5★sanket407
4548
accept rate: 11%

Yes N and K are not 10^18 in that testcase.

(18 May, 17:03) prakhariitd6★

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

(18 May, 17:25) sanket4075★

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

link

answered 19 May, 00:54

ista2000's gravatar image

5★ista2000
1.1k210
accept rate: 21%

edited 19 May, 00:55

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

(19 May, 01:45) ista20005★

sad for u @ista2000

(19 May, 01:50) anupam_datta4★

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

link

answered 19 May, 14:38

dhirajfx3's gravatar image

6★dhirajfx3
1
accept rate: 0%

edited 19 May, 14:41

https://www.hackerrank.com/contests/hourrank-20/challenges/p-string/editorial

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;

link

answered 01 Jun, 11:26

rj25's gravatar image

4★rj25
231
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×890
×29

question asked: 18 May, 15:47

question was seen: 2,508 times

last updated: 01 Jun, 11:26