Probability and Expected Value (Light OJ)

Problem 1: 1027 - A Dangerous Maze 

Say, Total number of door is N.
So, probability of choosing any door is, P = 1 / N .
Total number of door which bring you back to the beginning is  N' . 
For getting out with the positive expected time is, E_x = X_i .
For getting out with the negative expected time is, E_y = abs(X_i) + E .
'E' means we have to start again!
 So, E = ( ∑E_x + ∑E_y ) / N
 => N *  E = ( ∑abs(X_i) + N' * E) [As Positive number of door + N' = N, so we add X_i to N]
 => E = ( ∑abs(X_i) ) / (N - N')

	#include<bits/stdc++.h>
	#include<ext/pb_ds/tree_policy.hpp>
	#include<ext/pb_ds/assoc_container.hpp>
	using namespace std;
	using namespace __gnu_pbds;
	#define ll long long
	#define inf 2000000000
	#define infLL 2000000000000000000
	#define MAX 100005
	#define sf(a) scanf("%d", &a)
	#define sfl(a) scanf("%lld", &a)
	#define pf(a) printf("%d\n", a)
	#define pfl(a) printf("%lld\n", a)
	#define Case(t) printf("Case %d: ", t)
	#define pii pair<int, int>
	#define MOD 1000000007
	#define PI acos(-1.0)
	#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
	void err(istream_iterator<string> it) {}
	template<typename T, typename... Args>
	void err(istream_iterator<string> it, T a, Args... args)
	{
	cerr << *it << " = " << a << endl;
	err(++it, args...);
	}
	clock_t t_Start;
	void Start()
	{
	t_Start = clock();
	}
	void End()
	{
	double Time = (double)(clock()-t_Start)/CLOCKS_PER_SEC;
	error(Time);
	}
	typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>orderedSet;
	int main()
	{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	//Start();
	int T;
	cin>>T;
	for(int t = 1; t <= T; t++)
	{
	int n, sum = 0, neg = 0;
	cin>>n;
	for(int i = 0; i < n; i++)
	{
	int a;
	cin>>a;
	sum+=abs(a);
	if(a < 0) neg++;
	}
	Case(t);
	if(neg==n)
	cout<<"inf"<<endl;
	else
	{
	int g = __gcd(sum, n-neg);
	int p = sum / g;
	int q = (n-neg) / g;
	cout<<p<<"/"<<q<<endl;
	}
	}
	//End();
	return 0;
	}

view raw 1027.cpp hosted with ❤ by GitHub

Problem 2: 1030 - Discovering Gold 

Possibility of going to 1st position is T₁ = 1.
Possibility of going to 2nd position is T₂ = T₁ / min(n - position from it comes, 6)
Possibility of going to 3rd position is T₃ = (T₁/min(n - position from it comes, 6)) + (T₂/min(n - position from it comes, 6))
...
Possibility of going to nth position is T_n = (T_i-6/min(n - position from it comes, 6)) + (T_i-5/min(n - position from it comes,6)) + ... + (T_n/min( n - position from it comes, 6))

Now just add up the result, E =  ∑ T_i * a_i

	#include<bits/stdc++.h>
	#include<ext/pb_ds/tree_policy.hpp>
	#include<ext/pb_ds/assoc_container.hpp>
	using namespace std;
	using namespace __gnu_pbds;
	#define ll long long
	#define inf 2000000000
	#define infLL 2000000000000000000
	#define MAX 100005
	#define sf(a) scanf("%d", &a)
	#define sfl(a) scanf("%lld", &a)
	#define pf(a) printf("%d\n", a)
	#define pfl(a) printf("%lld\n", a)
	#define Case(t) printf("Case %d: ", t)
	#define pii pair<int, int>
	#define MOD 1000000007
	#define PI acos(-1.0)
	#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
	void err(istream_iterator<string> it) {}
	template<typename T, typename... Args>
	void err(istream_iterator<string> it, T a, Args... args)
	{
	cerr << *it << " = " << a << endl;
	err(++it, args...);
	}
	clock_t t_Start;
	void Start()
	{
	t_Start = clock();
	}
	void End()
	{
	double Time = (double)(clock()-t_Start)/CLOCKS_PER_SEC;
	error(Time);
	}
	typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>orderedSet;
	int main()
	{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	//Start();
	int T;
	cin>>T;
	for(int t = 1; t <= T; t++)
	{
	int n;
	cin>>n;
	double a[n+5], dp[n+5], ans;
	dp[1] = 1;
	for(int i = 1; i <= n; i++)
	cin>>a[i];
	ans = a[1];
	for(int i = 2; i <= n; i++)
	{
	dp[i] = 0;
	for(int j = max(i-6, 1); j < i; j++)
	{
	dp[i]+=(dp[j]/min((double)(n-j), 6.0));
	}
	ans+=(a[i]*dp[i]);
	}
	Case(t);
	cout<<fixed<<setprecision(6)<<ans<<endl;
	}
	//End();
	return 0;
	}

view raw 1030.cpp hosted with ❤ by GitHub

Problem 3: 1038 - Race to 1 Again 

Let, Expected value of n for the problem is E(n).
So, E(1) = 0
      E(2) = ( (E(1) + 1) / cnt) + ( (E(2) + 1) / cnt) [i.e. Here cnt = 2 as it has two divisors]
      ....
      E(n) = ( (E(1) + 1) / cnt) + ( (E(d₁) + 1) / cnt) + ... + ( (E(n/d₁) + 1) / cnt) + ( (E(n) + 1) / cnt) [i.e. Here d₁ is a divisor of n]
 So, after solving the above equation we get, E(n) =  ( ∑ ( E(d_t) + 1 ) ) / ( cnt - 1 ) [i.e. Here d_t is 't'th divisor of n and cnt is total number of divisors of n]
 

	#include<bits/stdc++.h>
	#include<ext/pb_ds/tree_policy.hpp>
	#include<ext/pb_ds/assoc_container.hpp>
	using namespace std;
	using namespace __gnu_pbds;
	#define ll long long
	#define inf 2000000000
	#define infLL 2000000000000000000
	#define MAX 100005
	#define sf(a) scanf("%d", &a)
	#define sfl(a) scanf("%lld", &a)
	#define pf(a) printf("%d\n", a)
	#define pfl(a) printf("%lld\n", a)
	#define Case(t) printf("Case %d: ", t)
	#define pii pair<int, int>
	#define MOD 1000000007
	#define PI acos(-1.0)
	#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
	void err(istream_iterator<string> it) {}
	template<typename T, typename... Args>
	void err(istream_iterator<string> it, T a, Args... args)
	{
	cerr << *it << " = " << a << endl;
	err(++it, args...);
	}
	clock_t t_Start;
	void Start()
	{
	t_Start = clock();
	}
	void End()
	{
	double Time = (double)(clock()-t_Start)/CLOCKS_PER_SEC;
	error(Time);
	}
	typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>orderedSet;
	double dp[MAX];
	void divisor()
	{
	for(int i = 2; i < MAX; i++)
	{
	double cnt = 0;
	for(int j = 1; j*j <= i; j++)
	{
	if(i%j)
	continue;
	if(j*j==i)
	{
	cnt++;
	dp[i]+=(dp[j]+1);
	}
	else
	{
	cnt+=2;
	dp[i]+=(dp[j]+dp[i/j]+2);
	}
	}
	dp[i] = (dp[i])/(cnt-1);
	}
	}
	int main()
	{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	//Start();
	divisor();
	int T;
	cin>>T;
	for(int t = 1; t <= T; t++)
	{
	int n;
	cin>>n;
	Case(t);
	cout<<fixed<<setprecision(6)<<dp[n]<<endl;
	}
	//End();
	return 0;
	}

view raw 1038.cpp hosted with ❤ by GitHub

Problem 4: 1079 - Just another Robbery 

Using the concept of 0-1 Knapsack DP we can easily do this problem. We will store minimum probability to get arrested to rob a bank and then we will check with given probability.
DP[total_money + Money[i]] = min( DP[total_money + Money[i]], DP[total_money] + (1 - DP[total_money]) * P[i] )

	#include<bits/stdc++.h>
	#include<ext/pb_ds/tree_policy.hpp>
	#include<ext/pb_ds/assoc_container.hpp>
	using namespace std;
	using namespace __gnu_pbds;
	#define ll long long
	#define inf 2000000000
	#define infLL 2000000000000000000
	#define MAX 100005
	#define sf(a) scanf("%d", &a)
	#define sfl(a) scanf("%lld", &a)
	#define pf(a) printf("%d\n", a)
	#define pfl(a) printf("%lld\n", a)
	#define Case(t) printf("Case %d: ", t)
	#define pii pair<int, int>
	#define MOD 1000000007
	#define PI acos(-1.0)
	#define eps 1e-9
	#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
	void err(istream_iterator<string> it) {}
	template<typename T, typename... Args>
	void err(istream_iterator<string> it, T a, Args... args)
	{
	cerr << *it << " = " << a << endl;
	err(++it, args...);
	}
	clock_t t_Start;
	void Start()
	{
	t_Start = clock();
	}
	void End()
	{
	double Time = (double)(clock()-t_Start)/CLOCKS_PER_SEC;
	error(Time);
	}
	typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>orderedSet;
	int main()
	{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	//Start();
	int T;
	cin>>T;
	for(int t = 1; t <= T; t++)
	{
	double P;
	int n;
	cin>>P>>n;
	int M[n+5], money = 0;
	double p[n+5];
	for(int i = 0; i < n; i++)
	{
	cin>>M[i]>>p[i];
	money+=M[i];
	}
	double dp[MAX];
	for(int i = 0; i < MAX; i++)
	dp[i] = 1;
	dp[0] = 0;
	for(int i = 0; i < n; i++)
	{
	for(int j = money; j >= 0; j--)
	{
	if(dp[j]==1)
	continue;
	dp[j+M[i]] = min(dp[j+M[i]], dp[j]+(1-dp[j])*p[i]);
	}
	}
	int ans;
	for(int i = money; i >= 0; i--)
	{
	if(dp[i] < P || fabs(P-dp[i]) < eps)
	{
	ans = i;
	break;
	}
	}
	Case(t);
	cout<<ans<<endl;
	}
	//End();
	return 0;
	}

view raw 1079.cpp hosted with ❤ by GitHub

Problem 5: 1104 - Birthday Paradox 

Bithday Paradox , read this and you will get the answer. Here I have used the generalized formula.

	#include<bits/stdc++.h>
	#include<ext/pb_ds/tree_policy.hpp>
	#include<ext/pb_ds/assoc_container.hpp>
	using namespace std;
	using namespace __gnu_pbds;
	#define ll long long
	#define inf 2000000000
	#define infLL 2000000000000000000
	#define MAX 100005
	#define sf(a) scanf("%d", &a)
	#define sfl(a) scanf("%lld", &a)
	#define pf(a) printf("%d\n", a)
	#define pfl(a) printf("%lld\n", a)
	#define Case(t) printf("Case %d: ", t)
	#define pii pair<int, int>
	#define MOD 1000000007
	#define PI acos(-1.0)
	#define eps 1e-9
	#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
	void err(istream_iterator<string> it) {}
	template<typename T, typename... Args>
	void err(istream_iterator<string> it, T a, Args... args)
	{
	cerr << *it << " = " << a << endl;
	err(++it, args...);
	}
	clock_t t_Start;
	void Start()
	{
	t_Start = clock();
	}
	void End()
	{
	double Time = (double)(clock()-t_Start)/CLOCKS_PER_SEC;
	error(Time);
	}
	typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>orderedSet;
	int main()
	{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	//Start();
	int T;
	cin>>T;
	for(int t = 1; t <= T; t++)
	{
	int n;
	cin>>n;
	double p = 1.0;
	int ans;
	for(int i = 1; i < 1000; i++)
	{
	p = p * (1.0 - ((double)i/n));
	double tot = 1.0 - p;
	if(fabs(tot-0.5)<eps || (tot-eps)>0.5)
	{
	ans = i;
	break;
	}
	}
	Case(t);
	cout<<ans<<endl;
	}
	//End();
	return 0;
	}

view raw 1104.cpp hosted with ❤ by GitHub

Some Useful Links:
Sums and Expected Value — part 1 (by Errichto) 
Sums and Expected Value — part 2 (by Errichto) 
Explaination of LOJ 1027