Idea to solve kill the birds

#1

suggest any idea or pseudocode how to solve the question - “Kill The Birds”?

#2

Hey @Jumbocoderzz
It is a simple brute force approach problem. You start with N=0,W=0 with probability 1. Then as you increase N, you’ll have a set of solutions. Iterate over all the solutions and consider the cases of both X points and Y points. Finally return value at W.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#4

I had done same thing as you said, but it gives wrong answer.
I commented the logic part in code - https://ide.codingblocks.com/s/183395
Please help me with the code of same.

#6

can you please explain your approach in little brief? Your code is not commented so it will take time in debugging.

#7

ignore i shared the wrong code I will try to debug your code

#8

Hi Vikas , This problem can be solved by dynammic programming Problem asks you to maximize your chances of winning i.e scoring atleast W points in this case. At each turn, you have two chances to choose from.
So, Lets maintain a state F(idx, pts) where idx denotes the turn which you are on and pts denotes the number of points you have fetched till now. So, overall the state denotes the maximum expected probability you can achieve while you are at idxth turn and having pts points.

F(idx, pts) {

   if ( idx == n ) return (pts >= w)

   //lets take choice #1
  //Now, we either hit the target with prob p1 or miss it with (1-p1)
   double  ans1 = p1*f(idx+1,pts+x) + (1-p1)*f(idx+1,pts)

   //lets take choice #2
  //Now we either hit the target with prob p2 or miss it with (1-p2)
   double ans2 = p2*f(idx+1,pts+y) + (1-p2)*f(idx+1,pts)

   return max(ans1,ans2)
}

my solution : https://ide.codingblocks.com/s/185041

In case of any doubt feel free to ask :slight_smile:
and if you got the answer please marks it as resolved