I understand the entire solution except the part " The probability of reaching any particular green square is the same for all but the green square in the last row", I don't get it why the last row is any different? ↵
↵
My understanding of the solution : We take all the squares which the extension of the diaganoonal of the rectangle part. We have to pass through one of these squares in order to reach the destination. Since there can be interesction between these paths, we individually find the probability of reaching each of these squares and add them.↵
↵
Can anyone please explain how the last row is any different?↵
↵
My code : ↵
↵
`↵
//IF YOU GIVE UP,THEN YOU DON'T DESERVE IT↵
↵
#include<bits/stdc++.h>↵
#define ll long long↵
#define pii pair<int,int>↵
#define pll pair<long long,long long>↵
#define pb push_back↵
#define endl "\n"↵
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
#define PI 3.14159265358979323846264↵
#define isz(x) (int)x.size()↵
using namespace std; ↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
using namespace __gnu_pbds;↵
↵
#define typ int↵
#define ordered_set tree<typ, null_type, less<typ>, rb_tree_tag, tree_order_statistics_node_update>↵
//*s.find_by_order(x) --> value at position x(0-indexed)↵
//s.order_of_key(x) --> number of elements less than x↵
#define eps 1e-9↵
#define maxn 100005↵
↵
double lfact[maxn];↵
ll w,h,l,u,r,d;↵
↵
// find and once we get to these squares the probability of reaching destination is 1. Since there cannot be interesction between these paths, we individually find the probability toof reach sqaure (m,n) from (1,1)↵
double find_prob(ll m, ll n)↵
{↵
ll u = m+n-2;↵
↵
double res = lfact[u] - lfact[n-1] - lfact[u-n+1]-(u*log(2));↵
return exp(res);↵
}↵
↵
double solve(ll w,ll h,ll l,ll u,ll r,ll d)↵
{ ↵
// deal squares below y = x line↵
int cr = d;↵
int cc = l;↵
cr++;cc--;↵
double ans = 0.0;↵
↵
while(cc>0 and cr<=h)↵
{↵
ans+=find_prob(cr,cc);↵
cc--;cr++;↵
}↵
↵
// deal squares above y = x line↵
cr = u;↵
cc = r;↵
cc++;cr--;↵
while(cc<=w and cr>0)↵
{↵
ans+=find_prob(cr,cc);↵
cr--;cc++;↵
}↵
return ans;↵
↵
}↵
↵
main()↵
{↵
int t;↵
cin>>t;↵
int tt = t;↵
lfact[0] = 0.0;↵
for(int i=1;i<=100000;i++)↵
lfact[i] = lfact[i-1] + log(i);↵
↵
while(t--)↵
{↵
↵
cin>>w>>h>>l>>u>>r>>d;↵
↵
double ans = solve(w,h,l,u,r,d);↵
cout<<"Case #"<<tt-t<<": "<<setprecision(9)<<ans<<endl;↵
}↵
}↵
↵
`ing each of these squares and add them.↵
↵
Can anyone please explain how the last row is any different?↵
↵
My code : https://ideone.com/FIGKWD (got WA)
↵
My understanding of the solution : We take all the squares which the extension of the diag
↵
Can anyone please explain how the last row is any different?↵
↵
My code : ↵
↵
`↵
//IF YOU GIVE UP,THEN YOU DON'T DESERVE IT↵
↵
#include<bits/stdc++.h>↵
#define ll long long↵
#define pii pair<int,int>↵
#define pll pair<long long,long long>↵
#define pb push_back↵
#define endl "\n"↵
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
#define PI 3.14159265358979323846264↵
#define isz(x) (int)x.size()↵
using namespace std; ↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
using namespace __gnu_pbds;↵
↵
#define typ int↵
#define ordered_set tree<typ, null_type, less<typ>, rb_tree_tag, tree_order_statistics_node_update>↵
//*s.find_by_order(x) --> value at position x(0-indexed)↵
//s.order_of_key(x) --> number of elements less than x↵
#define eps 1e-9↵
#define maxn 100005↵
↵
double lfact[maxn];↵
ll w,h,l,u,r,d;↵
↵
// find
double find_prob(ll m, ll n)↵
{↵
ll u = m+n-2;↵
↵
double res = lfact[u] - lfact[n-1] - lfact[u-n+1]-(u*log(2));↵
return exp(res);↵
}↵
↵
double solve(ll w,ll h,ll l,ll u,ll r,ll d)↵
{ ↵
// deal squares below y = x line↵
int cr = d;↵
int cc = l;↵
cr++;cc--;↵
double ans = 0.0;↵
↵
while(cc>0 and cr<=h)↵
{↵
ans+=find_prob(cr,cc);↵
cc--;cr++;↵
}↵
↵
// deal squares above y = x line↵
cr = u;↵
cc = r;↵
cc++;cr--;↵
while(cc<=w and cr>0)↵
{↵
ans+=find_prob(cr,cc);↵
cr--;cc++;↵
}↵
return ans;↵
↵
}↵
↵
main()↵
{↵
int t;↵
cin>>t;↵
int tt = t;↵
lfact[0] = 0.0;↵
for(int i=1;i<=100000;i++)↵
lfact[i] = lfact[i-1] + log(i);↵
↵
while(t--)↵
{↵
↵
cin>>w>>h>>l>>u>>r>>d;↵
↵
double ans = solve(w,h,l,u,r,d);↵
cout<<"Case #"<<tt-t<<": "<<setprecision(9)<<ans<<endl;↵
}↵
}↵
↵
`
↵
Can anyone please explain how the last row is any different?↵
↵
My code : https://ideone.com/FIGKWD (got WA)
