Hi, I am stuck at problem J of asc 29, and cant think of any solution. Can someone please guide me towards the solution.

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

1 | Um_nik | 3459 |

2 | tourist | 3438 |

3 | maroonrk | 3359 |

4 | ecnerwala | 3347 |

5 | Benq | 3317 |

6 | ksun48 | 3309 |

7 | boboniu | 3300 |

8 | Petr | 3293 |

9 | Radewoosh | 3289 |

10 | TLE | 3223 |

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

1 | Errichto | 206 |

2 | Monogon | 194 |

3 | SecondThread | 191 |

4 | pikmike | 187 |

5 | antontrygubO_o | 186 |

6 | vovuh | 185 |

7 | Ashishgup | 181 |

8 | Um_nik | 180 |

9 | Radewoosh | 169 |

10 | pashka | 167 |

I am not getting WA for the sample case 2 ( an error of 0.01) for this question (Problem A — Casino) http://codeforces.com/gym/100357

My approach is as follows :-

Since player always chooses best bet possible , for any amount of money we have, loosing a bet and going back to smaller amount of money can never be the best bet. Suppose dp1[a] denotes the max prob. of winning using best bet and also stores the index of the best bet.

dp1[a] = max over a<j<=n {dp1[i + w[j]] * p[j]/s};

Now we have the best bets stored for every index. Let dp[a][b] denote that at "a" unit of time, if we have "b" units of money, then what is the probability of getting to this state. Now we can reach b amounts of money from any state if the money at that state + money won from best bet == b. Using this we can get a dp relation . Finally we can run this dp over some 10000 units of time or any other large number till it becomes stable for an error of 10^9. Or we can use matrix exponentiation over the dp and compute even for a much larger limit.

Please help me, i can't understand why my method is wrong. Even if you can not understand my approach, it would be great if you explain how to solve the question.

My team ranked 107 on snackdown el. round and we just missed the onsites with a time diff of <20 mins. However i checked one of my WA on the easiest question and i noticed this. Problem Link : www.codechef.com/problems/TTENIS

Code which gave WA during contest : http://www.codechef.com/viewsolution/7190656 Code which gave AC after contest : http://www.codechef.com/viewsolution/7248112 The only difference between these two codes is that "scanf("%d", &t);" is replaced by "cin>>t;"

Also another query , if someone can read the question and tell me why this logic fails: http://www.codechef.com/viewsolution/7191333 The logic is based on the fact that this is given in the question :- "(It is guaranteed that statistics always represent a valid , finished match.)"

Any help will be grateful. Thnx a lot :)

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/21/2020 15:36:22 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|