Problem Link:Difficulty:Easy Prerequisites:Linearity of Expectation, basic probability Problem:Find the expected number of carries when adding two numbers, each at most N digits long. Explanation:let E[i] = probability that addition at i^{th} place results in carry. By linearity of expectation, Answer[N] = E[1] + E[2] ... E[N] Therefore, one could first precompute all E[i]'s and then Answer[i]'s in O(N) time overall. This gives complexity of O(N+T). However, it is also possible to have O(1) time per testcase. So, Answer[N] = E[1] + E[2] ... E[N] = 0.5 * n  0.0555..(n times 5)..5 Justifications:Adding the digits at i^{th} place results in a carry if
Hence E[i] = 45/100 + 10 * E[i1] / 100 Setter's Solution:Can be found here Tester's Solution:Can be found here
This question is marked "community wiki".
asked 22 Jul '13, 00:01

I used the formula E[i]=0.45*i+E[i1]/10 and got it accepted . I don't understand how your formula and mine can give the same results. Also your justification is quite unclear. Could you please elaborate it properly. answered 22 Jul '13, 03:24
Actually, your formula is same as mine. What you meant was: Ans[i] = 0.45*i + Ans[i1]/10 => Ans[i]  Ans[i1] = 0.45 + (Ans[i1]  Ans[i2]) / 10 => E[i] = 0.45 + E[i1] / 10 Just the reccurence above. Please let me know exactly what is unclear in the editorial.
(22 Jul '13, 08:48)
@bb_1: How do u get this E[i]=0.45*i+E[i1]/10 recurrence relation? plz explain ur approach bcz I didn't understand from editorial.
(22 Jul '13, 23:59)
@utkarsh_lath: Thanks It is more clear now
(24 Jul '13, 15:27)
@vikrant1433: Try to understand Linearity of Expectation . The above justifications are quite clear
(24 Jul '13, 15:28)

Can anyone explain dp approach to the question answered 22 Jul '13, 09:33

I started to see a pattern after I divided each of the test cases by 0.45. I got 1, 2.1, 3.21 ... as you can notice each one is the previous divided by 10 + next integer. so I pre calculated each E[i] as follows; d = 1; E[1] = 0.45; for each i from 2 to 100000 d /= 10; d += i; E[i] = 0.45 * d; Then for each n I read I write E[n]. answered 22 Jul '13, 01:04

why we are considering each pair two times like when we are calculating pairs with 9 we've already considerd 9+8..but again when calculating pairs for 8 we included 8+9..aren't they same ??? answered 22 Jul '13, 02:19
Yes I also have the same doubt. There seems to be a redundancy both while considering and calculating answer.
(22 Jul '13, 07:46)
1
No, they are not same. Adding 1 and 9 is different from adding 9 and 1. This is because both numbers are chosen independently. If you consider 1+9 same as 9+1, then you are giving more "weight" to the case when both digits are same(there will be 10/55 such cases as compared to 10/100 in the original setting). To see this quickly, make your base 2, and consider 1 digit numbers. Carry is there only when you add 1+1. Since you consider 0+1 same as 1+0, you will give answer 1/3. whereas, it is clearly 1/4(probability that both numbers are 1).
(22 Jul '13, 08:42)
You should have got over this doubt by seeing the answer 0.45 for single digit numbers. If you don't include repetition then it should have been 0.30 as there would be 30 such cases. But as the sum of 1,2,3...,10 is 55; it takes less than a millisecond to observe that number of cases is 45 (1+2+3+...+9). Adding (21 and 19) and (29 and 11) are considered to be different although in both cases the carry is due to 9+1, for the reason cum explanation mentioned by @utkarsh_lath
(22 Jul '13, 12:19)

I had used this formula.
answered 22 Jul '13, 09:04

I figured out the recurrence and used the fact that the answer has to be correct for six decimal digits only. Have a look at my solution. link Though I don't understand why this code didn't work. I thought long double would take care of precision.
answered 22 Jul '13, 12:48
You got it right, it gives WA due to precision issues. But you seem to not to know where precision is coming into picture. It is coming when you print your result ! cout prints upto 6 significant digits. This fact often gives wrong answer and people remain clueless about their error.
(22 Jul '13, 18:47)
just use: cout<<fixed <<arr[n]<<endl; and it will get AC :)
(24 Jul '13, 23:08)

plz tell me how the equation E(n)=45/100+10/100*E(i1) came?? answered 25 Jul '13, 19:36

shouldn't it be (10/100)+E[i1] where E[1]=(45/100)?? answered 04 Aug '13, 02:26

@ utkarsh lath why have we multiplied 45/100 with i.....???? answered 15 Aug '13, 23:30

fix cook tag please
Can someone explain setter's appraoch? The one that uses DP.
In the last line : E[i] = 45/100 + 9 * E[i1] / 100 ?? I think it should be E[i] = 45/100 + 10 * E[i1] / 100