theRevenant's blog

By theRevenant, history, 8 years ago, In English

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

http://mirror.codeforces.com/gym/100343

Full text and comments »

Tags asc, scc
  • Vote: I like it
  • 0
  • Vote: I do not like it

By theRevenant, history, 9 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://mirror.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.

Full text and comments »

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

By theRevenant, history, 9 years ago, In English

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 :)

Full text and comments »

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