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

Let R(m) in decimal form be a_{1}a_{2}a_{3}…a_{n}.

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

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

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

.

thanx nice explanation

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.