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