theRevenant's blog

By theRevenant, history, 5 years ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by vy007vikas (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I have tried it , but I didn't solve it.

I hope somebody reply your post because it seems a nice problem.