Please explain the logic of the problem http://www.codechef.com/DMNT2014/problems/REVADD/
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
thanx nice explanation
thanks a lot, I was trying to understand the solution for more than 3 hours.