How can Solve this problem. Need more explanation. Thanks in advance.

# | User | Rating |
---|---|---|

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | Radewoosh | 3655 |

4 | ksun48 | 3547 |

5 | jiangly | 3492 |

6 | Miracle03 | 3480 |

7 | ecnerwala | 3400 |

8 | maroonrk | 3385 |

9 | peehs_moorhsum | 3384 |

10 | sunset | 3338 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 215 |

2 | YouKn0wWho | 190 |

2 | Um_nik | 190 |

4 | sus | 183 |

5 | awoo | 182 |

6 | Errichto | 179 |

7 | tourist | 177 |

8 | -is-this-fft- | 173 |

9 | Radewoosh | 170 |

10 | Ashishgup | 169 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/29/2021 02:54:37 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Lets define a function F(int nw, int nb, bool turn) which returns the probability of the princess winning from the state with

nwwhite mouses andnbblack mouses currently in the bag and if turn isfalseit is the princess turn to move and if turn istrueit is the Dragon's turn to move.From this we can see the answer to the original question is

F(w,b,false)First lets take the case where it is the princess's turn to move. For her to win, either she can directly pick a white mouse with probability or she picks a black mouse with probability and for her to win we need to multiply this with

F(nw,nb- 1,true). So, the princess's equation is :Now, lets take the case where it is the Dragon's turn to move. For the princess to win, the Dragon should always pick the black mouse which has probability (nb/(nw+nb)). Now, there can be two cases: the first one is that a white mouse escapes the bag and the second is that a black mouse escapes the bag.

Case 1 :

White mouse escapesThis happens with probability (-1 because the dragon already picked ablackmouse). Now we have to multiply this withF(nw- 1,nb- 1,false) (Since, the dragon picked 1 black mouse and 1 white mouse escaped and 'false' since it will be the princess's turn to move now).Case 2:

Black mouse escapesThis happens with probability (Since Dragon already picked a black mouse, there will (nb-1) black mouses left). This should be multipled withF(nw,nb- 2,false) (Since, white mouse remains same and Dragon picked a black mouse and another black mouse escapes).So, the equation for dragon's move will be:

We can declare an array

dp[white][black][turn] to store the results so that it is not computed again. So, the overall complexity would beO(2wb)We should also handle cases where, nw is 0 or nb is 0 or negative and return appropriate values.

Accepted Solution in C++