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.
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:
There are n tests, so the expected count is: ans=n*q=n-(yes*yes+no*(no-1))/n
Why “If the order of tests is “YES-NO-NO”, then Valentine's solution won't pass the second test only; if the order is “NO-YES-NO”, then it will pass none of the tests; if the order is “NO-NO-YES”, the solution won't pass the first and the third tests.”
The "YES" come from two ways:1) when there is not have answer.txt;2) when answer.txt contain it.but i can't figure out this related to pass test! pass test should be the output.txt's content is same to answer.txt. how to explain the hint's explanation?