|
|
back to boardO(1) Formula I don't know why there were so many submitted O(n^2) DP solutions. Here is a simple formula for this problem: answer = n - (yes + yes*(yes-1) + no*(no-1))/n, where yes = s-2*n and no = n-yes are the total numbers of occurrences of corresponding strings in answer.txt. You can easily derive this if you try to think of probability of the same verdict for two arbitrary consecutive tests. Re: O(1) Formula Why this formula is right? I solved problem by DP, but i can't prove this formula. Re: O(1) Formula For any test, the probability to answer correctly is: the probability that the test is the first test and the answer on that test is "yes" plus the probability that the answer is on that test is "yes" and the answer on the previous test is also "yes" plus the probability that the answer on that test is "no" and the answer on previous test is also "no" That is: p=(1/n) *yes/n + (yes/n)*((yes-1)/n) + (no/n)*((no-1)/n) The probability to fail the test is: q=1-p There are n tests, so the expected count is: ans=n*q=n-(yes*yes+no*(no-1))/n Re: O(1) Formula This is so clear. Thank you. |
|
|