You are not logged in. Please login at www.codechef.com to post your questions!

×

TAAPLUSB - Editorial

13
5

Problem Link:

Practice
Contest

Difficulty:

Easy

Pre-requisites:

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 ith place results in carry.
Then   E[1] = 45/100
and     E[i] = 45/100 + 10/100 * E[i-1]       for i > 1
(Justification in next section)

By linearity of expectation,

      Answer[N] = E[1] + E[2] ... E[N]

Therefore, one could first pre-compute 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.
This can be done by rewriting the above equation as:
                (0.5 - E[i]) = 10/100 * (0.5 - E[i-1])
Therefore, (0.5 - E[i]) = (0.5 - E[1]) / 10i-1 = 0.00..(i times 0)..05

So,             Answer[N] = E[1] + E[2] ... E[N] = 0.5 * n - 0.0555..(n times 5)..5

Justifications:

Adding the digits at ith place results in a carry if

  1. The sum of those two digits is more than 9. All such pairs of digits are (1, 9), (2, 9), (3, 9) ..., (2, 8), (3, 8), ..., (3, 7), (4, 7), ..., (9, 1). There are 45 such pairs, therefore probability of this happening is 45/100.

  2. The sum of those two digits is exactly 9, and there was a carry from i-1th position. The sum of digits is 9 for the pairs (0, 9), (1, 8), (2, 7), ... (9, 0). The probability of this happening is 10 / 100 * E[i-1].

Hence E[i] = 45/100 + 10 * E[i-1] / 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

utkarsh_lath's gravatar image

5★utkarsh_lath ♦♦
255385251
accept rate: 0%

edited 23 Jul '13, 22:15

fix cook tag please

(22 Jul '13, 00:05) jarekczek3★
1

Can someone explain setter's appraoch? The one that uses DP.

(22 Jul '13, 01:21) tussharsingh134★

In the last line : E[i] = 45/100 + 9 * E[i-1] / 100 ?? I think it should be E[i] = 45/100 + 10 * E[i-1] / 100

(22 Jul '13, 10:29) fiery2★

I used the formula E[i]=0.45*i+E[i-1]/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.

link

answered 22 Jul '13, 03:24

bb_1's gravatar image

4★bb_1
6111
accept rate: 0%

Actually, your formula is same as mine. What you meant was:

Ans[i] = 0.45*i + Ans[i-1]/10

=> Ans[i] - Ans[i-1] = 0.45 + (Ans[i-1] - Ans[i-2]) / 10

=> E[i] = 0.45 + E[i-1] / 10

Just the reccurence above. Please let me know exactly what is unclear in the editorial.

(22 Jul '13, 08:48) utkarsh_lath ♦♦5★

@bb_1: How do u get this E[i]=0.45*i+E[i-1]/10 recurrence relation? plz explain ur approach bcz I didn't understand from editorial.

(22 Jul '13, 23:59) vikrant14333★

@utkarsh_lath: Thanks It is more clear now

(24 Jul '13, 15:27) bb_14★

@vikrant1433: Try to understand Linearity of Expectation . The above justifications are quite clear

(24 Jul '13, 15:28) bb_14★

can anyone give a link to tutorial on Linearity of expectation

link

answered 22 Jul '13, 00:09

coolbun's gravatar image

3★coolbun
2912
accept rate: 0%

Can anyone explain dp approach to the question

link

answered 22 Jul '13, 09:33

coolbun's gravatar image

3★coolbun
2912
accept rate: 0%

The sum of those two digits is exactly 9, and there was a carry from i-1th position. The sum of digits is 9 for the pairs (0, 9), (1, 8), (2, 7), ... (9, 0). The probability of this happening is 10 / 100 * E[i-1]. can someone plz explain why we r multiplying E[i-1]*10/100;

link

answered 24 Jul '13, 21:46

s24w's gravatar image

4★s24w
456
accept rate: 0%

1

The probability that we get a carry from i-1 th place is E[i-1]. Since the digits at ith place are independent of the digits at i-1 th place, we have

Prob[there was a carry from i-1 th place and sum of digits at i th place is 9] = Prob[there was a carry from i-1 th place] * Prob[sum of digits at i th place is 9] = E[i-1] * 10/100.

(24 Jul '13, 22:27) utkarsh_lath ♦♦5★

have we include the case when the first digit for a number(N>1) is 0...we keep on counting if the sum is 9 without testing that the first number cant be 0....

(25 Jul '13, 20:03) sidashsahil1★

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].

link

answered 22 Jul '13, 01:04

bondoc73's gravatar image

4★bondoc73
1062410
accept rate: 10%

still dnt able to get the concept can anyone please clarify that how there are 100 cases and 45 cases that gives carry one ....

link

answered 22 Jul '13, 01:08

devrishal's gravatar image

1★devrishal
1
accept rate: 0%

1

u can see for each 1 digit number like 0 u can add(0-9) so for 10 1-digit numbers cases are 10*10=100

now for carries for number 9 u can get carry by adding (1-9 any number) lly for number 8 u can get carry by adding(2-9 any number)

so total case are 9+8+7+6+5+4+3+2+1=45

hence E[x]=45/100

(22 Jul '13, 01:16) nitish14023★

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 ???

link

answered 22 Jul '13, 02:19

u1z9_3's gravatar image

3★u1z9_3
1112
accept rate: 0%

Yes I also have the same doubt. There seems to be a redundancy both while considering and calculating answer.

(22 Jul '13, 07:46) arnab_das3★
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) utkarsh_lath ♦♦5★

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) bugkiller3★

I had used this formula.
arr[0]=0.45

    for i in range(1,100001):
        if(i%2==1):
            p =  ((l[i-1]/10.0) + 0.9)
        else:
            p = ((l[i-2]/100.0) + .44)
        l.append(p)
    n=input()
    print l[n-1]+(n-1)/2

link

answered 22 Jul '13, 09:04

darkshadows's gravatar image

5★darkshadows ♦
3.0k93164187
accept rate: 12%

edited 22 Jul '13, 09:06

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.

int t,i,j,n;
long double arr[100001],d,num=0.045;
arr[0]=0.0;
d=0.45;
for(i=1;i<100001;++i)
{
    arr[i]=arr[i-1]+d;
    d+=num;
    num/=10;
}
cin>>t;
for(i=0;i<t;++i)
{
    cin>>n;
    cout<<arr[n]<<endl;
}
link

answered 22 Jul '13, 12:48

sikander_nsit's gravatar image

5★sikander_nsit
1.5k82130
accept rate: 0%

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) utkarsh_lath ♦♦5★

just use:

cout<<fixed <<arr[n]<<endl;

and it will get AC :)

(24 Jul '13, 23:08) akashverma_1233★

plz tell me how the equation E(n)=45/100+10/100*E(i-1) came??

link

answered 25 Jul '13, 19:36

sidashsahil's gravatar image

1★sidashsahil
013
accept rate: 0%

shouldn't it be (10/100)+E[i-1] where E[1]=(45/100)??

link

answered 04 Aug '13, 02:26

akshayaj's gravatar image

2★akshayaj
1223
accept rate: 0%

@ utkarsh lath why have we multiplied 45/100 with i.....????

link

answered 15 Aug '13, 23:30

sidashsahil's gravatar image

1★sidashsahil
013
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×3,820
×1,220
×252
×8
×2

question asked: 22 Jul '13, 00:01

question was seen: 4,292 times

last updated: 15 Aug '13, 23:30