TAAPLUSB - Editorial

editorial
, , , , ,
2

can anyone give a link to tutorial on Linearity of expectation

1 Like
3

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

4

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

5

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

6

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.

4 Likes
7

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
8

Can anyone explain dp approach to the question

1 Like
9

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;
}
10

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;

1 Like
11

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

12

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

13

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

14

fix cook tag please

15

Heard about Google?
http://www2.informatik.hu-berlin.de/alcox/lehre/lvss11/rapm/linearity_expectation.pdf
http://valis.cs.uiuc.edu/~sariel/teach/2003/b_273/notes/08_prob_III.pdf
http://courses.csail.mit.edu/6.042/fall05/ln14.pdf

5 Likes
16

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

1 Like
17

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

1 Like
18

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

19

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

1 Like
20

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.

21

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