Ameesha Loves Candy ( Code Wars Round 1)

help
1

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

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

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

4

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
5

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

6

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

7

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

8
\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
9

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

10

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

2 Likes
11

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

1 Like
12

@cubefreak777 @dontcheckme

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?

13

I’ve solved entire recurrence here check it.

14

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 ?

15

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 ?

16

thanks, got it now.

17

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 ?
please check it

18

I think I am wrong about the logic of 2^k and +1.

Can you please tell if the formula 2^(k+1)*x - 2^(k) + 1 can be intuitivly derived. Like 2^(k+1)x comes logically because after k+1 months it got x2^(k+1). Similarly is it possible to tell for other 2 terms because it is difficult to solve recurrence relations during contest and it does not come intuitivly

19
\displaystyle\ E[X_{K+1}]=\frac{2^{2K}-\frac{(2^K-1)2^K}{2}}{2^{K-1}}

This is the correct answer in it’s unsimplified form from the approach you’re trying. I think your answer is somewhat similar but not exactly correct.

20

Sorry but I don’t really think there’s an entirely intuitive way to get around it but you can try making the tree of all possible values and then take the weighted average if the leaf nodes. That will also get you the same answer. That approach is more easier to come up with if you’re not good with solving recurrence relations.