How to approach this DP problem?

How to approach this DP Win-the-Game problem on hackerearth?

When it comes to DP, I generally get stuck completely with absolutely no idea how to even take the first step.

Is the dp part giving you problem?

Lets solve your problem then! Damn dp giving trouble to our lovely @sun_d !!

Click to view

ABRA-KADABRA-GILLI-GILLI-GOOO

TAADAA!!

Now this problem doesnt require dp :smiley:

Its a simple probability question. My second hint box contains my solution, you should check it if you get really stuck (as in, cant get soln. after ~10 tries).

Click to view
#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int r,g;
        cin>>r>>g;
        double t=r+g,ans=0;
        
        if(r==0)cout<<fixed<<setprecision(6)<<1.000000<<endl;
        else
        {
            double c=1.0;
            while(r>0 && g>=0 && t>0)
            {
                ans+= c*r/t;
                c*= (g)*(g-1)/((t-1)*t);
                g-=2;
                t-=2;
            }
            cout<<fixed<<setprecision(6)<<ans<<endl;
        }
    }
    return 0;
}

MAKE SURE TO MANUALLY PRINT TILL 6 DIGITS!! I was getting WA for printing “1” instead of “1.000000” . :frowning:

Click to view

PS: I was really bored and so decided to have some fun. Hope you dont mind!! Its all fun in games and pranks :smiley: :slight_smile:

6 Likes

Nice way to explain… :stuck_out_tongue: I was also thinking same, why we need DP to solve this… But later I thought it can also be solved using 2D dp… but that would be unnecessary… @sun_d if you want to know dp approach I can explain that too if that helps… :slight_smile:

Whats really mysterious is that this problem has a mere 18% accuracy rate lol.

1 Like

@kauts_kanu please share your dp logic. This problem was categorized under the DP practice problems. So I wanted to learn the DP approach. Thanks.

@vijju123 there are many problems where one does not need DP, even then people apply dp. I just wanted to know the DP approach so as to improve my DP skill. It’s not the question of whether we need it. Making fun of others is not appropriate.

O_O

Dude, chill. I was not making fun of you :confused: . I’m sorry if it came across that way.

1 Like

@sun_d Making fun?? Making fun??? You never clearly mentioned that you only wanted a dp approach. Is taking out ones time and trying to make something seem interesting and fun called MAKING FUN??? Damn me. I guess I haven’t been paying much attention to my English classes since childhood… Pardon me.

1 Like

@sun_d there are very few answers here which make you laugh hard this was definitely was among them plz dont get offended by such small things. by the way @vijju123 it should be ABRA-KADABRA-GILLI-GILLI-CHOO not GOOO

2 Likes