Dementia 2014: Snow leopard and addition of numbers

Please explain the logic of the problem http://www.codechef.com/DMNT2014/problems/REVADD/

3 Likes

Let R(m) in decimal form be a1a2a3…an.

Number of times each digit ai is present in the rth ( 0<=r<=n-i ) place of any permutation is 2i-1 * C(n-i,r).This is because we can make 2i-1 permutations using digits before ai, which are a1,a2,a3…ai-1.For each of these permutations, we can append ai and any combination of r digits from the n-i digits present after ai.So each ai will contribute a total of 2i-1 * C(n-i,r) * 10r * ai to the total sum by being present in rth place.

So each ai contributes S(i) to the total sum where S(i)=sigma over r=0 to n-i ( 2i-1 * C(n-i,r) * 10r * ai ) which is equivalent to ( 2i-1 * ai)* sigma over r=0 to n-i ( C(n-i,r) * 10r ).Using binomial formula of (1+x)n ,we can say that sigma over r=0 to n-i( C(n-i,r) * 10r ) = (1+10)n-i=11n-i.So S(i)=2i-1 * 11n-i *ai.

So the final answer is simply sum of contribution by each digit ai i.e S(1)+S(2)…S(n) .Here is my solution

.

5 Likes

thanx nice explanation :slight_smile:

great explaination, thanks , and if problem not available in practice section then you can solve similar problems on spoj LINK1 and LINK2

thanks a lot, I was trying to understand the solution for more than 3 hours.