LOJ 1027 - A Dangerous Maze

Before reading this tutorial I would suggest you to read this article for a better understanding of Mathematical Expectation

By the definition of Mathematical Expectation,
If P(i) represents probability of choosing door i and T(i) represents time to get out of the maze if we choose door i,
then for n number of doors,
Mathematical Expectation,
E = P(1)*T(1) + P(2)*T(2) + P(3)*T(3) + ...... + P(n)*T(n)

Let's begin with analyzing the 3rd test of the sample test case. The 3rd test case is -

3
3 -6 -9

Here, we are given 3 doors. And we can only get out of the maze by the first door with a cost of 3 minutes. Where, the 2nd and 3rd door would return us to the same position costing 6 minutes and 9 minutes respectively.
Let's assume the final expected time be E, what is our answer.
So here,
E = P(1)*T(1) + P(2)*T(2) + P(3)*T(3)

Each time we can randomly choose 1 door out of 3 doors and choosing one door is an independent event.
So, probability of choosing any door would be 1/3.
Thus, P(i) = 1/3, for i = 1, 2, 3
Now, we need to calculate T(i) for i = 1, 2, 3

If i = 1 i.e if we choose 1st door it would take us straight out of the maze. So T(1) = 3
If i = 2 i.e if we choose 2nd door it would take 6 minutes but would return us to the same position!
So, sadly we would have to start the whole process once again. As we assumed before that the final expected time is E, therefore we can safely say that for starting the whole process once again we will need E minutes more!
Thus time to get out of the maze if we choose 2nd gate
T(2) = Time to return to the same position + Expected time to get out of the maze for starting the process from beginning Therefore, T(2) = 6 + E
Similiarly, if i = 3, T(3) = 9 + E

So, finally,
E = (1/3)*3 + (1/3)*(6 + E) + (1/3)*(9 + E)
E = (1/3)*(3 + 6 + 9) + (1/3)*(E + E)
(1/3)*(3*E - 2*E) = (1/3)*(3 + 6 + 9)
E*(3 - 2) = (3 + 6 + 9) (Diving both sides by 1/3)
and, E = (3 + 6 + 9)/(3 - 2) ......... (1)
which ultimately yields, E = 18 / 1, which is our answer.

If we look at equation (1), we can see,
3 + 6 + 9 is the sum of absolute value of time taken by each door.
And, 3 is the number of doors and 2 is the number of reverse doors (doors that returns to the same postion). In other word, (3-2) is the number of doors that can get us out of the maze.

So, now we can have a generalized solution for this problem,
E = (sum of absolute value of the given times) / (number of gates that can take us out of the maze)

As, the output format is p/q, so both the the numbers divded by their GCD will be the ultimate solution.

Special Case

If there is no gate that can take us out of the maze, we would never get out of the maze! So, the ans would be inf

Time Complexity

As we are using an equation to solve the problem the time complexity would be simply of O(n)

Solution in C++

#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
#define endl '\n'
#define scan(n) scanf("%lld", &n);
#define print(n) printf("%lld", n);
#define pb(n) push_back(n)

void compute(ll a, ll b){
    ll x = __gcd(a,b);
    printf("%lld/%lld\n",a/x,b/x);
}

int main()
{
    ll t, no = 1;
    scan(t);
    while(t--){
        ll n;
        scan(n);
        ll a[n], sum = 0;
        for(ll i=0; i<n; i++) {
            scan(a[i]); sum+=abs(a[i]);
        }
        ll neg_sum = 0;
        for(ll i=0; i<n; i++){
            if(a[i]<0) neg_sum++;
        }
        printf("Case %lld: ",no++);
        if(neg_sum == n) printf("inf\n");
        else compute(sum,n-neg_sum);
    }
    return 0;
}

Tutorial source