# EXMV - Editorial **URL:** \ **Category:** editorial\ **Tags:** editorial, expected-value, math, probability, june221\ **Created:** [June 8, 2022, 11:30am UTC](https://discuss.codechef.com/t/exmv-editorial/101471 "2022-06-08T11:30:20Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![kulyash](https://discuss.codechef.com/user_avatar/discuss.codechef.com/kulyash/32/219888_2.png) [@kulyash](https://discuss.codechef.com/u/kulyash)\ **Post date:** [June 8, 2022, 11:30am UTC](https://discuss.codechef.com/t/exmv-editorial/101471/1 "2022-06-08T11:30:21Z")
# PROBLEM LINK: [Contest Division 1](https://www.codechef.com/JUNE221A/problems/EXMV) [Contest Division 2](https://www.codechef.com/JUNE221B/problems/EXMV) [Contest Division 3](https://www.codechef.com/JUNE221C/problems/EXMV) [Contest Division 4](https://www.codechef.com/JUNE221D/problems/EXMV) Setter: [Muhammad Najmul Hasan Nayeem](https://www.codechef.com/users/nh_nayeem) Tester: [Takuki Kurokawa](https://www.codechef.com/users/tabr), [Lavish Gupta](https://www.codechef.com/users/lavish_adm) Editorialist: [Yash Kulkarni](https://www.codechef.com/users/kulyash) # DIFFICULTY: 1541 # PREREQUISITES: [Expected Value](https://en.wikipedia.org/wiki/Expected_value#:~:text=In%20probability%20theory%2C%20the%20expected,outcomes%20of%20a%20random%20variable.), [Probabilty](https://en.wikipedia.org/wiki/Probability) # PROBLEM: Given values of x and N. In one move you can flip a fair coin. - If it is head then x will **increase** by 1. But if x=N then x will **not** change. - If it is tail, x will **decrease** by 1. The game ends when the value of x reaches 1. Calculate the expected number of moves to end the game. # EXPLANATION: We know that the probabilities that x increases by 1 or decreases by 1 are both 0.5. > **Symmetric Problem** > > Let us first consider the symmetric problem in which the game ends if x reaches 1 or M. > Let E\_i be the expected number of moves to end this game if we start with x = i. > We can construct the following system of equations using basic knowledge of expectation theory, > > - E\_1 = 0. > - E\_2 = 0.5 (E\_1 + 1) + 0.5 (E\_3 + 1) = 0.5 E\_1 + 0.5 E\_3 + 1. > - E\_3 = 0.5 E\_2 + 0.5 E\_4 + 1. > ... > - E\_M = 0. > > Due to symmetry it is clear that E\_i = E\_{M - i + 1}. > > Formally, > E\_i = 1+ 0.5 E\_{i - 1} + 0.5 E\_{i + 1}, if 1 \< i \< M and E\_1 = E\_M = 0. > > The general solution for the above problem is, > E\_i = −i^2 + A + Bi. > > We can find out A and B using the knowledge E\_1 = E\_M = 0. We get A = -M and B = M + 1 . > So, > E\_i = −i^2 -M + (M + 1)i → E\_i = (i - 1) (M - i). > **Original Problem** > > Now, let us come back to the original problem. > All the equations for the original problem remain the same as the symmetric problem (M = N) except for the last equation. The changed equation is, > E\_N = 0.5 E\_{N - 1} + 0.5 E\_N + 1 (if we get a head at x = N then x does not change) > > In the original problem x always stays in the range [1, N] but we will use a trick by adding a symmetric image to the right of the above range. [1, N] + [N+1, 2N] = [1, 2N]. This transformation converts the original problem into the symmetric problem with M = 2N (E\_i = E\_{2N - i + 1}). We will allow x to increase beyond N and if x reaches 1 or 2N, the game ends. > We just need to check the equation for E\_N, > E\_N = 0.5 E\_{N-1} + 0.5 E\_{N + 1} + 1 → E\_N = 0.5 E\_{N - 1} + 0.5 E\_N + 1. > > This clearly shows that the equations for the symmetric problem (M = 2N) are identical to the equations of the original problem. Since the equations are same, it is certain that E\_i = (i - 1) (2N - i). So, our answer is nothing but E\_x = (x - 1) (2N - x). # TIME COMPLEXITY: O(1) for each test case. # SOLUTION: > **Setter's solution** > > ```auto > using namespace std; > int main() > { > int t; > cin>>t; > while(t--) > { > long long n, x; > cin >> x >> n; > // (X-1)(2N-X) > cout << (x-1)*(2*n-x) << '\n' ; > } > return 0; > } > > ``` > **Editorialist's Solution** > > ```auto > #define ll long long > using namespace std; > int main(){ > ll T; > cin >> T; > while(T--){ > ll x,n; > cin >> x >> n; > cout << (x-1)*(2*n-x) << endl; > } > return 0; > } > > ``` ---
**Author:** ![termii](https://discuss.codechef.com/user_avatar/discuss.codechef.com/termii/32/355675_2.png) [@termii](https://discuss.codechef.com/u/termii)\ **Post date:** [June 13, 2022, 10:55am UTC](https://discuss.codechef.com/t/exmv-editorial/101471/2 "2022-06-13T10:55:29Z")
there is an alternative solution for those that don’t have a heavy math background: **STEP 0:** try around for 4 hours, make no progress at all. **STEP 1:** go into excel, copy the numbers of the last testcase inside (X:568 N:57800 Result: 65223144) **STEP 2:** after literally 1 minute, notice that (568 - 1) cleanly divides 65223144 into 115032 **STEP 3:** after around 5 more minutes, notice that (2 \* 57800 - 568) is equal to our second divisor 115032 **STEP 4:** replace the numbers in 65223144 = (568 - 1) \* (2 \* 57800 - 568) with variables: result = (x - 1) \* (n \* 2 - x) **STEP 5:** feel like a cheater and submit ``` long x = sc.nextInt(); long n = sc.nextInt(); long result = (x-1)*(n*2-x); out.println(result); ``` **STEP 6:** enjoy full score, out of the world. ---
**Author:** ![lucifero](https://discuss.codechef.com/user_avatar/discuss.codechef.com/lucifero/32/66924_2.png) [@lucifero](https://discuss.codechef.com/u/lucifero)\ **Post date:** [June 13, 2022, 12:53pm UTC](https://discuss.codechef.com/t/exmv-editorial/101471/3 "2022-06-13T12:53:06Z")
could anyone provide a good resource for expectation theory i am quite bad in it ---
**Author:** ![veeru\_232](https://discuss.codechef.com/user_avatar/discuss.codechef.com/veeru_232/32/90094_2.png) [@veeru\_232](https://discuss.codechef.com/u/veeru_232)\ **Post date:** [June 13, 2022, 12:55pm UTC](https://discuss.codechef.com/t/exmv-editorial/101471/4 "2022-06-13T12:55:17Z")
I am unable to understand the explanation. why are ppl explaining by saying notice the ans for that and this. why editorial is also not solving the problem using only problem statement. ---
**Author:** ![termii](https://discuss.codechef.com/user_avatar/discuss.codechef.com/termii/32/355675_2.png) [@termii](https://discuss.codechef.com/u/termii)\ **Post date:** [June 13, 2022, 1:14pm UTC](https://discuss.codechef.com/t/exmv-editorial/101471/5 "2022-06-13T13:14:56Z")
the editorial solved the problem with only the problem statement. But this is not a programming problem, it is a relatively hard statistical problem. If you are here to learn coding, solving these problems will do absolutely nothing for you. For those interested in reading more about this problem, I don’t have a good source but I know the name of the problem. This problem falls in the **statistics** category. The problem is both in the sub-category **random walk problem** and **expectation theory** ---
**Author:** ![nav1285](https://discuss.codechef.com/user_avatar/discuss.codechef.com/nav1285/32/24644_2.png) [@nav1285](https://discuss.codechef.com/u/nav1285)\ **Post date:** [June 13, 2022, 1:23pm UTC](https://discuss.codechef.com/t/exmv-editorial/101471/6 "2022-06-13T13:23:34Z")
I am not getting the comparison for En. Can someone please explain. ---
**Author:** ![mundi](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@mundi](https://discuss.codechef.com/u/mundi)\ **Post date:** [June 13, 2022, 2:44pm UTC](https://discuss.codechef.com/t/exmv-editorial/101471/7 "2022-06-13T14:44:31Z")
[Solving linear recurrences](https://www.eecs.yorku.ca/course_archive/2008-09/S/1019/Website_files/21-linear-recurrences.pdf) This might help ---
**Author:** ![lucifero](https://discuss.codechef.com/user_avatar/discuss.codechef.com/lucifero/32/66924_2.png) [@lucifero](https://discuss.codechef.com/u/lucifero)\ **Post date:** [June 13, 2022, 3:21pm UTC](https://discuss.codechef.com/t/exmv-editorial/101471/8 "2022-06-13T15:21:35Z")
how does reaching the state at M end the game where M != 1 ---
**Author:** ![veeru\_232](https://discuss.codechef.com/user_avatar/discuss.codechef.com/veeru_232/32/90094_2.png) [@veeru\_232](https://discuss.codechef.com/u/veeru_232)\ **Post date:** [June 13, 2022, 5:44pm UTC](https://discuss.codechef.com/t/exmv-editorial/101471/9 "2022-06-13T17:44:08Z")
yes u r right. i want to learn problem solving with proper understanding of Problem statement. not just figuring out answer. yes i agree that i didnt understand the solution. but at least editorial should give complete explanation for the solution. ---
**Author:** ![termii](https://discuss.codechef.com/user_avatar/discuss.codechef.com/termii/32/355675_2.png) [@termii](https://discuss.codechef.com/u/termii)\ **Post date:** [June 13, 2022, 6:00pm UTC](https://discuss.codechef.com/t/exmv-editorial/101471/10 "2022-06-13T18:00:28Z")
I would rather find the fault with the problem setter and those that approved, because this is a pretty dumb problem for a coding challenge. It is off topic and unnecessarily hard. The prerequisites are completely over the top. University level knowledge in statistics to even attempt to understand the solution? Pretty terrible for a coding problem. ---
**Author:** ![notmotivated](https://discuss.codechef.com/user_avatar/discuss.codechef.com/notmotivated/32/122479_2.png) [@notmotivated](https://discuss.codechef.com/u/notmotivated)\ **Post date:** [June 14, 2022, 2:05am UTC](https://discuss.codechef.com/t/exmv-editorial/101471/11 "2022-06-14T02:05:03Z")
when X = N, the expected flips turn out to be 2 + 4 + 6 + 8 + \dots \, \, +2(N - 1) which is equal to N(N - 1) you can easily extend this idea to when X \ne N ---
**Author:** ![notmotivated](https://discuss.codechef.com/user_avatar/discuss.codechef.com/notmotivated/32/122479_2.png) [@notmotivated](https://discuss.codechef.com/u/notmotivated)\ **Post date:** [June 14, 2022, 2:33am UTC](https://discuss.codechef.com/t/exmv-editorial/101471/12 "2022-06-14T02:33:33Z")
that line is saying “Let us consider” ---
**Author:** ![demo\_neel](https://discuss.codechef.com/user_avatar/discuss.codechef.com/demo_neel/32/24644_2.png) [@demo\_neel](https://discuss.codechef.com/u/demo_neel)\ **Post date:** [June 14, 2022, 11:13am UTC](https://discuss.codechef.com/t/exmv-editorial/101471/13 "2022-06-14T11:13:31Z")
how did u think of that 😭 ---
**Author:** ![asmitdeb](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@asmitdeb](https://discuss.codechef.com/u/asmitdeb)\ **Post date:** [June 14, 2022, 2:52pm UTC](https://discuss.codechef.com/t/exmv-editorial/101471/14 "2022-06-14T14:52:42Z")
what’s the name of the problem? ---
**Author:** ![instinctive](https://discuss.codechef.com/user_avatar/discuss.codechef.com/instinctive/32/106748_2.png) [@instinctive](https://discuss.codechef.com/u/instinctive)\ **Post date:** [June 14, 2022, 4:26pm UTC](https://discuss.codechef.com/t/exmv-editorial/101471/15 "2022-06-14T16:26:42Z")
Suppose X = N = 4. Then the only way to get to 1 is to first go down to 3, since you are starting at the limit of 4. So E(4), the expected flips to reach 1 from 4, has to be equal to E(3) plus the expected flips to get to 3 from 4. How many flips is that? 1/2 times it will be 1 flip 1/4 times it will be 2 flips 1/8 times it will be 3 flips … 1\*(1/2) + 2\*(1/4) + 3\*(1/8) + 4\*(1/16) + … = 2 So E(4) = E(3) + 2. Now, how about E(3) ? The calculation is similar, but this time every time you flip heads you pay the extra cost for going back to 4, which you have already calculated. Again, it will be a similar infinite sum, but the multipliers will be larger because of the cost for going back to 4. Once you work out a couple of terms you will see the pattern. ---
**Author:** ![akm07](https://discuss.codechef.com/user_avatar/discuss.codechef.com/akm07/32/194571_2.png) [@akm07](https://discuss.codechef.com/u/akm07)\ **Post date:** [June 14, 2022, 4:27pm UTC](https://discuss.codechef.com/t/exmv-editorial/101471/16 "2022-06-14T16:27:09Z")
Literally me 🙂 ---
**Author:** ![paperba1l](https://discuss.codechef.com/user_avatar/discuss.codechef.com/paperba1l/32/229253_2.png) [@paperba1l](https://discuss.codechef.com/u/paperba1l)\ **Post date:** [June 14, 2022, 4:27pm UTC](https://discuss.codechef.com/t/exmv-editorial/101471/17 "2022-06-14T16:27:12Z")
What is that M in the Symmetric Problem? from where did it come from? We just know game ends when it reaches 1 right? ---
**Author:** ![kulyash](https://discuss.codechef.com/user_avatar/discuss.codechef.com/kulyash/32/219888_2.png) [@kulyash](https://discuss.codechef.com/u/kulyash)\ **Post date:** [June 15, 2022, 5:13pm UTC](https://discuss.codechef.com/t/exmv-editorial/101471/18 "2022-06-15T17:13:01Z")
The symmetric problem is a problem which ends if x reaches 1 or M, basically it has 2 end points unlike the given problem, which has 1 end point. We are using the trick of combining 2 unsymmetric problems to create a symmetric problem to solve this question. ---
**Author:** ![rhymehatch](https://discuss.codechef.com/user_avatar/discuss.codechef.com/rhymehatch/32/205573_2.png) [@rhymehatch](https://discuss.codechef.com/u/rhymehatch)\ **Post date:** [June 15, 2022, 11:09pm UTC](https://discuss.codechef.com/t/exmv-editorial/101471/19 "2022-06-15T23:09:18Z")
Everything is in the problem statement. For me the hardest part was to realize I can write a recursion. One can’t go over n. Expected number of throws is E\_n. This means that E\_n = \frac{1}{2}(E\_{n-1}+1) + \frac{1}{2}(E\_{n}+1) \xrightarrow[\text{simplifies to}]{} E\_n=E\_{n-1}+2. If you continue writing for E\_{n-1} = \frac{1}{2}(E\_{n-2}+1) + \frac{1}{2}(E\_{n}+1) and replace E\_{n} you get E\_{n-1}=E\_{n-2}+4. You can go on and write the expression for E\_{n-2} and you notice that it’s E\_{n-3}+ 6. After this you think in terms of 2 \cdot (1 + \ldots + n) and not even use the weird (x-1)\cdot(n\cdot2-x) formula but just deal with sum of numbers from 1 to n. My original solution was n (n-1) - (n-x+1)(n-x). I then simplified it symbolically with [sympy](https://www.sympy.org/en/index.html). ---
**Author:** ![pigkeeper](https://discuss.codechef.com/user_avatar/discuss.codechef.com/pigkeeper/32/24644_2.png) [@pigkeeper](https://discuss.codechef.com/u/pigkeeper)\ **Post date:** [June 16, 2022, 5:28pm UTC](https://discuss.codechef.com/t/exmv-editorial/101471/20 "2022-06-16T17:28:19Z")
Please explain this portion of the editorial in-depth. > In the original problem x always stays in the range [1, N] but we will use a trick by adding a symmetric image to the right of the above range. [1, N] + [N+1, 2N] = [1, 2N]. This transformation converts the original problem into the symmetric problem with M = 2N (E\_i = E\_{2N - i + 1} > ). We will allow x to increase beyond N and if x reaches 1 or 2N, the game ends. If someone is looking for tutorial, this might help. > **[Mathematical Expectation | CodeChef](https://www.codechef.com/wiki/tutorial-expectation)** > > Mathematical Expectation | CodeChef Thank you [Next page](https://discuss.codechef.com/t/exmv-editorial/101471.md?page=2)