EXMV - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Muhammad Najmul Hasan Nayeem
Tester: Takuki Kurokawa, Lavish Gupta
Editorialist: Yash Kulkarni

DIFFICULTY:

1541

PREREQUISITES:

Expected Value, Probabilty

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)iE_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} + 1E_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
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
#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;
}
2 Likes

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.

20 Likes

could anyone provide a good resource for expectation theory i am quite bad in it

7 Likes

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.

2 Likes

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

1 Like

I am not getting the comparison for En.
Can someone please explain.

Solving linear recurrences

This might help

2 Likes

how does reaching the state at M end the game where M != 1

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.

1 Like

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.

3 Likes

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

1 Like

that line is saying “Let us consider”

how did u think of that :sob:

what’s the name of the problem?

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.

1 Like

Literally me :slight_smile:

1 Like

What is that M in the Symmetric Problem?

from where did it come from?

We just know game ends when it reaches 1 right?

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.

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.

2 Likes

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.

Thank you