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.
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 !!
ABRA-KADABRA-GILLI-GILLI-GOOO
TAADAA!!
Now this problem doesnt require dp
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).
#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” .
PS: I was really bored and so decided to have some fun. Hope you dont mind!! Its all fun in games and pranks
Nice way to explain… 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…
Whats really mysterious is that this problem has a mere 18% accuracy rate lol.
@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 . I’m sorry if it came across that way.
@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.