Google Kickstart Round B "Wandering Robot Problem" help

Правка en1, от AjaySabarish, 2020-07-31 14:30:05

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 diaganol 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, 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 probability to 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;
}

}

`

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский AjaySabarish 2020-08-01 10:01:18 236
en5 Английский AjaySabarish 2020-08-01 09:59:46 11
en4 Английский AjaySabarish 2020-07-31 14:41:02 24
en3 Английский AjaySabarish 2020-07-31 14:40:10 113
en2 Английский AjaySabarish 2020-07-31 14:33:35 1834 (published)
en1 Английский AjaySabarish 2020-07-31 14:30:05 2453 Initial revision (saved to drafts)