# Ameesha Loves Candy ( Code Wars Round 1)

Can someone help me how to solve Ameesha loves candy problem? here is what i tried https://www.codechef.com/viewsolution/45355161

\displaystyle \mathbb{E}[K+1]=2^{K+1} X-2^{K}+1

x
2x , 2x - 1 (after 1 month)
2 * 2x , 2 * 2x - 1 , 2 * (2x - 1) , 2 * (2x - 1) - 1 (after 2 month)
222x , 222x - 1 , 2 * (22x - 1) , 2 * (22x - 1) - 1…
.
.
.

terms = 1 << k; (total terms after k months)
P = (terms * 2 ^ (k) * x - sum(0 to terms - 1)) / (1 << (k- 1))

You can also do this by solving the following recurrence.
\mathbb{E}[X_i] is the Expected number of candies after i months}
\mathbb{P}(I) is the probability that magic box eats one of the candies.

\mathbb{E}[X_{i+1}]=\mathbb{P}(I)\times (2 \ \mathbb{E}[X_i])+\mathbb{P}(I')\times(2 \ \mathbb{E}[X_i]-1)\\ \mathbb{E}[X_{i+1}]=\frac{1}{2}\times 2\ \mathbb{E}(X_i)+\frac{1}{2}\times(2 \ \mathbb{E}[X_i]-1) \\ \mathbb{E}[X_{i+1}]=2 \ \mathbb{E}[X_i]-\frac{1}{2}

Solving this recurrence will get you the result I mentioned above.

1 Like

this is exactly what I did… still got it wrong CodeChef: Practical coding for everyone
any ideas? please tell me if you get this.

You did not divide the total candies by 2 ^ (k - 1).
Also consider the base case 0 when x = 0.

Please share the solved recurrence for better understanding along with this.

\mathbb{E}[X_{i}]=2 \ \mathbb{E}[X_{i-1}]-\frac{1}{2}\\ 2\ \mathbb{E}[X_{i-1}]=2^2\ \mathbb{E}[X_{i-2}]-1 \\ \vdots \\ 2^{i-1}\ \mathbb{E}[X_1]=2^i \ \mathbb{E}[X_0]-2^{i-2}

Now it’s trivial to see that \mathbb{E}[X_0]=X
On adding all the above equations.

\mathbb{E}[X_{i}]=2^iX-\frac{1}{2}-1-2-4 \dots -2^{i-2} \\ \mathbb{E}[X_{i}]=2^iX-\frac{1}{2} \frac{(2^i-1)}{(2-1)} \\ \mathbb{E}[X_K]=2^KX-\frac{1}{2}(2^K-1)

Now since we are assured that in the K+1 th month magic box doesn’t eat the extra candy so we can simply double the answer we obtained after K months. i.e.

\mathbb{E}[X_{K+1}]=2\times \mathbb{E}[X_K] \\ \boxed{ \therefore \mathbb{E}[X_{K+1}]=2^{K+1}X-(2^K-1)}
4 Likes

Thanks a lot brother, cubefreak777. Can you pls suggest more problems like it ?
Or, is there any specific resources to be better at “Expected number” problems.

Top Coder has a great collection of probability and expectation value problems. Almost every SRM they conduct has an expected value problem.

2 Likes

You can check the official editorial of this question from codeforces named as Nastya and a Wardrobe and here is the link.

1 Like

except the last +1 i can understand the equation. where does this +1 come from, they say last k+1th month should not be considered but why did we do +1 for that?

I’ve solved entire recurrence here check it.

i understood the derivation brother but if i want to instinctively get a logic, i cant understand why +1 comes. so in simple terms, i understand that for each month it gets doubled so after k+1 months its value will be 2^(k+1) * x and then because the wardrobe eats 1 candy after each month , after k+1 months the loss would be 2^k (after 1st month loss is 2^0, after 2nd loss is 2^1, after k+1 months loss is 2^k). Till this its fine. but here since we also counted loss for last month, we need to again nullify the loss separately. but how is it 1 ?

I don’t understand this. I mean after each month he consumes one candy so how are these powers of 2 showing up ?
Also I don’t get where have you considered the notion of probability in this intuitive approach ?

thanks, got it now.

x0 = initial value ,i have taken 4 here

                                            4
/       \
7          8
/    \       / \
13    14       15  16


x = sum of last level
k = total number of levels
answer = 2 * x / number_of_nodes at last level
ans = 2 * x/ pow(2, k - 1)

now find left which is 13 here let say ‘a’ and right say ‘b’
the x = (a + b) * (b - a + 1)/2

is this correct ?