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*(yes1) + no*(no1))/n, where yes = s2*n and no = nyes 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. Why this formula is right? I solved problem by DP, but i can't prove this 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)*((yes1)/n) + (no/n)*((no1)/n) The probability to fail the test is: q=1p There are n tests, so the expected count is: ans=n*q=n(yes*yes+no*(no1))/n Some tests? You can try use these tests: 4999 12832 >2455.1680336 5000 12345 >2490.9210000 4987 9999 >50.7443353 1234 3456 >394.1183144 2976 6547 >952.8800403 3487 8000 >1448.9340407 4955 11111 >1820.5574168 456 968 >99.1228070 43 123 >10.4651163 1 2 >1 4 9 >2.2500000 3 9 >0 2 5 >1.5 2 4 >1 4399 13013 >352.6492385 4321 9923 >1803.1751909 4001 10500 >1877.1534616 4000 10001 >2000.4992500 4000 10000 >2000.5000000 4123 9999 >2015.9083192 i've been thinking at this problem for 2 weeks. can somebody give me a hint ? always wa at test 11,why? I can't figure out what the hint about! Why “If the order of tests is “YESNONO”, then Valentine's solution won't pass the second test only; if the order is “NOYESNO”, then it will pass none of the tests; if the order is “NONOYES”, the solution won't pass the first and the third tests.” Can you give me more detailed explanation？ This is test #11: 5000 12500 Who have answer? Edited by author 06.09.2013 20:53 The answer for that is 2500.50 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? We answer "YES" if "YES" was right answer for previous test. No matter when I used double or long double, my code still got TLE. Opt[Now][j][0] = Opt[Pre][j][0] + Opt[Pre][j][1] + Opt[Pre][j][3]; Opt[Now][j][1] = Opt[Pre][j  1][0] + Opt[Pre][j  1][2] + Opt[Pre][j  1][1]; Opt[Now][j][2] = Opt[Pre][j][2] + Opt[Pre][j][3]; Opt[Now][j][3] = Opt[Pre][j  1][2] + Opt[Pre][j  1][3]; I had to write a Pascal code using extended and got AC. Could anyone tell me how to AC in C++? I know solution which can be written on all allowable languages. I suppose, this solution won't get TLE. Becouse it is O(1). I know solution which can be written on all allowable languages. I suppose, this solution won't get TLE. Becouse it is O(1). During 3 days I couldn’t find appropriate way to work with big binomials having lost of order or overflow. Simple and clever routine was found and gave satisfaction. Could you give any hint: what kind of "simple routine" have you found? I also have got overflow / lost of order? Is it possible to avoid such problem in O(N^2) solution? I don't know what your algo is, but my dynamic O(N^2) solution hasn't problems with overflows  all numbers is of order N Thanks! I've got AC with O(N^2) DP. Every value was not exceeding N. But it's still interesting  how did some people get AC with 0.015sec and minimum of memory. 
