Dementia 2014: Snow leopard and addition of numbers

Please explain the logic of the problem


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



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

thanx nice explanation :slight_smile:

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